简介
链表（linked list）是一种线性数据结构，最大的特点就是存储不连续，可以用于实现邻接表等。
链表分为单链表、双向链表和循环链表三种，如下图所示：
可以看出，单链表中每个节点都有一个next指针，指向后一个节点，而最后一个节点的next为空指针；
双向链表的每个节点还有一个prev指针，指向前一个节点；
循环链表则是在上面的基础上让最后一个节点的next指向头节点，如果是双向循环链表还会让头节点的prev指针指向最后一个节点。
代码
链表可以用数组和指针两种方式实现，以下我们采用指针来实现单链表。
注意：以下的代码中使用了C++ 11标准中的nullptr表示空指针，若不支持C++ 11标准，请把代码中的所有nullptr替换成NULL。
首先，先用struct创建节点的结构体：1
2
3
4
5
6
7
8
9
10
11
12
13template<class type>
struct Node {
type data;
Node<type> *nxt;
Node(type _data);
};
template<class type>
Node<type>::Node(type _data) {
data = _data;
nxt = nullptr;
}
然后构建一个链表模板类：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23template<class type>
class LinkedList {
private:
Node<type> *head;
public:
LinkedList();
Node<type>* getHead();
Node<type>* getEnd();
Node<type>* locate(int pos);
void ins(type data);
void ins(type data, int pos);
void del();
void del(int pos);
int size();
void print();
bool empty();
};
template<class type>
LinkedList<type>::LinkedList() {
head = nullptr;
}
我们用私有变量head储存头指针，初始化时将其设置为nullptr。LinkedList的方法有10个：
getHead()：返回head指针getEnd()：返回最后一个节点的指针locate(int pos)：返回第pos个节点的指针ins(type data)：将data插入到末尾ins(type data, int pos)：重载函数，将data插入到pos的位置del()：删除末尾节点del(int pos)：重载函数，删除第pos个节点size()：返回节点数print()：遍历链表，输出每个节点的值empty()：返回链表是否为空
这几个方法比较好写：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
72template<class type>
Node<type>* LinkedList<type>::getHead() {
return head;
}
template<class type>
Node<type>* LinkedList<type>::getEnd() {
Node<type> *ptr = head;
while (ptr -> nxt != nullptr)
ptr = ptr -> nxt;
return ptr;
}
template<class type>
Node<type>* LinkedList<type>::locate(int pos) {
if (pos < 0 || pos > size())
return nullptr;
Node<type> *ptr = head;
for (int i = 1; i <= pos; ++i)
ptr = ptr -> nxt;
return ptr;
}
template<class type>
void LinkedList<type>::ins(type data) {
Node<type> *node = new Node<type>(data);
if (head == nullptr)
head = node;
else {
Node<type> *ptr = getEnd();
ptr -> nxt = node;
}
}
template<class type>
void LinkedList<type>::del() {
if (head -> nxt == nullptr)
return;
Node<type> *ptr = head, *p = nullptr;
while (ptr -> nxt != nullptr) {
p = ptr;
ptr = ptr -> nxt;
}
p -> nxt = nullptr;
delete ptr;
}
template<class type>
int LinkedList<type>::size() {
int len = -1;
Node<type> *ptr = head;
while (ptr != nullptr) {
++len;
ptr = ptr -> nxt;
}
return len;
}
template<class type>
void LinkedList<type>::print() {
Node<type> *ptr = head;
while (ptr -> nxt != nullptr) {
ptr = ptr -> nxt;
printf("%d ", ptr -> data);
}
puts("");
}
template<class type>
bool LinkedList<type>::empty() {
return head == nullptr || head -> nxt == nullptr;
}
大部分都是直接遍历链表就好。
对于插入到链表中间的操作，我们可以让前一个节点指向新节点，而新节点的next指向前一个节点的next。
例如，对于下图，我们想把$233$插入到第2个节点：
可以先创建一个新节点，值为$233$：
然后使Node 1的next指向新节点，新节点的next指向原Node 2（原Node 2变成Node 3，原Node 3变成Node 4）：
代码：1
2
3
4
5
6
7
8template<class type>
void LinkedList<type>::ins(type data, int pos) {
if (pos < 1 || pos > size())
return;
Node<type> *node = new Node<type>(data), *ptr = locate(pos - 1);
node -> nxt = ptr -> nxt;
ptr -> nxt = node;
}
同样，对于删除操作，我们只要让前一个节点的next指向待删除节点的next，然后删除节点即可。
代码如下：1
2
3
4
5
6
7
8template<class type>
void LinkedList<type>::del(int pos) {
if (pos < 1 || pos > size())
return;
Node<type> *ptr = locate(pos - 1), *p = ptr -> nxt;
ptr -> nxt = p -> nxt;
delete p;
}
完整代码：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
128template<class type>
struct Node {
type data;
Node<type> *nxt;
Node(type _data);
};
template<class type>
Node<type>::Node(type _data) {
data = _data;
nxt = nullptr;
}
template<class type>
class LinkedList {
private:
Node<type> *head;
public:
LinkedList();
Node<type>* getHead();
Node<type>* getEnd();
Node<type>* locate(int pos);
void ins(type data);
void ins(type data, int pos);
void del();
void del(int pos);
int size();
void print();
bool empty();
};
template<class type>
LinkedList<type>::LinkedList() {
head = nullptr;
}
template<class type>
Node<type>* LinkedList<type>::getHead() {
return head;
}
template<class type>
Node<type>* LinkedList<type>::getEnd() {
Node<type> *ptr = head;
while (ptr -> nxt != nullptr)
ptr = ptr -> nxt;
return ptr;
}
template<class type>
Node<type>* LinkedList<type>::locate(int pos) {
if (pos < 0 || pos > size())
return nullptr;
Node<type> *ptr = head;
for (int i = 1; i <= pos; ++i)
ptr = ptr -> nxt;
return ptr;
}
template<class type>
void LinkedList<type>::ins(type data) {
Node<type> *node = new Node<type>(data);
if (head == nullptr)
head = node;
else {
Node<type> *ptr = getEnd();
ptr -> nxt = node;
}
}
template<class type>
void LinkedList<type>::ins(type data, int pos) {
if (pos < 1 || pos > size())
return;
Node<type> *node = new Node<type>(data), *ptr = locate(pos - 1);
node -> nxt = ptr -> nxt;
ptr -> nxt = node;
}
template<class type>
void LinkedList<type>::del() {
if (head -> nxt == nullptr)
return;
Node<type> *ptr = head, *p = nullptr;
while (ptr -> nxt != nullptr) {
p = ptr;
ptr = ptr -> nxt;
}
p -> nxt = nullptr;
delete ptr;
}
template<class type>
void LinkedList<type>::del(int pos) {
if (pos < 1 || pos > size())
return;
Node<type> *ptr = locate(pos - 1), *p = ptr -> nxt;
ptr -> nxt = p -> nxt;
delete p;
}
template<class type>
int LinkedList<type>::size() {
int len = -1;
Node<type> *ptr = head;
while (ptr != nullptr) {
++len;
ptr = ptr -> nxt;
}
return len;
}
template<class type>
void LinkedList<type>::print() {
Node<type> *ptr = head;
while (ptr -> nxt != nullptr) {
ptr = ptr -> nxt;
printf("%d ", ptr -> data);
}
puts("");
}
template<class type>
bool LinkedList<type>::empty() {
return head == nullptr || head -> nxt == nullptr;
}
双向链表和循环链表的实现与单链表类似，不多赘述。
