当前位置：首页 > news >正文

二.双链表

news 2026/7/19 10:14:50

一、基础概念类

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

回答：

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

核心优劣对比

维度	单链表	双向链表
遍历方向	仅单向	正反双向
访问前驱	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 = 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)」的核心要求。

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

回答：

三个最高频的坑：

指针顺序写错导致断链：比如先修改了前节点的 next，就找不到原来的下一个节点了，正确顺序永远是「先改新节点的指针，再改相邻节点的指针」
只改 next 忘了改 prev：正向遍历没问题，反向遍历直接出错，这种 bug 非常隐蔽
删除节点后遗留野指针：没有释放内存，或者还持有已删除节点的指针继续访问

四、项目实战知识

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; } } } }