二.双链表-北京尧图网络

一、基础概念类面试官提问双向链表和单链表的核心区别是什么有什么优劣适用哪些场景回答你可以把单链表理解成单行公路只能往前开要掉头必须从头绕一圈双向链表就是双行道前后方向都能直接通行。核心优劣对比维度单链表双向链表遍历方向仅单向正反双向访问前驱O (n) 需遍历O (1) 直接访问删除指定节点O (n) 需先找前驱O (1) 直接操作尾删效率O (n) 找倒数第二个节点O (1) 直接操作内存开销低1 个指针略高2 个指针维护成本低改 2 个指针高改 4 个指针易出错适用场景需要频繁双向遍历、需要 O (1) 操作任意节点、头尾增删都频繁的场景典型代表是 LRU 缓存、操作系统进程队列、内存池空闲块管理。二、核心操作类节点结构体struct DListNode { int val; DListNode* prev; DListNode* next; DListNode(int x) : val(x), prev(nullptr), next(nullptr){} }头尾哨兵工业级双向链表几乎都会加头尾哨兵哑节点两个固定存在的空节点初始时head-next tailtail-prev head。彻底消除空链表、操作头尾节点的边界判断所有增删操作都统一为「中间节点操作」逻辑一致bug 率极低仅用 2 个节点的极小空间换极高的代码可维护性初始化代码DListNode* head new DListNode(0); DListNode* tail new DListNode(0); head-next tail; tail-prev head;头部插入节点考点指针修改顺序、哨兵节点用法void addTohead(DListNode* node) { node-prev head; node-next head-next; head-next-prev node; head-next node; }临场提醒永远先改新节点的指针再改原链表的指针不会出现断链。删除指定节点O (1)考点双向链表核心优势和单链表的核心差异void removeNode(DListNode* node) { node-next-prev node-prev; node-prev-next node-next; node-prev nullptr; node-next nullptr; }移动节点到头部考点LRU 核心操作组合逻辑封装void removeToHead(DListNode* node) { removeNode(node); addToHead(node); }临场提醒先删后插逻辑最清晰不要试图直接挪指针极易写错。尾部删除节点尾删 O (1)考点双向链表对比单链表的优势LRU 淘汰操作// 删除尾部有效节点最久未使用返回节点方便释放 DListNode* removeTail() { DListNode* tailNode tail-prev; removeNode(tailNode); return tailNode; }双向链表反转DListNode* reverseDList(DListNode* head) { DListNode* curr head; DListNode* temp nullptr; while(curr ! nullptr) { temp curr-prev; curr-prev curr-next; curr-next temp; curr curr-prev; } return temp nullptr ? head : temp-prev; }三、进阶理解类提问为什么工业级双向链表几乎都用哨兵节点回答核心是用极小的空间成本消除边界 case降低 bug 率。没有哨兵的话插入头节点、删除尾节点都要单独判断「空链表」「只有一个节点」的分支逻辑冗余且容易漏。哨兵节点是固定存在的所有增删操作都等价于操作中间节点逻辑完全统一代码更简洁也没有额外的性能损耗。提问LRU 缓存为什么一定要用双向链表用单链表不行吗回答核心是性能要求不允许。LRU 有两个核心高频操作访问一个元素后把它移到链表头部标记为最近使用缓存满了删除链表尾部的元素淘汰最久未使用如果用单链表移动节点需要先遍历找到它的前驱节点时间复杂度直接退化成 O (n)。而双向链表可以 O (1) 拿到前驱节点删除头插全是 O (1)刚好匹配 LRU 缓存「读写都要 O (1)」的核心要求。提问双向链表最容易踩的坑有哪些回答三个最高频的坑指针顺序写错导致断链比如先修改了前节点的 next就找不到原来的下一个节点了正确顺序永远是「先改新节点的指针再改相邻节点的指针」只改 next 忘了改 prev正向遍历没问题反向遍历直接出错这种 bug 非常隐蔽删除节点后遗留野指针没有释放内存或者还持有已删除节点的指针继续访问四、项目实战知识LRU 缓存完整实现场景说明LRU最近最少使用缓存是后端、基础架构岗的超高频面试题也是双向链表最经典的落地场景要求get和put操作均为 O (1)。实现原理哈希表存key到链表节点的映射实现 O (1) 查找双向链表按访问顺序维护节点头部是「最近使用」尾部是「最久未使用」容量超限时删除尾部节点同时清除哈希表对应记录完整代码:#includeunordered_map using namespace std; class LRUCache{ private: struct DListNode { int key; int val; DListNode* prev; DListNode* next; DListNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr){} }; // 头尾哨兵 DListNode* head; DListNode* tail; // 缓存大小 int capacity; // k-v容器 unordered_mapint, DListNode* cache; // 封装基础操作----------------- // 删除指定元素 void removeNode(DListNode* node) { node-next-prev node-prev; node-prev-next node-next; } // 头部添加元素 void addToHead(DListNode* node) { node-prev head; node-next head-next; head-next-prev node; head-next node; } // 移动元素到头部 void moveToHead(DListNode* node) { removeNode(node); addToHead(node); } // 删除尾部元素 DListNode* removeTail() { DListNode* temp tail-prev; removeNode(temp); return temp; } public: LRUCache(int cap) : capacity(cap) { head new DListNode(0, 0); tail new DListNode(0, 0); head-next tail; tail-prev head; } // 调用元素 int get(int key) { // 无要调用的元素 if(!cache.count(key)) return -1; moveToHead(cache[key]); return cache[key]-val; } // 添加元素 void put(int key, int value) { // 元素已存在的情况:更新值把元素移动到头部 if(cache.count(key)) { DListNode* temp cache[key]; temp-val value; moveToHead(temp); } else { DListNode* node new DListNode(key, value); addToHead(node); cache[key] node; // 超出容量时删除尾部元素 if(cache.size() capacity) { DListNode* temp removeTail(); cache.erase(temp-key); delete temp; } } } }Linux 内核list_head双向循环链表设计亮点内核采用侵入式链表设计和我们平时写的链表完全反过来普通链表节点结构体包含「数据指针」是「链表装数据」侵入式链表链表节点只有prev和next两个指针把这个小节点嵌入到业务数据结构体里是「数据装链表节点」核心优势C 语言实现泛型没有模板语法的情况下一套链表 API 适配所有数据类型不用为每种数据重写链表逻辑性能极高无泛型开销纯指针操作效率拉满灵活性强一个数据结构可以同时挂多个链表比如进程结构体可以同时挂在就绪队列、等待队列中应用场景Linux 内核几乎所有链表场景都用它进程调度队列、内存页 LRU 回收链表、设备驱动链表、网络连接队列是工业界双向链表的最优实践之一。实际项目中的常见落地场景缓存系统LRU/LFU 缓存的淘汰队列操作系统进程 / 线程就绪队列、等待队列、内存页回收链表网络服务连接池空闲连接管理、定时器超时链表、消息队列内存管理内存池空闲块链表支持快速合并相邻空闲块

二.双链表

相关推荐

AI智能体开发学习文档（四）

CVE\-2024\-45519实战分析：Zimbra Postjournal未认证RCE漏洞利用、检测与防御全套方案

进程、线程、协程的优缺点

更多资讯

HTML table标签属性全解析：从过时属性到现代CSS替代方案

为什么劝你做 Agent 先手搓一遍：框架的抽象税，是生产环境最贵的隐性负债

Kafka与RabbitMQ核心差异及选型指南

Python模拟MapReduce分治思想 | 从单文件统计到大文件拆分聚合学习笔记

51单片机+ESP8266构建稳定智能家居控制系统

大模型不擅长选股，却能治好你的手痒？AI交易心态陪练实操指南

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？