企业官网建设流程全解析

前言

双向链表（doubly linked list）的每个结点除了指向后继的next，还有指向前驱的prev。多一个指针带来的好处是：可以在 O(1) 时间内从任意结点向前或向后移动，删除某个结点时也不需要先找它的前驱。代价是每个结点多占一个指针的空间，插入和删除时要多维护一组指针。

手写双向链表最容易错的地方不是算法，而是指针操作的顺序：先改哪条、后改哪条，稍有不慎就会断链、成环，或者留下悬垂指针。另一个常见问题是头尾结点的特殊处理——如果不用哨兵结点，插入到空链表、删除第一个结点、删除最后一个结点都要写单独的if，代码很快变得难以维护。

本文用「循环哨兵」（circular sentinel）实现一个双向链表，把头部和尾部合并成同一种情况，然后依次实现增、删、查、改。代码以 C++17 为基准。

一、哨兵结点与循环结构

哨兵（sentinel）是一个不存实际数据的结点，它的next指向第一个真实结点，prev指向最后一个真实结点。当链表为空时，哨兵的next和prev都指向自己，形成一个长度为 1 的环。

空链表：
head
┌────┐
│ │
└────┘
next/prev 都指向自己

非空链表：
head -> A <-> B <-> C <- head

这样做的好处：

• 
  
• 不需要head == nullptr的特判；空链表也有一个合法的「头」。
• 
  
• 在头部插入、在尾部插入、在任意结点前插入，都可以用同一个insertBefore。
• 
  
• 删除第一个/最后一个结点时，它的前驱和后继总是存在（至少是哨兵），不需要判空。
• 
  

哨兵本身不是链表元素，遍历时以「回到哨兵」为终止条件。

二、结点与类定义

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

class DoublyList {
public:
struct Node {
int val;
Node* prev;
Node* next;
explicit Node(int v) : val(v), prev(nullptr), next(nullptr) {}
};

DoublyList() noexcept {
head_.next = &head_;
head_.prev = &head_;
}

~DoublyList() { clear(); }

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

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

bool insertAt(std::size_t index, int v);
Node* find(int v);
bool erase(int v);
bool eraseAt(std::size_t index);
bool set(std::size_t index, int v);
std::size_t size() const;
void clear() noexcept;
void print() const;

private:
Node* insertBefore(Node* pos, int v) {
Node* node = new Node(v);
node->prev = pos->prev;
node->next = pos;
pos->prev->next = node;
pos->prev = node;
return node;
}

Node* nodeAt(std::size_t index) {
Node* p = head_.next;
for (std::size_t i = 0; i < index && p != &head_; ++i) {
p = p->next;
}
return (p == &head_) ? nullptr : p;
}

static void unlink(Node* p) noexcept {
p->prev->next = p->next;
p->next->prev = p->prev;
}

Node head_{0};
};

head_{0}用0初始化哨兵的值；这个值不会被读取，只是为了让Node的构造函数能跑起来。构造函数里把next、prev都指向自己，形成空环。

拷贝构造和拷贝赋值被删除。原因是默认的逐成员拷贝只会复制head_的指针值，副本的head_.next仍指向原链表的结点，析构时会重复释放。如果确实需要拷贝，必须写深拷贝：遍历原链表，对每个值调用push_back。

三、插入：增

insertBefore(pos, v)是唯一的核心插入操作，它在pos之前插入一个新结点：

假设：pos->prev 是 P，pos 是 Q
目标：P <-> node <-> Q

node->prev = P;
node->next = Q;
P->next = node;
Q->prev = node;

四条赋值缺一不可。顺序上，前两条先建立node自己的指针，后两条再让邻居指向node；如果先改P->next，而node的指针还没设好，中间状态就会断链（虽然在单线程里不会有人观察，但保持「先设置新结点、再接入链表」的顺序是好习惯）。

基于insertBefore，三个插入接口都很短：

• 
  
• push_front(v)：在第一个真实结点（head_.next）前插入。空链表时head_.next == &head_，等价于在哨兵前插入，结果正确。
• 
  
• push_back(v)：在哨兵前插入。哨兵的prev是最后一个结点，所以新结点成为新的最后一个。
• 
  
• insertAt(index, v)：找到下标为index的结点，在它前面插入；index == size()时追加到末尾。
• 
  

// 适用于 C++17
bool DoublyList::insertAt(std::size_t index, int v) {
if (index == size()) {
push_back(v);
return true;
}
Node* pos = nodeAt(index);
if (pos == nullptr) return false;
insertBefore(pos, v);
return true;
}

nodeAt(index)返回下标为index的结点；如果index >= size()，返回nullptr。insertAt先处理index == size()的追加情况，再处理越界。

四、删除：删

删除一个结点分两步：先从链表里摘下来（unlink），再delete。

// 适用于 C++17
bool DoublyList::erase(int v) {
Node* p = find(v);
if (p == nullptr) return false;
unlink(p);
delete p;
return true;
}

bool DoublyList::eraseAt(std::size_t index) {
Node* p = nodeAt(index);
if (p == nullptr) return false;
unlink(p);
delete p;
return true;
}

unlink只改邻居的指针，不释放内存：

P <-> p <-> N
P->next = N;
N->prev = P;

因为哨兵的存在，p->prev和p->next永远非空：即使p是第一个结点，p->prev也是哨兵；即使p是最后一个，p->next也是哨兵。所以unlink不需要任何空指针判断。

erase(v)只删除第一个匹配的结点。如果要删除所有等于v的结点，需要循环：

// 适用于 C++17
std::size_t DoublyList::eraseAll(int v) {
std::size_t removed = 0;
Node* p = head_.next;
while (p != &head_) {
Node* next = p->next; // 先保存 next，delete 后不能再读 p
if (p->val == v) {
unlink(p);
delete p;
++removed;
}
p = next;
}
return removed;
}

这里必须在delete p之前保存p->next。如果写成delete p; p = p->next;，就是释放后使用（use-after-free），属于未定义行为（undefined behavior, UB）。

clear()可以用同样的模式：

// 适用于 C++17
void DoublyList::clear() noexcept {
Node* p = head_.next;
while (p != &head_) {
Node* next = p->next;
delete p;
p = next;
}
head_.next = &head_;
head_.prev = &head_;
}

最后两行把哨兵重新指向自己，恢复空环状态。如果只删结点不重置head_.prev，它会指向已释放的内存，后续push_back会访问悬垂指针。

五、查找与修改：查、改

查找就是从head_.next开始顺序遍历，直到回到哨兵：

// 适用于 C++17
DoublyList::Node* DoublyList::find(int v) {
for (Node* p = head_.next; p != &head_; p = p->next) {
if (p->val == v) return p;
}
return nullptr;
}

std::size_t DoublyList::size() const {
std::size_t n = 0;
for (const Node* p = head_.next; p != &head_; p = p->next) ++n;
return n;
}

修改可以通过下标或通过find返回的结点指针：

// 适用于 C++17
bool DoublyList::set(std::size_t index, int v) {
Node* p = nodeAt(index);
if (p == nullptr) return false;
p->val = v;
return true;
}

如果调用方已经持有Node*，可以直接p->val = v;。这也是双向链表相对于std::vector的一个特点：结点地址在插入/删除其他结点时保持不变（除非该结点本身被删除），可以长期保存指针。但要小心：结点被删除后，保存的指针就悬垂了。

六、完整示例

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

class DoublyList {
public:
struct Node {
int val;
Node* prev;
Node* next;
explicit Node(int v) : val(v), prev(nullptr), next(nullptr) {}
};

DoublyList() noexcept {
head_.next = &head_;
head_.prev = &head_;
}
~DoublyList() { clear(); }
DoublyList(const DoublyList&) = delete;
DoublyList& operator=(const DoublyList&) = delete;

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

bool insertAt(std::size_t index, int v) {
if (index == size()) { push_back(v); return true; }
Node* pos = nodeAt(index);
if (pos == nullptr) return false;
insertBefore(pos, v);
return true;
}

Node* find(int v) {
for (Node* p = head_.next; p != &head_; p = p->next) {
if (p->val == v) return p;
}
return nullptr;
}

bool erase(int v) {
Node* p = find(v);
if (p == nullptr) return false;
unlink(p);
delete p;
return true;
}

bool set(std::size_t index, int v) {
Node* p = nodeAt(index);
if (p == nullptr) return false;
p->val = v;
return true;
}

std::size_t size() const {
std::size_t n = 0;
for (const Node* p = head_.next; p != &head_; p = p->next) ++n;
return n;
}

void clear() noexcept {
Node* p = head_.next;
while (p != &head_) {
Node* next = p->next;
delete p;
p = next;
}
head_.next = &head_;
head_.prev = &head_;
}

void print() const {
for (const Node* p = head_.next; p != &head_; p = p->next) {
std::cout << p->val << ' ';
}
std::cout << "| ";
for (const Node* p = head_.prev; p != &head_; p = p->prev) {
std::cout << p->val << ' ';
}
std::cout << '\n';
}

private:
Node* insertBefore(Node* pos, int v) {
Node* node = new Node(v);
node->prev = pos->prev;
node->next = pos;
pos->prev->next = node;
pos->prev = node;
return node;
}

Node* nodeAt(std::size_t index) {
Node* p = head_.next;
for (std::size_t i = 0; i < index && p != &head_; ++i) p = p->next;
return (p == &head_) ? nullptr : p;
}

static void unlink(Node* p) noexcept {
p->prev->next = p->next;
p->next->prev = p->prev;
}

Node head_{0};
};

int main() {
DoublyList list;
list.push_back(2);
list.push_back(3);
list.push_front(1); // 1 2 3
list.insertAt(3, 4); // 1 2 3 4
list.print(); // 正向 1 2 3 4，反向 4 3 2 1

list.set(1, 20); // 1 20 3 4
list.erase(3); // 1 20 4
list.print();

std::cout << list.size() << '\n';
std::cout << (list.find(20) != nullptr) << '\n';

list.clear();
list.print(); // 空，只剩分隔符
return 0;
}

手工推演push_front(1)：此时链表是2 <-> 3，head_.next指向 2，pos->prev是哨兵；新结点 1 的prev是哨兵、next是 2，哨兵的next改为 1，2 的prev改为 1。结果是head <-> 1 <-> 2 <-> 3 <-> head，正确。

七、复杂度

如果频繁调用size()，可以在类里维护一个std::size_t size_，在插入时加一、删除时减一，把size()降到 O(1)。代价是每次修改都要同步计数，漏改就会不一致。本文为了代码简短没有维护计数。

常见坑点

1. 插入时只改一个方向

❌ 只写pos->prev->next = node; pos->prev = node;，忘了node->prev、node->next。

✅ 四条指针都要设置：node->prev、node->next、前驱->next、pos->prev。

2. 删除时先 delete 再读 next

❌delete p; p = p->next;

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

3. 忘记重置哨兵的 prev

❌clear()只把head_.next指向自己，head_.prev仍指向已释放的结点。

✅ 同时设置head_.next = &head_; head_.prev = &head_;。

4. 用 nullptr 判断链表结束

❌while (p != nullptr)，但哨兵是循环结构，真实结点的next最终指向哨兵，不是nullptr。

✅ 用p != &head_作为终止条件。

5. 删除哨兵

❌erase的实现没有区分真实结点和哨兵，遍历到&head_时把它也删了。

✅ 遍历和删除只处理head_.next到head_.prev之间的真实结点。

6. 拷贝构造使用默认实现

❌DoublyList b = a;，默认拷贝只复制head_的指针，两个对象共享结点。

✅ 删除拷贝，或写深拷贝（遍历原链表逐个push_back）。

7. 保存结点指针后又删除该结点

❌Node* p = list.find(3); list.erase(3); p->val = 4;

✅ 结点被删除后指针悬垂；使用前确认结点仍在链表中。

8. 在遍历中删除当前结点后继续用 p

❌for (Node* p = head_.next; p != &head_; p = p->next) { if (...) { unlink(p); delete p; } }

✅ 先保存next，删除后用保存的指针继续。

总结

双向链表的代码量比单链表多，但有了哨兵之后，头尾的特殊情况都被消除了，插入和删除各自只需要维护四条（或两条）指针。写的时候记住两个顺序：插入时先设置新结点的指针再接入链表，删除时先保存后继再释放当前结点。这两条能避免绝大多数断链和悬垂问题。