企业官网建设流程全解析

前言

双向循环链表是把每个节点的前驱和后继都串起来，并让尾节点的后继指回头节点、头节点的前驱指向尾节点，形成一个没有「尽头」的环。它比单链表多一个前驱指针，换来的是「已知节点即可 O(1) 删除」和「从任意位置双向遍历」；比普通双向链表多一个环，换来的是「头尾操作对称」，不必为边界单独写分支。

学习和使用它时有三个典型误解。第一是认为循环链表必须判断p->next == head才算结束，于是一遇到空表就出错——空表时head->next就是head自己。第二是以为「有环」意味着遍历一定会死循环，实际上只要结束条件写对，环形结构反而消除了大量空指针判断。第三是把std::list当成「就是双向循环链表所以不用手写」，但标准并不规定std::list的内部结构，把它当作教学模型来理解指针操作是可以的，把它当作实现细节来依赖则不行。

本文手写一个带哨兵节点的双向循环链表，讲清楚插入和删除时的指针顺序、空表与单元素表的边界，最后讨论它与std::list的取舍。代码以 C++17 为基准。

一、哨兵节点：把边界情况消掉

不带哨兵的链表要区分「插入到空表」「插入到头」「插入到尾」「插入到中间」四种情况，删除时还要单独判断被删的是不是头节点。这些分支是链表代码出错的主要来源。

哨兵（sentinel）的做法是：额外分配一个不存数据的节点head_，让它的next指向第一个真实节点，prev指向最后一个真实节点；第一个真实节点的prev指向head_，最后一个真实节点的next也指向head_。这样整个结构永远是一个环，head_既是「头之前的节点」，也是「尾之后的节点」。

有了哨兵，空表的表示就是head_.next == &head_，并且head_.prev == &head_；只有一个元素时，head_.next和head_.prev都指向那个元素。所有插入操作都可以统一描述成「在某个节点之前插入」，所有删除操作都可以统一描述成「把某个节点的前驱和后继直接连起来」，不需要任何针对头尾的特殊分支。

判断遍历结束的条件也从「直到空指针」变成了「直到回到哨兵」：

for (Node* p = head_.next; p != &head_; p = p->next)

这条循环对空表是安全的：初始时p就是&head_，条件立即为假，循环体一次都不执行。

二、插入与删除的指针顺序

指针操作最常见的错误是「先断开、后连接」，导致后续语句访问已经丢失的节点。正确的原则是：先让新节点记住它的邻居，再让邻居认识新节点。

在pos之前插入新节点n，涉及四条指针赋值：

n->prev = pos->prev
n->next = pos
pos->prev->next = n
pos->prev = n

前两条只写n自己的成员，不影响链表；第三条让原来的前驱指向n；第四条让pos指回n。如果先执行第四条，pos->prev就变成了n，再执行第三条时pos->prev->next实际改的是n->next，原前驱就永远指向不了新节点，链表断裂。

删除节点n只有两条语句：

n->prev->next = n->next
n->next->prev = n->prev

这两条的顺序无所谓，因为它们操作的是n的邻居，与n自身无关；但必须在delete n之前完成。先delete再改指针，等于在对象生命周期结束后访问它，是未定义行为（undefined behavior, UB），可能看起来正常，也可能在开启优化后崩溃。

还有一个容易忽略的点：删除时如果只做了第一条、忘了第二条，正向遍历仍然正常，但反向遍历会踩到已释放的内存。这类错误在单向测试里很难发现，必须两个方向都验一遍。

三、完整实现

下面这个类用哨兵组织整个环，并提供头插、尾插、按值删除、正向打印和反向打印。拷贝构造与拷贝赋值被显式删除，避免默认的浅拷贝造成两个对象共享同一批节点、析构时重复释放。

// 适用于 C++17
#include <cstddef>
#include <iostream>

class IntList {
private:
struct Node {
int value;
Node* prev;
Node* next;
};

public:
IntList() {
head_.next = &head_;
head_.prev = &head_;
}

~IntList() { clear(); }

IntList(const IntList&) = delete;
IntList& operator=(const IntList&) = delete;

void push_back(int v) { insert_before(&head_, v); }
void push_front(int v) { insert_before(head_.next, v); }

// 删除第一个值为 v 的节点，返回是否删除成功
bool remove_value(int v) {
for (Node* p = head_.next; p != &head_; p = p->next) {
if (p->value == v) {
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
--size_;
return true;
}
}
return false;
}

void clear() {
Node* p = head_.next;
while (p != &head_) {
Node* next = p->next; // 先保存后继，再释放当前节点
delete p;
p = next;
}
head_.next = &head_;
head_.prev = &head_;
size_ = 0;
}

std::size_t size() const { return size_; }
bool empty() const { return head_.next == &head_; }

void print_forward() const {
for (const Node* p = head_.next; p != &head_; p = p->next) {
std::cout << p->value << ' ';
}
std::cout << '\n';
}

void print_backward() const {
for (const Node* p = head_.prev; p != &head_; p = p->prev) {
std::cout << p->value << ' ';
}
std::cout << '\n';
}

private:
// 在 pos 之前插入；pos 可以是哨兵，表示插到尾部
void insert_before(Node* pos, int v) {
Node* n = new Node{v, pos->prev, pos};
pos->prev->next = n;
pos->prev = n;
++size_;
}

Node head_{0, nullptr, nullptr}; // 哨兵，value 不参与语义
std::size_t size_ = 0;
};

int main() {
IntList list;
list.push_back(2);
list.push_back(3);
list.push_front(1);
list.push_back(4);

list.print_forward(); // 应当是 1 2 3 4
list.print_backward(); // 应当是 4 3 2 1

list.remove_value(3);
list.print_forward(); // 应当是 1 2 4
std::cout << list.size() << '\n';
return 0;
}

Node head_{0, nullptr, nullptr};这一行依赖聚合初始化：Node是聚合类型，三个成员按顺序赋值。构造函数的函数体随后把两个指针改成指向自己，完成闭环。这里不能在类内直接写head_{0, &head_, &head_}，因为成员初始化器里this指向的对象还没构造完，而且&head_在类定义阶段并不是常量表达式。

insert_before用new分配节点，异常安全性只能算「基本保证」：如果new抛出std::bad_alloc，链表保持原状，不会泄漏。但如果在insert_before之后的++size_之前发生异常（实际不会），计数就会不一致，所以把不抛异常的语句放在最后是良好的习惯。

四、与 std::list 的取舍

标准库的std::list就是一个双向链表，支持 O(1) 的splice、push_front、erase，并且保证插入和删除不会让其他元素的迭代器失效。绝大多数场景下直接用std::list就够了，没有必要手写。

手写的价值主要在三个地方。第一是教学：理解指针怎么连、边界怎么处理，是后续看懂侵入式链表、LRU 缓存、内核链表的前提。第二是侵入式设计：当对象本身需要同时挂在多条链表上时，标准容器要求对象被容器拥有，而侵入式链表把prev、next放进对象内部，一个对象可以同时属于多个链表，不需要额外分配节点。第三是内存布局可控：在嵌入式或对分配次数敏感的场景里，可以配合内存池一次性分配。

标准容器的取舍点也要清楚：std::list每个节点独立分配，缓存局部性差，遍历性能通常不如std::vector；它的优势只在「频繁在中间插入删除」且「已经持有迭代器」时成立。如果主要操作是遍历和尾部追加，std::vector往往更快，这一点在选容器时比「链表插入是 O(1)」这句口诀更重要。

常见坑点

坑点一：删除节点时先 delete 再改指针。

❌delete p; p->prev->next = p->next;在对象生命周期结束后访问成员，属于 UB。

✅ 先完成两条指针赋值，最后delete p。

坑点二：遍历的结束条件用空指针。

❌for (Node* p = head_.next; p != nullptr; p = p->next)循环永远不结束。

✅ 结束条件写成p != &head_，哨兵是环的入口也是出口。

坑点三：空表时对head_.next解引用。

❌int v = head_.next->value;空表时head_.next就是&head_，读到的是哨兵里的无效值。

✅ 先判empty()，或者用size()判断。

坑点四：插入时先改pos->prev，再改新节点。

❌ 先执行pos->prev = n;再写n->prev = pos->prev;，此时pos->prev已经是n，新节点的前驱指向自己。

✅ 严格按「新节点先记住邻居，邻居再认识新节点」的顺序。

坑点五：只删除不更新 size，或者更新了 size 却没真正删除。

❌remove_value里--size_写在return true之后，永远执行不到。

✅ 计数与指针操作放在同一个分支里，删除成功后立即递减。

坑点六：使用默认拷贝构造。

❌ 不写拷贝构造，两个对象析构时对同一批节点delete两次。

✅ 删除拷贝构造与拷贝赋值，需要复制时显式实现深拷贝，或提供clone()。

坑点七：清空链表时先 delete 再取 next。

❌delete p; p = p->next;，p->next读的是已释放内存。

✅ 先Node* next = p->next;，再delete p;，最后p = next;。

坑点八：删除节点后继续用指向它的指针遍历。

❌remove_value返回后调用方仍持有旧指针，后续解引用悬垂。

✅ 删除接口不暴露内部指针；需要「删除并继续」时返回下一个节点的指针，且明确文档化其有效性。

总结

双向循环链表的难点从来不是「指针多了一个」，而是「边界被哨兵消掉之后，你是否还清楚地知道每条语句在改谁」。把插入的四条赋值和删除的两条赋值背下来没有意义，能在纸上画出执行每一步之后的环，才是真的掌握了。