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

前言链表是最基础的动态数据结构之一。它用一组不必连续的结点通过指针串成线性序列。相比数组链表在已知位置插入和删除是常数时间代价是不能随机访问而且每个结点都要额外存指针、在内存里跳来跳去缓存局部性差。初学者常见的误解有两个一是把插入删除 O(1)当成任何情况下都比数组快忽略了定位到那个位置本身要 O(n)也忽略了访存模式的影响二是手写链表时只顾着把结点接上忘了释放或者拷贝对象时只复制了头指针导致两个链表共用同一批结点析构时重复释放。本文用单链表讲清结点结构、头插尾插、按值删除、原地反转这几个核心操作并说明所有权和拷贝语义该怎么处理。文末也会提到标准库里的std::forward_list和std::list实际工程里优先用它们。一、结点与链表的结构单链表的结点包含数据域和指向后继的指针。链表对象本身只需要保存头指针和元素个数。// 适用于 C17#include cstddefstruct Node {int value;Node *next;explicit Node(int v) : value(v), next(nullptr) {}};这里刻意用裸指针而不是智能指针是为了把指针操作讲清楚。真实项目里更推荐std::unique_ptrNode表示后继这样析构会自动递归释放但递归析构在链表很长时可能耗尽栈空间这是它自己的坑后面会提。空链表用空指针表示。很多实现会加一个哑结点dummy head让头部的插入删除和其他位置统一处理省掉大量判空分支。本文的删除操作使用二级指针同样能达到统一处理的效果。二、插入头插与尾插头插最简单新结点的next指向当前头然后更新头指针。尾插需要走到末尾。如果每次都从头走连续插入 n 个元素就是 O(n²)。常见优化是额外维护一个尾指针或者在链表对象里保存m_tail。// 适用于 C17class 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本身。一种写法是单独判断头部另一种是用指向指针的指针统一处理。// 适用于 C17bool SinglyList::removeFirst(int v){Node **link m_head;while (*link ! nullptr) {Node *cur *link;if (cur-value v) {*link cur-next; // 让前驱或头指针跳过 curif (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()则是标准的遍历释放// 适用于 C17void 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;}四、原地反转反转单链表是面试高频题核心是三个指针的滚动// 适用于 C17void 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换成声明并写深拷贝// 适用于 C17SinglyList(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_listint单链表或std::listint双向链表更省事它们的拷贝、移动、析构都已经正确处理。六、链表与数组的取舍维度数组 /std::vector链表随机访问O(1)O(n)头部插入删除O(n)O(1)已知位置插入删除O(n) 搬移元素O(1) 改指针内存布局连续缓存友好分散指针跳转多每元素额外开销通常没有至少一个指针迭代器失效扩容时全部失效删除仅影响被删结点复杂度只是渐近描述。元素很少、或者操作集中在尾部时std::vector往往更快因为连续内存的预取和缓存命中率高。链表真正的优势在已经持有位置、频繁在中间插入删除的场景比如 LRU 链表。常见坑点❌ 删除结点后继续用它的nextdelete cur; cur cur-next;✅ 先保存Node *next cur-next;再delete cur。❌ 删除头结点时忘记更新m_head只改了前驱的next。✅ 用二级指针或对头部单独判断。❌ 使用默认拷贝构造两个链表共享结点析构时 double free。✅ 删除拷贝操作或实现深拷贝。❌ 析构函数为空链表所有结点泄漏。✅clear()中逐个delete并把头尾指针置空。❌ 反转时先改cur-next再想取后继。✅ 严格按存后继、改指针、移 prev、移 cur的顺序。❌for (Node *p head; p-next; p p-next)处理空表时解引用空指针。✅ 循环条件写p ! nullptr需要看后继时再判空。❌ 删除尾结点后m_tail仍指向已释放内存。✅ 删除时同步维护尾指针或置空后延迟重建。❌ 认为链表插入删除一定比vector快。✅ 定位成本、缓存局部性都要算进去小数据量优先用连续容器。总结操作关键点复杂度头插新结点指旧头更新头指针O(1)尾插维护尾指针避免每次遍历O(1)按值删除二级指针统一处理头结点O(n)反转三指针滚动先存后继O(n)清空先存后继再释放O(n)链表的价值在于指针操作本身把它写对等于把所有权、失效、边界这三件事练了一遍。真正写业务代码时优先用标准容器把手写链表留给需要精细控制内存布局或者面试练习的场合。