链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
本文主要给大家介绍了关于C++实现双链表基本接口的相关内容，分享出来供大家参考学习，话不多说，来一起看看详细的介绍吧。
首先先简单通过图示区分单链表和双链表的结构差异：
单链表的基本接口实现可参考：单链表简单实现
接下来就是双链表的基本接口实现：
|
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
|
#include <iostream>#include <assert.h>using namespace std;typedef int DataType;struct ListNode{ ListNode* _next; ListNode* _prev; DataType _data; ListNode(DataType x) :_next(NULL) , _prev(NULL) , _data(x) {}};typedef ListNode Node;class List{public: List() :_head(NULL) ,_tail(NULL) {} List(const List& l) :_head(NULL) ,_tail(NULL) { Copy(l); } void Copy(const List& l) { Node* cur = l._head; while (cur) { PushBack(cur->_data); cur = cur->_next; } } List& operator=(const List& l) { Destory(); Copy(l); return *this; } ~List() { Destory(); } void Destory() { if (_head) { Node* cur = _head; while (_head) { cur = _head; _head = _head->_next; delete cur; } _head = _tail = NULL; } } void PushBack(DataType x) { if (_head == NULL) { Node* tmp = new Node(x); tmp->_next = tmp->_prev = NULL; _head = _tail = tmp; } else { Node* tmp = new Node(x); _tail->_next = tmp; tmp->_prev = _tail; _tail = tmp; } } void PopBack() { if (_head == NULL) { return; } else if (_head->_next == NULL) { delete _head; _head = _tail = NULL; } else { Node* tmp = _tail; _tail = _tail->_prev; _tail->_next = NULL; delete tmp; } } void PushFront(DataType x) { if (_head == NULL) { _head = _tail = new Node(x); } else { Node* tmp = new Node(x); tmp->_next = _head; _head->_prev = tmp; _head = _head->_prev; } } void PopFront() { if (_head == NULL) { return; } else if (_head->_next == NULL) { delete _head; _head = _tail = NULL; } else { Node* tmp = _head; _head = _head->_next; delete tmp; _head->_prev = NULL; } } Node* Find(DataType x) { Node* cur = _head; while (cur) { if (cur->_data == x) return cur; cur = cur->_next; } return NULL; } // 在pos的前面插入x void Insert(Node* pos, DataType x) { assert(pos); if ((pos == 0) || (pos->_prev == NULL)) { PushFront(x); } else { Node* font = pos->_prev; Node* tmp = new Node(x); tmp->_prev = font; tmp->_next = pos; font->_next = tmp; pos->_prev = tmp; } } //删除pos位置的元素 void Erase(Node* pos) { assert(pos); if ((pos == 0) || (pos->_prev == NULL)) { PopFront(); } else if (pos->_next == NULL) { PopBack(); } else { Node* font = pos->_prev; Node* last = pos->_next; font->_next = last; last->_prev = font; delete pos; } } //逆序整个双链表 void Reverse() { Node* cur = _head; while (cur) { swap(cur->_next,cur->_prev); cur = cur->_prev; } swap(_head, _tail); } void Print() { Node* cur = _head; while (cur) { cout << cur->_data << "->"; cur = cur->_next; } cout << "NULL" << endl; }private: Node* _head; Node* _tail;}; |
注：在一些操作实现时，一定要要考虑清楚各种情况，再进行情况的分类尽量提高代码的复用程度。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持
原文链接：http://blog.csdn.net/sssssuuuuu666/article/details/75442501
