C++数据结构之链表详解

前言

链表是最基础的动态数据结构之一。它用一组不必连续的结点，通过指针串成线性序列。相比数组，链表在已知位置插入和删除是常数时间，代价是不能随机访问，而且每个结点都要额外存指针、在内存里跳来跳去，缓存局部性差。

初学者常见的误解有两个：一是把"插入删除 O(1)"当成任何情况下都比数组快，忽略了定位到那个位置本身要 O(n)，也忽略了访存模式的影响；二是手写链表时只顾着把结点接上，忘了释放，或者拷贝对象时只复制了头指针，导致两个链表共用同一批结点，析构时重复释放。

本文用单链表讲清结点结构、头插尾插、按值删除、原地反转这几个核心操作，并说明所有权和拷贝语义该怎么处理。文末也会提到标准库里的std::forward_list和std::list，实际工程里优先用它们。

一、结点与链表的结构

单链表的结点包含数据域和指向后继的指针。链表对象本身只需要保存头指针和元素个数。

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

struct Node {
int value;
Node *next;

explicit Node(int v) : value(v), next(nullptr) {}
};

这里刻意用裸指针而不是智能指针，是为了把指针操作讲清楚。真实项目里更推荐std::unique_ptr<Node>表示后继，这样析构会自动递归释放；但递归析构在链表很长时可能耗尽栈空间，这是它自己的坑，后面会提。

空链表用空指针表示。很多实现会加一个"哑结点"（dummy head），让头部的插入删除和其他位置统一处理，省掉大量判空分支。本文的删除操作使用二级指针，同样能达到统一处理的效果。

二、插入：头插与尾插

头插最简单：新结点的next指向当前头，然后更新头指针。

尾插需要走到末尾。如果每次都从头走，连续插入 n 个元素就是 O(n²)。常见优化是额外维护一个尾指针，或者在链表对象里保存m_tail。

// 适用于 C++17
class SinglyList {
public:
SinglyList() = default;
~SinglyList() { clear(); }

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

void pushFront(int v)
{
Node *n = new Node(v);
n->next = m_head;
m_head = n;
++m_size;
}

void pushBack(int v)
{
Node *n = new Node(v);

if (m_head == nullptr) {
m_head = m_tail = n;
} else {
if (m_tail == nullptr) { // 尾结点被删过，重新找回尾
Node *p = m_head;
while (p->next != nullptr) {
p = p->next;
}
m_tail = p;
}
m_tail->next = n;
m_tail = n;
}
++m_size;
}

std::size_t size() const { return m_size; }

void clear(); // 定义见下文
bool removeFirst(int v); // 定义见下文
void reverse(); // 定义见下文

private:
Node *m_head = nullptr;
Node *m_tail = nullptr;
std::size_t m_size = 0;
};

clear、removeFirst、reverse的完整定义放在下几节，写成SinglyList::成员函数。

三、删除与二级指针

按值删除的难点在头结点：如果待删的正好是第一个，必须修改m_head本身。一种写法是单独判断头部，另一种是用"指向指针的指针"统一处理。

// 适用于 C++17
bool SinglyList::removeFirst(int v)
{
Node **link = &m_head;
while (*link != nullptr) {
Node *cur = *link;
if (cur->value == v) {
*link = cur->next; // 让前驱（或头指针）跳过 cur
if (m_tail == cur) {
m_tail = nullptr; // 删的是尾，重新找回新的尾
if (m_head != nullptr) {
Node *p = m_head;
while (p->next != nullptr) {
p = p->next;
}
m_tail = p;
}
}
delete cur;
--m_size;
return true;
}
link = &cur->next;
}
return false;
}

link始终保存"指向当前结点的那个指针"的地址。它可能是&m_head，也可能是前一个结点的next成员的地址。这样删除头结点和删除中间结点走的是同一条路径，不需要特判。

尾指针的处理要小心：如果删掉的正好是尾结点，m_tail就成了悬垂指针。可以在删除后从头走一遍重新找到尾结点（只在删尾时发生，代价 O(n)），也可以先置空、等下一次尾插时再重建。无论哪种，都不能让m_tail继续指向已释放的结点。

clear()则是标准的遍历释放：

// 适用于 C++17
void SinglyList::clear()
{
Node *cur = m_head;
while (cur != nullptr) {
Node *next = cur->next; // 先保存后继，再释放当前
delete cur;
cur = next;
}
m_head = m_tail = nullptr;
m_size = 0;
}

四、原地反转

反转单链表是面试高频题，核心是三个指针的滚动：

// 适用于 C++17
void SinglyList::reverse()
{
Node *prev = nullptr;
Node *cur = m_head;
while (cur != nullptr) {
Node *next = cur->next; // 1. 保存后继，否则改完就找不到了
cur->next = prev; // 2. 反向指
prev = cur; // 3. prev 前移
cur = next; // 4. cur 前移
}
std::swap(m_head, m_tail);
}

循环结束时prev指向原来的尾结点，也就是新的头。cur为空。交换m_head和m_tail之后，尾指针也正确了。

这段代码不分配任何新结点，时间 O(n)，额外空间 O(1)。

五、拷贝语义与所有权

上面的类删除了拷贝构造和拷贝赋值。原因是默认生成的版本只复制指针，两个对象会指向同一串结点：任一对象析构时释放全部结点，另一个对象的头指针立刻悬垂，再次析构就是重复释放，属于 UB。

如果要支持拷贝，就得把上面的= delete换成声明，并写深拷贝：

// 适用于 C++17
SinglyList(const SinglyList &other)
{
Node **tailLink = &m_head;
for (Node *p = other.m_head; p != nullptr; p = p->next) {
*tailLink = new Node(p->value);
m_tail = *tailLink;
tailLink = &(*tailLink)->next;
++m_size;
}
}

这段代码逐结点复制。异常安全方面，如果中途new抛出std::bad_alloc，已经构造的部分会泄漏，因为对象还没构造完成、析构函数不会运行。稳妥做法是先构造一个临时链表再交换，或者用std::unique_ptr管理每个结点。

实际工程里，直接用std::forward_list<int>（单链表）或std::list<int>（双向链表）更省事，它们的拷贝、移动、析构都已经正确处理。

六、链表与数组的取舍

复杂度只是渐近描述。元素很少、或者操作集中在尾部时，std::vector往往更快，因为连续内存的预取和缓存命中率高。链表真正的优势在"已经持有位置、频繁在中间插入删除"的场景，比如 LRU 链表。

常见坑点

1. 
   
2. ❌ 删除结点后继续用它的next：delete cur; cur = cur->next;
3. 
   

✅ 先保存Node *next = cur->next;再delete cur。

1. 
   
2. ❌ 删除头结点时忘记更新m_head，只改了前驱的next。
3. 
   

✅ 用二级指针，或对头部单独判断。

1. 
   
2. ❌ 使用默认拷贝构造，两个链表共享结点，析构时 double free。
3. 
   

✅ 删除拷贝操作，或实现深拷贝。

1. 
   
2. ❌ 析构函数为空，链表所有结点泄漏。
3. 
   

✅clear()中逐个delete，并把头尾指针置空。

1. 
   
2. ❌ 反转时先改cur->next，再想取后继。
3. 
   

✅ 严格按"存后继、改指针、移 prev、移 cur"的顺序。

1. 
   
2. ❌for (Node *p = head; p->next; p = p->next)处理空表时解引用空指针。
3. 
   

✅ 循环条件写p != nullptr，需要看后继时再判空。

1. 
   
2. ❌ 删除尾结点后m_tail仍指向已释放内存。
3. 
   

✅ 删除时同步维护尾指针，或置空后延迟重建。

1. 
   
2. ❌ 认为链表插入删除一定比vector快。
3. 
   

✅ 定位成本、缓存局部性都要算进去；小数据量优先用连续容器。

总结

链表的价值在于指针操作本身：把它写对，等于把"所有权、失效、边界"这三件事练了一遍。真正写业务代码时，优先用标准容器，把手写链表留给需要精细控制内存布局或者面试练习的场合。