来用 C++ 写一个单链表吧！
链表结点
首先，我们定义链表结点 Node：
1template <class EleTy>
2class LinkedList {
3 public:
4 class Node {
5 public:
6 EleTy val;
7 Node* next{nullptr};
8 explicit Node() noexcept(true) {}
9 explicit Node(EleTy val) noexcept(true) : val(val) {}
10 explicit Node(EleTy val, Node* next) noexcept(true)
11 : val(val), next(next) {}
12 };
13}
这里需要注意，对于 POD 类型，尽量设置一个默认值（尤其是关键的字段），从而避免栈上初始化沾染随机数据。
单链表有两个域：值和下一个结点。
链表构造、解构函数
首先需要一个 dummy head （伪头结点），可以帮我们省很多事情。
析构函数调用私有的 dispose 方法，将占据的资源释放。
1 private:
2 // 伪头结点
3 Node dummy;
4
5 // 释放内存
6 void dispose() noexcept(true) {
7 auto llcur = dummy.next;
8 while (llcur) {
9 Node* next = llcur->next;
10 delete llcur;
11 llcur = next;
12 }
13 dummy.next = nullptr;
14 }
15
16 public:
17 // 空构造函数
18 LinkedList() {}
19
20 // 析构函数
21 ~LinkedList() { dispose(); }
支持初始化器列表
为了使用起来更方便，增加初始化器列表：
1 // 用初始值构造
2 LinkedList(initializer_list<EleTy> list) {
3 auto it = list.begin();
4 auto llcur = &dummy;
5 while (it != list.end()) {
6 llcur->next = new Node(*it);
7 llcur = llcur->next;
8 it++;
9 }
10 }
拷贝构造函数
由于定义了析构函数，且我们的类确实动态分配了内存，所以应当定义拷贝构造函数实现深拷贝，避免 Double Free.
1 // 由于定义了析构函数，因此必须定义拷贝构造函数
2 LinkedList(LinkedList const& other) {
3 auto othercur = other.dummy.next;
4 auto tail_ = tail(true);
5 while (othercur) {
6 tail_->next = new Node(othercur->val);
7 tail_ = tail_->next;
8 othercur = othercur->next;
9 }
10 }
这样对于类似
1LinkedList<int> h2 = h1;
2// 或者
3LinkedList<int> h3(h1);
这样的使用，也能从容应对。拷贝构造不用我们调用 dispose()，因为它的调用时机决定了尚未额外使用堆内存。
拷贝赋值函数
同理定义拷贝赋值函数。
1 // 由于定义了析构函数，因此必须定义拷贝赋值函数
2 LinkedList& operator=(LinkedList& other) {
3 dispose();
4 auto othercur = other.dummy.next;
5 auto tail_ = tail(true);
6 while (othercur) {
7 tail_->next = new Node(othercur->val);
8 tail_ = tail_->next;
9 othercur = othercur->next;
10 }
11 return *this;
12 }
考虑到会有这样的使用：
1LinkedList<int> h2({1,2,3});
2h2 = h1;
因此我们必须对 h2 进行资源释放然后再拷贝 h1 的资源。这样保证 h2 所占据的资源会被正确释放，然后通过我们定义的拷贝赋值函数装载 h1 的值。
移动构造和移动赋值
为了支持移动，我们可以选择定义移动构造函数和移动赋值函数，这样更加高效。但二者也必须同时定义。
1 // 支持移动
2 LinkedList(LinkedList&& other) : dummy(other.dummy) {
3 other.dummy.next = nullptr;
4 }
5 // 由于定义了移动构造函数，因此必须同时定义移动赋值函数
6 LinkedList& operator=(LinkedList&& other) {
7 this->dummy = other.dummy;
8 other.dummy.next = nullptr;
9 return *this;
10 }
可以看到，移动的情况，我们接收一个右值，直接夺取了其 dummy 成员的所有权。不必重复分配。
实现链表功能
链表的大多数操作都比较简单，但交换是比较复杂的一个，因此我们着重实现一下交换：
1 void _swap(Node* aPrev, Node* a, Node* bPrev, Node* b) {
2 auto aNext = a->next, bNext = b->next;
3
4 // 情况1 aPrev-->a-->b-->bNext
5 if (aNext == b) {
6 aPrev->next = b;
7 b->next = a;
8 a->next = bNext;
9 }
10 // 情况2 bPrev-->b-->a-->aNext
11 else if (bNext == a) {
12 bPrev->next = a;
13 a->next = b;
14 b->next = aNext;
15 }
16 // 情况3 aPrev->a-->aNext...->bPrev-->b-->bNext
17 else {
18 aPrev->next = b;
19 bPrev->next = a;
20 a->next = bNext;
21 b->next = aNext;
22 }
23 }
24
25 // 获取一个节点的前一个节点
26 Node* prevOf(Node* a) {
27 auto cur = &dummy;
28 while (cur->next) {
29 if (cur->next == a) {
30 return cur;
31 }
32 cur = cur->next;
33 }
34 return nullptr;
35 }
36 // 交换两个节点
37 void swap(Node* a, Node* b) {
38 auto aPrev = prevOf(a), bPref = prevOf(b);
39 _swap(aPrev, a, bPref, b);
40 }
链表中两个节点的交换需要分两个大类讨论。
-
相邻。则需要三步完成交换，根据相邻的先后位置决定三步如何完成。
-
不相邻。则比较简单，直接建立新的链接即可。
实现其他功能
这里我直接给出完整的代码吧：
1template <class EleTy>
2class LinkedList {
3 public:
4 class Node {
5 public:
6 EleTy val;
7 // 确保默认值是 nullptr
8 Node* next{nullptr};
9 explicit Node() noexcept(true) {}
10 explicit Node(EleTy val) noexcept(true) : val(val) {}
11 explicit Node(EleTy val, Node* next) noexcept(true)
12 : val(val), next(next) {}
13 };
14
15 private:
16 // 伪头结点
17 Node dummy;
18
19 // 释放内存
20 void dispose() noexcept(true) {
21 auto llcur = dummy.next;
22 while (llcur) {
23 Node* next = llcur->next;
24 delete llcur;
25 llcur = next;
26 }
27 dummy.next = nullptr;
28 }
29
30 void _swap(Node* aPrev, Node* a, Node* bPrev, Node* b) {
31 auto aNext = a->next, bNext = b->next;
32
33 // 情况1 aPrev-->a-->b-->bNext
34 if (aNext == b) {
35 aPrev->next = b;
36 b->next = a;
37 a->next = bNext;
38 }
39 // 情况2 bPrev-->b-->a-->aNext
40 else if (bNext == a) {
41 bPrev->next = a;
42 a->next = b;
43 b->next = aNext;
44 }
45 // 情况3 aPrev->a-->aNext...->bPrev-->b-->bNext
46 else {
47 aPrev->next = b;
48 bPrev->next = a;
49 a->next = bNext;
50 b->next = aNext;
51 }
52 }
53
54 public:
55 // 空构造函数
56 LinkedList() {}
57
58 // 用初始值构造
59 LinkedList(initializer_list<EleTy> list) {
60 auto it = list.begin();
61 auto llcur = &dummy;
62 while (it != list.end()) {
63 llcur->next = new Node(*it);
64 llcur = llcur->next;
65 it++;
66 }
67 }
68 // 析构函数
69 ~LinkedList() { dispose(); }
70
71 // 由于定义了析构函数，因此必须定义拷贝构造函数
72 LinkedList(LinkedList const& other) {
73 auto othercur = other.dummy.next;
74 auto tail_ = tail(true);
75 while (othercur) {
76 tail_->next = new Node(othercur->val);
77 tail_ = tail_->next;
78 othercur = othercur->next;
79 }
80 }
81
82 // 由于定义了析构函数，因此必须定义拷贝赋值函数
83 LinkedList& operator=(LinkedList& other) {
84 dispose();
85 auto othercur = other.dummy.next;
86 auto tail_ = tail(true);
87 while (othercur) {
88 tail_->next = new Node(othercur->val);
89 tail_ = tail_->next;
90 othercur = othercur->next;
91 }
92 return *this;
93 }
94 // 支持移动
95 LinkedList(LinkedList&& other) : dummy(other.dummy) {
96 other.dummy.next = nullptr;
97 }
98 // 由于定义了移动构造函数，因此必须同时定义移动赋值函数
99 LinkedList& operator=(LinkedList&& other) {
100 this->dummy = other.dummy;
101 other.dummy.next = nullptr;
102 return *this;
103 }
104 Node* first(EleTy val) {
105 auto llcur = dummy.next;
106 while (llcur) {
107 if (llcur->val == val) {
108 return llcur;
109 }
110 llcur = llcur->next;
111 }
112 return nullptr;
113 }
114 void push_back(EleTy val) { tail(true)->next = new Node(val); }
115 void push_back(initializer_list<EleTy> vals) {
116 auto it = vals.begin();
117 auto cur = tail(true);
118 while (it != vals.end()) {
119 cur->next = new Node(*it);
120 cur = cur->next;
121 it++;
122 }
123 }
124 // 获取尾部元素。如果 get_dummy 为真，则允许获取伪头节点
125 Node* tail(bool get_dummy = false) {
126 Node* prev = get_dummy ? &dummy : nullptr;
127 auto llcur = dummy.next;
128 while (llcur) {
129 prev = llcur;
130 llcur = llcur->next;
131 }
132 return prev;
133 }
134 Node* prevTail() {
135 Node* prev = &dummy;
136 auto llcur = prev->next;
137 while (llcur->next) {
138 prev = llcur;
139 llcur = llcur->next;
140 }
141 return prev;
142 }
143 void show(string prefix = "list ") {
144 auto llcur = dummy.next;
145 std::cout << prefix << "at " << this << " = ";
146 while (llcur) {
147 std::cout << llcur->val << " ";
148 llcur = llcur->next;
149 }
150 std::cout << std::endl;
151 }
152 // 获取一个节点的前一个节点
153 Node* prevOf(Node* a) {
154 auto cur = &dummy;
155 while (cur->next) {
156 if (cur->next == a) {
157 return cur;
158 }
159 cur = cur->next;
160 }
161 return nullptr;
162 }
163 // 交换两个节点
164 void swap(Node* a, Node* b) {
165 auto aPrev = prevOf(a), bPref = prevOf(b);
166 _swap(aPrev, a, bPref, b);
167 }
168 void insert_after(Node* pos, EleTy val) {
169 auto newNode = new Node(val);
170 newNode->next = pos->next;
171 pos->next = newNode;
172 }
173 void insert_at(int index, EleTy val) {
174 assert(index >= 0);
175 auto cur = &dummy;
176 while (index-- > 0) {
177 cur = cur->next;
178 }
179 insert_after(cur, val);
180 }
181};
182int main() {
183 LinkedList h1({1, 2, 3, 4});
184 h1.swap(h1.first(4), h1.first(3));
185 h1.show("h1: ");
186 h1.push_back({1, 2});
187 h1.show("h1: ");
188 h1.insert_after(h1.first(3), 9);
189 h1.insert_at(0, 8);
190 LinkedList<int> h3;
191 h3 = std::move(h1);
192 h1.show("h1: ");
193 h3.show("h3: ");
194
195 LinkedList h4({1, 2, 3, 4});
196 h4 = h3;
197 h4.show("h4: ");
198
199 LinkedList<string> h2({"aa", "bb"});
200 h2.swap(h2.first("aa"), h2.first("bb"));
201 h2.show("h2: ");
202 h2.push_back({"cc"});
203 h2.push_back("dd");
204 h2.show("h2: ");
205 return 0;
206}
编译时，可以采用 -fsanitize=address 选项，或者使用 valgrind ：
1valgrind --tool=memcheck --leak-check=full
这样能够第一时间发现内存泄漏。
个人感觉现在工具这么完善了，内存泄漏或者重复释放的检测基本上（只要各个分支都覆盖执行）问题不大。困难的地方不在于定位内存泄漏的分配位置，而在于定位泄漏的根本原因。我的经验是使用二分法。
如果有可以改进的地方，还望读者赐教！