单链表这个东西，教材里写得云淡风轻，真正动手写时，十个里崩掉五六个。不是链表本身难，而是指针操作的时序、头结点的角色、C++内存管理的几条纪律，没人愿意掰开讲。这篇就围绕“带头结点”这个细节展开，把设计原因、完整实现、调试思路一次说透。适合刚学完C++类和指针、准备认真写一遍数据结构第一个实验的人，也适合面试前想快速把链表操作重新理一遍的人。代码我会给一个可以直接编译跑的完整类，再告诉你哪些地方容易写错、错的时候长什么样。
1. 项目定位：为什么带头结点值得单独讲
很多人第一次看单链表，会觉得多一个“头结点”纯粹是浪费空间，一个空链表为什么要多存一个节点？这个想法我理解，但实际敲代码之后你会发现，头结点是帮你省掉大量if判断的哨兵。
1.1 头结点的真实作用
先明确概念：头结点是一个真实存在的节点，它有自己的内存空间，只是数据域不存有效数据。头指针指向头结点，头结点的next指向链表第一个真正存数据的节点，这个节点叫首元结点。
带头结点之后，第一个效果是空表和非空表的操作被统一了。没有头结点时，空链表的头指针是nullptr，插入第一个节点要特殊处理；有头结点后，空链表不过是head->next == nullptr，插入操作永远都是“在某个节点的后面插入新节点”，不需要区分是不是第一个。
第二个效果是删除首元结点时不需要动头指针。不带头结点的链表删除第一个节点，你得修改头指针本身，所以函数形参要么用二级指针，要么用引用；带头结点的链表，删除的是head->next，head始终不变，接口就干净很多。
第三个效果是遍历的起点固定。你永远从head->next开始走，判断是否走到链表尾部，只需要看当前节点是不是nullptr。所有操作的代码路径高度一致，边界条件少，写起来就不容易漏。
1.2 带头结点与不带头结点的对比
我整理了一张表，方便你把两种方案的差异一眼看穿。
| 对比项 | 带头结点 | 不带头结点 |
|---|---|---|
| 空表状态 | head 指向头结点，head->next 为 nullptr | head 为 nullptr |
| 插入首元结点 | 在 head 后插入，逻辑与普通插入一致 | 需要修改头指针，必须用二级指针或引用 |
| 删除首元结点 | 删除 head->next，head 不变 | 需要修改头指针 |
| 遍历起点 | head->next | head |
| 节点数量 | 多一个哨兵节点，空间多一个指针加数据域 | 无额外节点 |
| 代码统一性 | 高，边界条件少 | 低，首节点和尾节点要单独处理 |
空间上多一个节点，几乎可以忽略；时间效率上，插入和删除都是O(1)（给定前驱节点的情况下），查找是O(n)，头结点带来的额外遍历只有“跳过它”这一步，也是常数时间。这个代价换来的是代码复杂度的下降，绝对值。
1.3 什么时候选带头结点
我个人接触的项目和作业里，九成以上都推荐带头结点。尤其是你要把链表封装成一个类、对外提供接口的时候，头结点能让你省掉大量防御性判断。比如插入位置是0，那就是在头结点后面插，代码路径和插入位置是3没有任何区别。
不带头结点也有它的适用场景。比如你只是想临时用std::forward_list解决的问题，或者你明确知道链表一定非空、且不会在头部操作，那少一个节点反而更紧凑。但这类场景在C++里通常直接用STL容器，自己手写链表的机会本来就不多。真正手写时，请无脑带头结点。
2. 设计思路与结构拆分
这个项目的核心设计只有三块：节点的定义、链表类的封装、接口的约定。想清楚这三块，后面的代码就是体力活。
2.1 节点结构：指针成员到底放什么
节点本身是一个结构体，里面有一个数据域和一个指针域。数据域先用int演示，后面想看模板化我也会有。
struct Node { int data; Node* next; Node(const int& value = 0, Node* nxt = nullptr) : data(value), next(nxt) {} };这个构造函数非常关键。它意味着你在写new Node(5)时，next已经被赋值成nullptr。如果省掉这个默认值，你很容易写出Node* n = new Node; n->next = 随机地址;这种野指针操作。C++里局部指针变量不初始化就是随机值，直接解引用必崩。
2.2 类的封装与三大件
节点有了，接下来是链表类。类的成员只需要两个：头指针head和一个长度记录size_。有人会问，不是带头结点吗，怎么还要一个size_？链表长度理论上可以遍历得到，但每次求长度都O(n)，很多接口需要判断位置是否合法，有一个size_就能在O(1)时间拒绝非法输入。
C++的类里面，最绕不开的就是构造函数、析构函数、拷贝构造和赋值运算符。链表的节点都是new出来的，默认的浅拷贝会让两个链表对象的head指向同一串节点，析构时双重删除直接崩溃。所以必须自己写深拷贝。
我的习惯是写一个clear()私有方法，负责释放所有节点，然后在析构函数和赋值运算符里复用。拷贝构造单独写，参数是另一个链表对象，遍历对方的节点依次尾插。
赋值运算符用copy-and-swap写法最稳妥，传参会先拷贝一份临时对象，再和当前对象交换成员。这样如果拷贝过程抛异常，当前对象还是完整的。
2.3 接口清单与约定
对外接口我建议这样设计：
bool insert(int pos, const int& val)：在位置pos插入，返回是否成功bool remove(int pos)：删除位置pos的节点，返回是否成功bool get(int pos, int& out)：读取位置pos的值int find(const int& val)：查找第一个匹配的值，返回下标void print() const：打印整个链表int size() const：返回节点个数void reverse()：反转链表void clear()：清空所有有效节点
位置从0开始，还是从1开始，这是一个约定问题。0基在程序里更顺，因为插入位置pos的含义是“新节点将成为下标pos的节点”，删除位置pos的含义是“删除当前下标pos的节点”。这个约定要和注释写清楚，否则使用者会晕。
非法输入的处理逻辑也很重要。插入位置pos要求0 <= pos <= size_，因为允许在链表尾部插入；删除位置要求0 <= pos < size_。读位置和要求同样是pos < size_。所有返回bool的接口都要保证失败时链表状态不变。
3. 核心操作实现与指针顺序
这一节是整个项目的精髓。链表代码写错百分之八十是指针连接顺序错，剩下的是忘了改size_或忘了释放内存。下面每个操作我都会把关键逻辑和背后原因写出来。
3.1 初始化与销毁：new和delete如何对应
构造函数很简单：
LinkedList() { head = new Node(); size_ = 0; }这里new Node()走的是默认参数，data是0，next是nullptr。头结点的数据域不参与业务逻辑。
析构函数要做的第一件事是清空所有有效节点，然后删除头结点。很多人只删除头结点，头结点后面的节点就泄漏了；还有人循环里删除头结点，后面就找不到了。正确写法：
~LinkedList() { clear(); delete head; } void clear() { Node* p = head->next; while (p != nullptr) { Node* tmp = p->next; delete p; p = tmp; } head->next = nullptr; size_ = 0; }clear里必须用一个临时变量tmp先保存p->next，再delete p。因为delete p之后，p指向的内存已经释放，此时访问p->next就是访问已释放内存，属于未定义行为，可能当场崩，也可能数据被改成乱七八糟的值。
这里的对应关系是：一个new配一个delete，不多不少。主要作用是把所有new出来的节点全部正常还掉，保证进程不会因为泄漏被系统压垮。
3.2 插入：先把新节点接好，再改前驱
插入分为头插、尾插、按位置插。按位置插写好了，头插和尾插都是它的特例。
bool insert(int pos, const int& val) { if (pos < 0 || pos > size_) { return false; } Node* prev = head; for (int i = 0; i < pos; ++i) { prev = prev->next; } Node* newNode = new Node(val, prev->next); prev->next = newNode; ++size_; return true; }核心是把prev走到待插入位置的前一个节点。插入位置是0，prev停在head，新节点插到头结点后面；插入位置是size_，prev停在最后一个节点，新节点接在尾部。这就是头结点的价值，不用为“头部插入”单独写逻辑。
指针操作的顺序是唯一的坑：先构造新节点并把它的next指向prev->next，再修改prev->next指向新节点。如果顺序反过来，先修改prev->next，再想取原来的后继就找不到了，链表就断掉了。
3.3 删除：先保存被删节点，再改链接
删除比插入多一步释放内存。
bool remove(int pos) { if (pos < 0 || pos >= size_) { return false; } Node* prev = head; for (int i = 0; i < pos; ++i) { prev = prev->next; } Node* del = prev->next; prev->next = del->next; delete del; --size_; return true; }同样先把prev走到待删除节点的前驱，然后del保存要删的那个节点。改链时，把prev->next直接指向del->next，跳过了del。最后delete del把内存释放。
这里最容易犯的错误是顺序反掉。先delete del再把prev->next = del->next，del->next已经是非法访问，属于典型的悬垂指针问题。还有一种错误是忘记保存del，直接prev->next = prev->next->next; delete prev->next;，这时候删的已经是后一个节点了，链也断了。
3.4 遍历与查找：判断条件是p还是p->next
遍历的核心是next成员和循环条件。打印和查找都用同一套模式：
void print() const { Node* p = head->next; while (p != nullptr) { std::cout << p->data << " "; p = p->next; } std::cout << std::endl; } int find(const int& val) const { Node* p = head->next; int index = 0; while (p != nullptr) { if (p->data == val) { return index; } p = p->next; ++index; } return -1; }很多人纠结为什么不是while (p->next != nullptr)。你可以这样想：当p指向最后一个有效节点时，p->next是nullptr，如果用p->next判断，循环体就不会执行，最后一个节点就丢了。更稳的做法是养成习惯，只要操作的是“当前节点”，判断条件就用p != nullptr。只有在一个操作需要访问p->next并且要求p->next存在时，才需要额外的判断。
3.5 反转：三指针法的顺序坑
反转链表的本质是让每个节点的next指向它的前驱，原来的头变尾，原来的尾变头。但不能边遍历边改，因为改了当前节点的next之后，原来的下一个节点就找不到了。所以需要三个指针：prev、cur、nxt。
void reverse() { Node* prev = nullptr; Node* cur = head->next; while (cur != nullptr) { Node* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } head->next = prev; }关键在循环体内三行的顺序：先保存nxt，再让cur->next指向prev，然后prev移到cur，cur移到nxt。如果先执行cur = cur->next，再执行cur->next = prev，此时当前位置已经变了，反转就错位了。
循环结束后，prev指向原链表最后一个节点，也就是反转后的首元结点，把它接到head->next上，反转完成。头结点本身不需要动，它依然在链表最前面。
4. 实操过程：完整代码与用例
纸上谈兵没有用，我直接给一份能编译运行的完整实现。这份代码包含前面讲的多数接口，并且加入了模板化改造，你可以直接把int换成自己的数据类型。
4.1 完整可运行代码
#include <iostream> template <typename T> class LinkedList { private: struct Node { T data; Node* next; Node(const T& value = T(), Node* nxt = nullptr) : data(value), next(nxt) {} }; Node* head; int size_; public: LinkedList() : head(new Node()), size_(0) {} ~LinkedList() { clear(); delete head; } LinkedList(const LinkedList& other) : head(new Node()), size_(0) { Node* p = other.head->next; Node* tail = head; while (p != nullptr) { tail->next = new Node(p->data); tail = tail->next; p = p->next; } size_ = other.size_; } LinkedList& operator=(LinkedList other) { std::swap(head, other.head); std::swap(size_, other.size_); return *this; } void clear() { Node* p = head->next; while (p != nullptr) { Node* tmp = p->next; delete p; p = tmp; } head->next = nullptr; size_ = 0; } bool insert(int pos, const T& val) { if (pos < 0 || pos > size_) return false; Node* prev = head; for (int i = 0; i < pos; ++i) prev = prev->next; Node* newNode = new Node(val, prev->next); prev->next = newNode; ++size_; return true; } bool remove(int pos) { if (pos < 0 || pos >= size_) return false; Node* prev = head; for (int i = 0; i < pos; ++i) prev = prev->next; Node* del = prev->next; prev->next = del->next; delete del; --size_; return true; } bool get(int pos, T& out) const { if (pos < 0 || pos >= size_) return false; Node* p = head->next; for (int i = 0; i < pos; ++i) p = p->next; out = p->data; return true; } int find(const T& val) const { Node* p = head->next; int index = 0; while (p != nullptr) { if (p->data == val) return index; p = p->next; ++index; } return -1; } void reverse() { Node* prev = nullptr; Node* cur = head->next; while (cur != nullptr) { Node* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } head->next = prev; } void print() const { Node* p = head->next; while (p != nullptr) { std::cout << p->data << " "; p = p->next; } std::cout << std::endl; } int size() const { return size_; } };这里有几个细节值得说。模板化之后，节点构造函数里的初始值T()是类型T的默认构造值，对int就是0，对string就是空字符串。size_用int而不是size_t，是方便返回-1之类的错误值，实际项目里你可以用ssize_t或更大范围的无符号类型，但教学演示用int更直观。
拷贝构造中使用了尾插法，通过不断追加新节点完成深拷贝。赋值运算符使用了copy-and-swap，参数传值天然生成一次拷贝，然后交换成员，旧对象在临时变量析构时自动释放。这种写法简单又安全。
4.2 测试用例设计
写完代码一定要测。我建议按下面这个顺序做用例，每一类都能覆盖一类边界条件。
| 用例场景 | 操作序列 | 期望输出 |
|---|---|---|
| 空表插入 | insert(0, 10) | 0: 10 |
| 头部插入 | insert(0, 20) | 0: 20 10 |
| 尾部插入 | insert(2, 30) | 0: 20 10 30 |
| 中间插入 | insert(1, 40) | 0: 20 40 10 30 |
| 非法插入 | insert(5, 50) | false，链表不变 |
| 删除头节点 | remove(0) | 0: 40 10 30 |
| 删除尾节点 | remove(2) | 0: 40 10 |
| 非法删除 | remove(5) | false，链表不变 |
| 反转 | reverse() | 0: 10 40 |
| 查找 | find(10) | 1 |
| 拷贝构造 | 用当前对象构造新对象，再删除原对象 | 新对象不受影响 |
实际操作中，每个用例之间要重新初始化一个链表，或者把size()打印出来对照。尤其是反转后，再执行插入和删除，验证整个链表结构没有被破坏。
4.3 从int到泛型以及STL视角
完整代码里我直接给了模板版本。如果从int换成T，需要改的地方只有节点里的data类型、构造函数参数、所有接口签名里的int改成const T&。类的使用者指定的类型必须支持拷贝和赋值，否则链表类无法正常工作。
如果你对STL的内部实现感兴趣，std::list是双向链表，同样带头结点。头结点在那里叫哨兵节点，用来统一空表和非空表操作，迭代器的end()就落在头结点上。理解了这里的手写链表，你再看STL的list源码，会发现设计上有很多相通之处。
5. 常见问题与排查技巧
链表写多了，报错就那么几种。我把自己和身边人踩过的坑集中列出来，配上定位方法，这一部分是纯经验。
5.1 段错误和野指针的定位思路
最常见的崩溃是Segmentation fault。原因十有八九是访问了空指针或已释放内存。
我调试的时候一般先看崩溃位置的代码，如果是p->data这类，马上问自己：p是从哪里来的？如果p是prev->next，那prev有没有可能是nullptr？插入和删除里，prev的循环次数是pos，如果pos过大，prev会走到链表尾部之后变成nullptr，再访问prev->next就崩了。这就是为什么必须在入口处校验pos的范围。
另一个隐蔽的坑是双重删除。两个链表对象共享节点，析构时第一个对象删除节点，第二个对象再删就是未定义行为。解决方法就是深拷贝，或者退一步用智能指针管理节点。
5.2 内存泄漏与悬垂指针
内存泄漏不会让你程序立刻崩，但会让内存占用一路涨。我排查链表泄漏时倾向于用编译器的地址消毒器。GCC和Clang可以在编译时加-fsanitize=address，然后程序退出时，如果有没有释放的内存，它会直接报出来。
g++ -fsanitize=address -g test.cpp -o test ./test比如clear()里忘记把head->next置空，析构走出后，head的后面所有节点都会泄漏。ASAN会把泄漏点的调用栈打出来，一眼就能看到是哪个函数没配对new和delete。
5.3 面试常见变形题思路
带头结点单链表的题目，面试里出现频率很高。给你几种变形的通用思路。
- 找中间节点：快慢指针，一个走一步，一个走两步，快的到末尾时慢的就在中间。
- 判断是否有环：同样快慢指针，如果两个指针能相遇，就说明有环。
- 找倒数第k个：先让快指针走k步，然后快慢一起走，快的到末尾，慢的就是倒数第k个。
- 反转区间：先找到区间的前驱，再对该区间做局部反转，最后接回来。
这些题本质上都是对指针移动和边界条件的考察。带头结点的好处是，处理这些题目时你不用额外考虑空表、第一个节点这些特殊情况。
5.4 经验清单
下面这些是我反复踩过坑之后总结的检查项，写链表时一条条过一遍。
- 插入前检查
pos范围，pos == size_是合法的尾插。 - 删除前检查
pos范围，pos == size_是非法的。 - 修改
next之前，先确认原来的后继被保存，或已无需要。 - 删除节点一定要先保存待删节点，再改链接，再
delete。 - 遍历一律从
head->next开始，判断条件用p != nullptr。 size_在每次成功插入、删除后同步更新，别在返回时才想起来。- 拷贝构造和赋值运算符必须深拷贝，拒绝默认浅拷贝。
- 析构函数必须
clear()之后delete head，顺序不能反。 - 头结点的
next是nullptr，代表空链表，不带头结点才需要判断head == nullptr。 - 如果程序崩了，先检查有没有访问空指针，再检查双重删除，再查越界。
最后分享一个我自己的习惯。写链表时，在纸上把每个节点的next画出来，然后手动模拟一遍插入和删除的过程，看指针指向哪里。手画一遍能省下调试半小时。尤其是反转链表，刷三遍还总会有人卡在cur->next = prev之后丢了nxt，就是因为没有用临时变量保存。你把这个点记住了，链表基本就不会再出大问题。
