Linked List
链表是一种线性数据结构，其中的元素（节点）不是通过物理顺序存储，而是通过指针（或引用）连接在一起
[data | next] -> [data | next] -> [data | next]
核心特点
- 动态内存分配：不需要预先知道数据量大小
- 非连续存储：节点在内存中可以是分散的
- 顺序访问：不能像数组一样直接通过索引访问
缺点
- 访问速度慢：需要遍历才能访问特定元素
- 内存开销大：需要额外的空间存储指针
- 缓存不友好：非连续存储，CPU缓存命中率低
| 操作 | 时间复杂度 |
|---|---|
| 遍历 | O(n) |
| 查找 | O(n) |
| 插入 | O(1)* |
| 删除 | O(1)* |
*前提是已知节点
Single LinkedList
结构
节点结构
[data|next]
data：实际存储的数据next：指向后一个节点的地址
[data|next] -> [data|next] -> [data|next] -> null
- 每个节点只能指向下一个节点（
next） - 单链表只能向前遍历，无法回溯
适用场景
- 需要频繁插入/删除的场景
- 内存受限或数据规模不确定的场景
- 只需要单向遍历
- 实现栈/队列
不适用场景
- 频繁随机访问
- 需要双向遍历
- 数据量大：指针占用空间
- 需要快速查找
- 缓存性能重要
应用案例
LRU缓存淘汰算法
实现
遍历
时间复杂度O(n)
void traverse(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->val << " ";
current = current->next;
}
}
查找
ListNode* search(ListNode* head, int target) {
ListNode* current = head;
while (current != nullptr) {
if (current->val == target) {
return current;
}
current = current->next;
}
return nullptr;
}
插入
1.头插（O(1)）
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
return newNode; // 新节点成为新的头节点
}
2.在指定位置后插入（O(1)）
void insertAfter(ListNode* prevNode, int val) {
if (prevNode == nullptr) return;
ListNode* newNode = new ListNode(val);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
删除
1.删除指定值的节点
ListNode* deleteNode(ListNode* head, int val) {
// 处理头节点就是要删除的节点
while (head != nullptr && head->val == val) {
ListNode* temp = head;
head = head->next;
delete temp;
}
// 处理中间节点
ListNode* current = head;
while (current != nullptr && current->next != nullptr) {
if (current->next->val == val) {
ListNode* temp = current->next;
current->next = current->next->next;
delete temp;
} else {
current = current->next;
}
}
return head;
}
2.删除指定位置的节点
void deleteNode(ListNode* node) {
// 假设node不是尾节点
node->val = node->next->val;
ListNode* temp = node->next;
node->next = node->next->next;
delete temp;
}
哨兵节点(sentinel/dummy node)
if (head == nullptr) { ... }
if (pos == head) { ... }
if (head->data = val) { ... }
这些判断有几个共同点
- 逻辑分叉多
- 易错（边界条件）
- 代码重复
- 插入/删除要“特判头节点”
因此哨兵节点的目标只有一个：让头节点变成普通节点
哨兵节点 = 永远存在的“假节点”，不存放有效数据
[sentinel] -> [data1] -> [data2] -> nullptr
sentinel不算链表元素sentinel->next才是真正的第一个节点- 链表永远非空（至少有哨兵）
产生变化
结构变化
head -> [data|next] -> [data|next] -> [data|next] -> null
传统单链表head指向第一个有效节点或nullptr，若有哨兵节点，永远指向哨兵节点
初始化
head = new Node<T>(T{});
head->next = nullptr;
T{}：C++11 列表初始化语法（brace-init），表示用类型T的默认值来构造一个对象
判空
bool isEmpty() const {
return head->next == nullptr;
}
头节点特判不复存在，退化为普通节点处理
哨兵节点在工程实践中是一种强烈推荐的做法，广泛应用于Linux内核/STL/各种容器中
Double LinkedList
节点结构
[prev|data|next]
prev：指向前一个节点的地址data：实际存储的数据next：指向后一个节点的地址
链表结构
NULL <-> [data|next] <-> [data|next] <-> [data|next] <-> NULL
双向的好处
单向链表有一个致命缺陷：无法O(1)从当前节点回到前一个节点
只能沿着next的方向遍历，想要倒退需要重新遍历
双向链表解决了这个问题，任意节点都能O(1)前进/后退
即用空间换时间
这直接带来了几个重要能力
- 删除当前节点不需要“前驱节点”
- 支持双向遍历
- 非常适合LRU/Undo/双端操作
核心操作
插入节点（中间插入）
假设结构
A <-> B <-> C
要在B和C之间插入X
需要修改的指针（4个）
X.prev = B
X.next = C
B.next = X
C.prev = X
顺序很重要，错一个就断链
删除节点
删除节点B
A <-> B <-> C
操作
A.next = C
C.prev = A
不需要从head找前驱，O(1), 这正是双向链表存在的核心理由之一
遍历
正向遍历
for (node = head; node != null; node = node.next)
反向遍历
for (node = tail; node != null; node = node.prev)
时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 随机访问 | O(n) |
| 头部插入 | O(1) |
| 中间插入 | O(1) |
| 删除节点 | O(1) |
哨兵节点对比
哨兵节点通过引入一个（或多个）永远存在的特殊节点，将链表在头尾处的边界情况统一为普通节点，从而消除插入和删除时对nullptr的分支判断
循环哨兵节点进一步通过将头尾连接成环，把“前边界”和“后边界”合并为同一个哨兵节点，使所有节点在结构上完全等价
| 类型 | 结构示意 | 空链表状态 |
|---|---|---|
| No Sentinel | nullptr <- A <-> B <-> C -> nullptr | head = nullptr, tail = nullptr |
| Normal Sentinel | [HEAD] <-> A <-> B <-> C <-> [TAIL] | HEAD.next = TAIL, TAIL.prev = HEAD |
| Circular Sentinel | [SENTINEL] <-> A <-> B <-> C <-> [SENTINEL] | sentinel.next = sentinel.prev = sentinel |
边界处理对比
| 操作 | No Sentinel | Normal Sentinel | Circular Sentinel |
|---|---|---|---|
| 插入头 | 要判断 head 是否为空 | 直接插在 head 后，无需判断 | 直接插在 sentinel 后，无需判断 |
| 插入尾 | 要判断 tail 是否为空 | 直接插在 tail 前，无需判断 | 直接插在 sentinel 前，无需判断 |
| 删除头 | 要判断 head 是否为空 | 直接删除 node，无需判断 | 直接删除 node，无需判断 |
| 删除尾 | 要判断 tail 是否为空 | 同上 | 同上 |
| 空链表判断 | head == nullptr | head->next == tail | sentinel.next == sentinel |
节点数量与存储开销
| 类型 | 每条链表额外节点 |
|---|---|
| No Sentinel | 0 |
| Normal Sentinel | 2（head & tail） |
| Circular Sentinel | 1（sentinel） |
操作复杂度对比
| 操作 | No Sentinel | Normal Sentinel | Circular Sentinel |
|---|---|---|---|
| push_front/back | O(1) | O(1) | O(1) |
| remove | 需要判断 prev/next 是否 nullptr | 不需判断 | 不需判断 |
| empty | O(1) | O(1) | O(1) |
安全性对比
| 类型 | UB / 崩溃风险 | 指针错误概率 |
|---|---|---|
| No Sentinel | 边界判断少写就 UB | 高 |
| Normal Sentinel | sentinel 管控了头尾 | 中 |
| Circular Sentinel | sentinel + 循环保证安全 | 低 |
循环哨兵节点是工业级链表的首选，如Linuxlist_head, STL内部_List_node_base
Circular LinkedList
循环链表是最后一个节点指向头节点的链表
从任意节点出发，都能转一圈回到自己
单向循环链表
┌──────────┐
v │
[A]->[B]-> [C]
head tail
tail->next = head
设计理念
tailbase （推荐）
因为是next 单链表tail永远是最后一个节点tail->next永远是头节点
这是工程中常见的做法
headbase
head永远指向头节点
尾节点的next == head
如果不关心尾插，只需要从头遍历，从头取元素，可以这样写
但工程中几乎永远不会这样做
| 操作 | head base | tail base |
|---|---|---|
| 头插 | O(1) | O(1) |
| 尾插 | O(n) | O(1) |
| 删除头 | O(n) 要找尾 | O(1) |
| 删除尾 | O(n) | O(n) |
| 任意插入 | O(n) | O(n) |
| 遍历 | 一样 | 一样 |
简而言之，tail能很快找到head，head找tail需要遍历
双向循环链表
↖─────────────↗
head ↔ [A] ↔ [B] ↔ [C]
head->prev = tailtail->next = head
链表相关算法
- 链表反转（Reverse Linked List）
- 快慢指针（Floyd思想）
- 删除倒数第N各节点
- 合并两个有序链表
- 判断链表是否回文
- 两两交换节点（Swap Nodes in Pairs）
- K个一组反转链表
- LRU Cache（链表 + 哈希表）
- 侵入式链表（Intrusive List）
- 空闲链表（Free List）
- 链表排序
- 链表相交判断
- 判断链表是否有环