一、基础概念类

面试官提问：双向链表和单链表的核心区别是什么？有什么优劣？适用哪些场景？

回答：

你可以把单链表理解成单行公路，只能往前开，要掉头必须从头绕一圈；双向链表就是双行道，前后方向都能直接通行。

核心优劣对比

适用场景

需要频繁双向遍历、需要 O (1) 操作任意节点、头尾增删都频繁的场景，典型代表是 LRU 缓存、操作系统进程队列、内存池空闲块管理。

二、核心操作类

节点结构体

struct DListNode { int val; DListNode* prev; DListNode* next; DListNode(int x) : val(x), prev(nullptr), next(nullptr){} }

头尾哨兵

工业级双向链表几乎都会加头尾哨兵（哑节点）：两个固定存在的空节点，初始时head->next = tail，tail->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)」的核心要求。

提问：双向链表最容易踩的坑有哪些？

回答：

三个最高频的坑：

1. 指针顺序写错导致断链：比如先修改了前节点的 next，就找不到原来的下一个节点了，正确顺序永远是「先改新节点的指针，再改相邻节点的指针」

2. 只改 next 忘了改 prev：正向遍历没问题，反向遍历直接出错，这种 bug 非常隐蔽

3. 删除节点后遗留野指针：没有释放内存，或者还持有已删除节点的指针继续访问

四、项目实战知识

LRU 缓存完整实现

场景说明：LRU（最近最少使用）缓存是后端、基础架构岗的超高频面试题，也是双向链表最经典的落地场景，要求get和put操作均为 O (1)。

实现原理：

• 哈希表：存key到链表节点的映射，实现 O (1) 查找

• 双向链表：按访问顺序维护节点，头部是「最近使用」，尾部是「最久未使用」

• 容量超限时，删除尾部节点，同时清除哈希表对应记录

完整代码:

#include<unordered_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_map<int, 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两个指针，把这个小节点嵌入到业务数据结构体里，是「数据装链表节点」

核心优势：

1. C 语言实现泛型：没有模板语法的情况下，一套链表 API 适配所有数据类型，不用为每种数据重写链表逻辑

2. 性能极高：无泛型开销，纯指针操作，效率拉满

3. 灵活性强：一个数据结构可以同时挂多个链表，比如进程结构体可以同时挂在就绪队列、等待队列中

应用场景：Linux 内核几乎所有链表场景都用它：进程调度队列、内存页 LRU 回收链表、设备驱动链表、网络连接队列，是工业界双向链表的最优实践之一。

实际项目中的常见落地场景

缓存系统：LRU/LFU 缓存的淘汰队列

操作系统：进程 / 线程就绪队列、等待队列、内存页回收链表

网络服务：连接池空闲连接管理、定时器超时链表、消息队列

内存管理：内存池空闲块链表，支持快速合并相邻空闲块