1. 单向链表的结构
在上一个章节中为大家详细讲解了静态链表，它解决了插入和删除数据的时候大量移动元素的问题，但是解决不了合理分配和使用内存的问题。解决这个问题的最优方案就是使用动态链表，简称链表。
链表和数组都可以称之为线性表，数组是一种顺序存储结构的线性表，而链表是一种链式存储结构的线性表，链表中的节点和节点之间的内存是不连续的，它们之间的前后关系需要通过指针来维系。
关于链表有很多种，比如：单向链表、单向循环链表，双向链表、双向循环链表，并且这些链表可以带头结点也可以不带头结点。
1.1 单向链表节点
我们先从单向链表说起，所谓的单向链表就是链表的节点中只有一个指针域，并且这个指针域指向当前节点的下一个节点（后继节点）的地址。
假设单向链表的节点存储的是整形数据，那么该节点的定义如下：
1
2
3
4
5
6
|
struct Node
{
int data = 0;
Node* next = nullptr;
};
|
对于上图这个单向链表而言：
- 链表第1个节点中的
Next指针保存了第2个节点中Data1的起始地址
- 链表第2个节点中的
Next1指针保存了第3个节点中Data2的起始地址
- 链表第3个节点中的
Next2指针保存了第4个节点中Data3的起始地址
- 链表最后一个节点中的
Next3指针指向了空地址nullptr
通过这种方式我们就可以使用指针维护一个链式结构的线性表了。
1.2 头结点和头指针
1.2.1 头结点
头结点是为了操作的方便和统一而设立的，放在第一个数据节点之前，其数据域一般没有意义（有时也用来存储链表的长度）。
- 有了头结点之后，在第一个数据节点前插入新节点和删除第一个数据节点，其操作流程和其他数据节点无异
- 链表可以有头结点，也可以没有头结点
下图是不带头结点的链表：
下图是带头结点的链表：
通过对比，二者的区别一目了然，平时建议使用带头结点的链表，它的优势在后边的链表操作章节大家会有深刻体会。
链表中的最后一个节点我们将其称之为尾节点，尾节点和其它节点的不同之处在于它的指针域指向的不是下一个数据节点的地址而是空，通常用 NULL（C语言）或者 nullptr（C++）表示。
1.2.2 头指针
头指针顾名思义就是指向链表头结点地址的指针，对于链表的操作必须从头指针开始。在编码过程中一般都是通过头指针来辅助我们完成链表的节点插入、节点删除、节点遍历等操作。
在进行链表操作的时候定义一个指针让其指向链表的头结点，此时这个指针就是上面所说的头指针了。它是我们操作链表的过程中的一个必要步骤，那么如何对链表进行节点的添加、删除以及遍历呢？接下来我们来逐一分析。
2. 单向链表的操作
2.1 链表的遍历和搜索
关于链表的遍历应该是链表操作中最简单的操作了，主要步骤如下：
- 定义一个辅助指针，让指针指向链表的第一个节点，得到头指针
- 根据头结点的
next域指针，访问第二个链表节点，再根据第二个节点的next域指针访问第三个链表节点，以此类推……
- 判断如果某个链表节点的
next域指针指向空(NUL或者nullptr)，遍历结束
如果掌握了链表的遍历，想要搜索链表中的某个节点，大家也就有思路了，只需要在遍历链表过程中，对每个节点进行判断即可。
关于链表的搜索无外乎有两种方式：
按照值搜索：遍历过程中将每个节点的值和要搜索的值进行比较按照节点搜索：遍历过程中将每个节点的地址和要搜索的节点的地址进行比较
2.2 链表的插入
2.2.1 带头结点的插入
场景1：在头部和中间位置插入新节点
对于带头节点的链表而言，在头部插入节点就是把新的数据节点作为链表的第一个数据节点，它是头结点的后继节点。
带头结点的单向链表在进行新节点插入的时候需要判断的情况相对较少，在链表中插入第一个数据节点和在中间位置插入数据节点的处理流程是一样的。
在链表的头部和中间位置（pos）插入新节点需要分以下几步：
- 创建一个新的节点，并初始化，记作
newNode
- 遍历链表找到
pos-1位置的节点，记作preNode
- 将新节点的后继节点设置为
pos位置的节点，也就是newNode->next = preNode->next
- 重置
preNode节点的后继，设置为newNode，即：preNode->next = newNode
温馨提示：第三步、第四步操作是不能颠倒的。
下图是将新节点插入到链表的非第一个数据节点的位置：
下图是将新节点作为第一个数据节点插入到链表中：
有图有真相，证明在以上两种情况下插入新节点的操作流程是相同的。
场景2：在尾部插入新节点
在链表的尾部添加新节点就是让原来的尾节点指向新节点的地址，让新节点的指针域指向空地址。主要的操作步骤如下：
- 遍历链表并找到它的尾节点，记作
tailNode
- 创建一个新的链表节点，记作
newNode，并初始化，有两种方式：
newNode->next = nullptrnewNode->next = tailNode->next
- 让找到的尾节点的指针域指向新创建的节点的地址，
tailNode->next = newNode
在链表尾部添加新节点的时候，上图中两条红色的线，先连接哪一条取决于 newNode 节点的 next 域的初始化方式（详见步骤2）。
2.2.2 不带头结点的插入
如果是带头结点的链表，在进行链表操作的过程中永远不会出现链表中没有任何节点的情况。如果链表没有头结点在进行插入操作的时候就需要单独对这种情况进行判断。
场景1：空链表
如果链表为空链表，那么新添加的节点就是链表的第一个数据节点。另外，如果有头指针需要让头指针指向这个新添加的节点。
场景2：在头部插入新节点
将新的节点插入到链表头部的操作相对简单，操作流程如下：
- 创建一个新的链表节点
- 使用新的链表节点的
next域指针指向原来的链表头结点
- 如果有头指针需要让头指针前移，指向这个新添加的节点
场景3：在链表中间位置插入新节点
在链表的中间位置（pos）插入新节点的操作步骤如下：
- 创建一个新的节点，并初始化，记作
newNode
- 遍历链表找到
pos-1位置的节点，记作preNode
- 将新节点的后继节点设置为
pos位置的节点，也就是newNode->next = preNode->next
- 重置
preNode节点的后继，设置为newNode，即：preNode->next = newNode
温馨提示：第三步、第四步操作是不能颠倒的。
场景4：在链表尾部插入新节点
在链表的尾部添加新节点主要的操作步骤如下：
- 遍历链表并找到它的尾节点，记作
tailNode
- 创建一个新的链表节点，记作
newNode，并初始化，有两种方式：
newNode->next = nullptrnewNode->next = tailNode->next
- 让找到的尾节点的指针域指向新创建的节点的地址，
tailNode->next = newNode
通过上面的分析可以得出结论，对于不带头结点的链表而言，在处理插入节点的过程中比带头结点的链表要判断更多的情况。另外，两种链表在中间位置以及尾部添加新节点的时候，处理流程是相同的。
2.3 链表的删除
2.3.1 带头结点的删除
通过以上两种场景下操作流程的对比可以得到一个结论：对于带头结点的单向链表，删除链表中任意位置的节点的处理流程都是相同的。
2.3.2 不带头结点的删除
如果是不带头结点的链表，在进行节点删除的时候会出现链表为空（没有任何节点）的情况，对于这种特殊情况需要单独进行处理。
通过上面的分析可以得出结论：不论是带头结点的链表还是不带头结点的链表，在删除中间位置或者尾部数据节点的时候，操作流程是相同的。
3. 单向链表的实现
3.1 带头结点的单向链表
在进行链表操作的时候，为了能够提高操作效率以及使用起来更加方便，除了给链表添加一个头指针以外，还可以提供一个尾指针，有了尾指针之后访问链表尾节点的时候时间复杂度就从O(n)变成了O(1)。同理，给链表添加了长度成员之后，每次想要得到链表的长度，就不需要进行遍历了。
头文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#pragma once
struct Node
{
int data = 0;
Node* next = nullptr;
};
class LinkList
{
public:
LinkList();
~LinkList();
bool isEmpty();
int length();
void prepend(int data);
void append(int data);
bool insert(int pos, int data);
Node* find(int data, int& pos);
bool remove(int pos);
void display();
inline Node* head() { return m_head; }
int value(int pos);
private:
int m_length = 0;
Node* m_head = nullptr;
Node* m_tail = nullptr;
};
|
关于上面链表类中的各个操作函数都有对应的注释说明，在此就不再赘述了。
源文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
#include "SLinkList.h"
#include <iostream>
#include <cassert>
using namespace std;
LinkList::LinkList() : m_head(new Node)
{
if (m_head == nullptr)
{
return;
}
m_head->next = nullptr;
m_tail = m_head;
}
LinkList::~LinkList()
{
Node* p = m_head;
while (p != nullptr)
{
Node* tmp = p;
cout << "释放资源: " << tmp->data << endl;
p = p->next;
delete tmp;
}
}
bool LinkList::isEmpty()
{
bool flag = m_head->next == nullptr;
return flag;
}
int LinkList::length()
{
return m_length;
}
void LinkList::prepend(int data)
{
Node* pNode = new Node;
if (pNode == nullptr)
{
cout << "头部添加链表节点失败!\n" << endl;
return;
}
pNode->data = data;
pNode->next = m_head->next;
if (m_head->next == nullptr)
{
m_tail = pNode;
}
m_head->next = pNode;
m_length++;
}
void LinkList::append(int data)
{
Node* pNode = new Node;
pNode->data = data;
m_tail->next = pNode;
m_tail = pNode;
m_length++;
}
bool LinkList::insert(int pos, int data)
{
if (pos < 1 || pos > length()+1)
{
return false;
}
Node* p = m_head;
int j = 0;
while (p != nullptr && j < pos - 1)
{
p = p->next;
j++;
}
Node* pNode = new Node;
pNode->data = data;
if (length()+1 == pos)
{
m_tail = pNode;
}
pNode->next = p->next;
p->next = pNode;
m_length++;
return true;
}
Node* LinkList::find(int data, int& pos)
{
pos = 1;
Node* p = m_head->next;
while (p != nullptr && p->data != data)
{
p = p->next;
pos++;
}
return p;
}
bool LinkList::remove(int pos)
{
if (pos < 1 || pos > length())
{
cout << "删除失败, 无效的节点位置" << endl;
return false;
}
Node* p = m_head;
for (int i = 0; i < pos - 1; ++i)
{
p = p->next;
}
Node* delNode = p->next;
p->next = delNode->next;
if (delNode->next == nullptr)
{
m_tail = p;
}
delete delNode;
m_length--;
return true;
}
void LinkList::display()
{
Node* p = m_head->next;
if (p == nullptr)
{
cout << "空链表" << endl;
return;
}
cout << "链表值: ";
while (p != nullptr)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int LinkList::value(int pos)
{
assert(pos > 0 && pos <= length());
Node* p = m_head;
for (int i = 0; i < pos; ++i)
{
p = p->next;
}
return p->data;
}
int main()
{
LinkList lst;
bool flag = lst.isEmpty();
cout << "链表是否为空: " << flag << endl;
lst.insert(1, 88);
lst.prepend(10);
lst.append(20);
lst.prepend(30);
lst.insert(2, 40);
lst.insert(1, 50);
lst.insert(6, 60);
lst.append(100);
cout << "链表长度尾: " << lst.length() << endl;
lst.display();
int pos = 0;
Node* node = lst.find(50, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
node = lst.find(100, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
node = lst.find(10, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
lst.append(200);
lst.display();
return 0;
}
|
在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部（第一个数据节点）、中间、尾部。
执行程序，终端输出的信息为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 链表是否为空: 1
链表长度尾: 8
链表值: 50 30 40 10 88 60 20 100
元素的位置: 1, 元素值: 50
链表值: 30 40 10 88 60 20 100
元素的位置: 7, 元素值: 100
链表值: 30 40 10 88 60 20
元素的位置: 3, 元素值: 10
链表值: 30 40 88 60 20
链表值: 30 40 88 60 20 200
释放资源: 0
释放资源: 30
释放资源: 40
释放资源: 88
释放资源: 60
释放资源: 20
释放资源: 200
|
对于上面链表类中的某些API函数带有一个整形的节点位置pos，该位置的值是从1开始的，也就是说链表中第一个数据节点的位置是1。
3.2 不带头节点的单向链表
头文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#pragma once
struct Node
{
int data = 0;
Node* next = nullptr;
};
class LinkList1
{
public:
LinkList1();
~LinkList1();
bool isEmpty();
int length();
void prepend(int data);
void append(int data);
bool insert(int pos, int data);
Node* find(int data, int& pos);
bool remove(int pos);
void display();
private:
int m_length = 0;
Node* m_head = nullptr;
Node* m_tail = nullptr;
};
|
源文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
#include "SLinkList1.h"
#include <iostream>
using namespace std;
LinkList1::LinkList1()
{
}
LinkList1::~LinkList1()
{
Node* p = m_head;
while (p != nullptr)
{
Node* tmp = p;
cout << "释放资源: " << tmp->data << endl;
p = p->next;
delete tmp;
}
}
bool LinkList1::isEmpty()
{
return m_head == nullptr;
}
int LinkList1::length()
{
return m_length;
}
void LinkList1::prepend(int data)
{
Node* pNode = new Node;
pNode->data = data;
if (m_head == nullptr)
{
m_tail = pNode;
}
pNode->next = m_head;
m_head = pNode;
m_length++;
}
void LinkList1::append(int data)
{
Node* pNode = new Node;
pNode->data = data;
if (isEmpty())
{
m_head = m_tail = pNode;
}
else
{
m_tail->next = pNode;
m_tail = pNode;
}
m_length++;
}
bool LinkList1::insert(int pos, int data)
{
if (pos<1 || pos>length() + 1)
{
cout << "插入数据失败, 位置无效" << endl;
return false;
}
Node* pNode = new Node;
pNode->data = data;
if (pos == length()+1)
{
m_tail = pNode;
}
if (pos == 1)
{
pNode->next = m_head;
m_head = pNode;
m_length++;
return true;
}
Node* p = m_head;
int j = 1;
while (p != nullptr && j < pos - 1)
{
p = p->next;
j++;
}
pNode->next = p->next;
p->next = pNode;
m_length++;
return true;
}
Node* LinkList1::find(int data, int& pos)
{
pos = 1;
Node* p = m_head;
while (p != nullptr && p->data != data)
{
p = p->next;
pos++;
}
return p;
}
bool LinkList1::remove(int pos)
{
if (pos<1 || pos>length())
{
return false;
}
Node* p = m_head;
if (pos == 1)
{
m_head = p->next;
delete p;
m_length--;
return true;
}
for (int i = 2; i < pos; ++i)
{
p = p->next;
}
Node* delNode = p->next;
p->next = delNode->next;
if (delNode->next == nullptr)
{
m_tail = p;
}
delete delNode;
m_length--;
return true;
}
void LinkList1::display()
{
if (m_head == nullptr)
{
cout << "空链表" << endl;
return;
}
Node* p = m_head;
cout << "链表值: ";
do {
cout << p->data << " ";
p = p->next;
} while (p != nullptr);
cout << endl;
}
int main()
{
LinkList1 lst;
bool flag = lst.isEmpty();
cout << "链表是否为空: " << flag << endl;
lst.insert(1, 88);
lst.prepend(10);
lst.append(20);
lst.prepend(30);
lst.insert(2, 40);
lst.insert(1, 50);
lst.insert(7, 60);
lst.append(100);
cout << "链表长度: " << lst.length() << endl;
lst.display();
int pos = 0;
Node* node = lst.find(50, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
node = lst.find(100, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
node = lst.find(10, pos);
cout << "元素的位置: " << pos << ", 元素值: " << node->data << endl;
lst.remove(pos);
lst.display();
lst.append(200);
lst.display();
return 0;
}
|
在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部、中间、尾部。
执行程序，终端打印的信息如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 链表是否为空: 1
链表长度: 8
链表值: 50 30 40 10 88 20 60 100
元素的位置: 1, 元素值: 50
链表值: 30 40 10 88 20 60 100
元素的位置: 7, 元素值: 100
链表值: 30 40 10 88 20 60
元素的位置: 3, 元素值: 10
链表值: 30 40 88 20 60
链表值: 30 40 88 20 60 200
释放资源: 30
释放资源: 40
释放资源: 88
释放资源: 20
释放资源: 60
释放资源: 200
|
比较上面的两份代码，证明不带头结点的链表在进行节点插入、删除的时候确实是要处理更多的情况，这样无疑就给bug的滋生提供了更多的生存空间。
