二.双链表

一、基础概念类面试官提问双向链表和单链表的核心区别是什么有什么优劣适用哪些场景回答你可以把单链表理解成单行公路只能往前开要掉头必须从头绕一圈双向链表就是双行道前后方向都能直接通行。核心优劣对比维度单链表双向链表遍历方向仅单向正反双向访问前驱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 缓存的淘汰队列操作系统进程 / 线程就绪队列、等待队列、内存页回收链表网络服务连接池空闲连接管理、定时器超时链表、消息队列内存管理内存池空闲块链表支持快速合并相邻空闲块