C++实现一个尽可能优雅的双向链表
justaLoli

这是「数据结构与算法」课程的一部分. 在这门课中, 我们将接触各种常见的数据结构, 并了解它们各种基本操作的实现方式.

这门课的第一章为顺序表, 其中包括一种数据结构“链表”. 我产生了一种想法, 为什么不借助C++强大的类封装能力, 实现一个自己的链表呢?

我的目标是想让这个链表尽可能的“优雅”. 这要求在使用这个链表时, 各种操作应尽可能的简洁直观. 我的目标是做的比C++ STL模版库的链表易用(虽然性能可能略低), 并且尽可能靠近python的列表.

注意: STL模版库的list是双向链表,但python的list, 据资料, 是基于变长顺序表. 这里说的靠近不是利用python list的底层逻辑, 而是实现和python list尽可能相似的调用方式.

使用例

话不多说, 先看使用例:

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
/* 本程序需要引用的外部库仅iostream */

/* 例子1 简单的添加数据、打印数据 */
list<int> list1;
for (int i = 1; i <= 10; ++i)
{
list1.append(i);
}
cout << list1 << endl;

/* 例子2 列表嵌套 */
list<list<int>> list2;
int num = 1;
for (int i = 1; i <= 10; ++i)
{
list<int> templist;
for (int j = 0; j < i; ++j,++num)
{
templist.append(num);
}
list2.append(templist);
}
for (int i = 0; i < 10; ++i)
{
for (int j = 0; j < list2[i].size(); ++j)
{
cout << list2[i][j] << " ";
}
cout << endl;
}

结果:

1
2
3
4
5
6
7
8
9
10
11
12
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
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
程序执行完成, 用时63微秒.

使用过python的人, 应该能看出我对python列表的借鉴(比如append()); 使用过C++ STL模版库的list的人, 应该能看出它比STL list在使用(尤其是遍历)上要简单一些.

类定义

列表的UML类图如下:

classDiagram 
    class node{
        +T data
        +node* next
        +node* prev
    }
    class list{
        -node* head
        -node* tail
        -int _size
        -node* temp
        -int tempindex
        
        +copy() list
        +slice(i1,i2,i3) list
        +size() int
        +append(data) int
        +insert(index,data) void
        +swap(i1,i2) void
        +pop(i=-1) T
        +remove(data) void
        +clear() void
        +operator[](index) T
        +operator=(data) list
        +operator+(data) list
        +operator+=(data) list
        #get(index) node*
        #swap(node,node) void
    }

在完善这个数据类型的过程中, 遇到了很多有趣的问题, 也学习到了很多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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
#ifndef MYLIST
#define MYLIST
#include <iostream>

namespace my {


#define LOG(args) printf(args);


template <typename T>
class list{
private:
class node{
public:
node(){}
node(const T& dta){data = dta;}
T data;
node* next=nullptr;
node* prev=nullptr;
};
class iterator_base{
protected:
node* ptr;
public:
iterator_base(node* p):ptr(p){}
bool operator!=(const iterator_base& it)const{return ptr!=it.ptr;}
void operator++(){ptr=ptr->next;}void operator++(int){ptr=ptr->next;}
};
class iterator:public iterator_base{
public:
using iterator_base::iterator_base,iterator_base::ptr;
T& operator*(){return ptr->data;}
};
class const_iterator:public iterator_base{
public:
using iterator_base::iterator_base,iterator_base::ptr;
const T& operator*(){return ptr->data;}
};
node* head;
node* tail;
int _size;
node* temp;
int tempindex = 0;
public:

iterator begin(){return iterator(head->next);}
iterator end(){return iterator(tail);}
const_iterator begin()const{return const_iterator(head->next);}
const_iterator end()const{return const_iterator(tail);}



list();/* 构造函数 */

list(const list<T>&);/* 拷贝重载,
做了一些区分:用这个重载是做一个影子链表,用等号重载是做一个完整地拷贝。 */
/* 如此,在初始化和函数传递时默认时 */

~list();/* 析构函数 */

list<T> copy();/* 复制 */

list<T> slice(const int,const int,const int)const;/* 切片 */

int size()const{return _size;}/* 得到长度 */

int append(const T&);/* 追加 */

list<T>& insert(const int,const T&);/* 插入 */

void swap(const int,const int);/* 交换 */

T pop(const int i=-1);/* 弹出并删除 */

void remove(const T&);/* 删除所有和参数相同的元素 */

void clear();/* 清空 */

T& operator[](const int);/* 索引[]运算 */

list<T>& operator=(const list<T>&);/* 赋值=运算 */

list<T> operator+(const list<T>&);/* 加+运算 */

void operator+=(list<T>&);/* 自增+=运算 */

void operator+=(const T&);/* 自增+=运算 */


protected:
node* gethead()const{return head;}
node* gettail()const{return tail;}
node* get(int i);/* 索引,得到节点指针 */
void swap(node*,node*);/* 交换 */
node* getFromHead(int);
node* getFromTail(int);
node* getFromTemp(int);
void resetTemp(){temp=head;tempindex = 0;}/* 重置temp指针保证它指向链中的某个项。 */
/* fun fact:虽然重置tempindex=0,但是现在temp指向head而不是第一个“元素”。
但这无伤大雅。由于距离的最小值判定的逻辑,查找时会优先从head向后查找,而不是用temp查找。 */
int dis(int a,int b){return a>=b?a-b:b-a;}
};

template <typename T>
std::ostream& operator<<(std::ostream& out,const list<T>& L){
/* 运算符:重载cout输出 */
out << "[";
bool flag = false;
for(auto i:L){
if(flag){
out << ", ";
}
else{
flag = true;
}
out << i;
}
out << "]";
return out;
}

template <typename T>
T& list<T>::operator[](const int i){
/* 运算符:索引 */
return get(i)->data;
}
template <typename T>
list<T>& list<T>::operator=(const list<T> &li){
if(this==&li)return *this;
/* 运算符:赋值 */
clear();
node* t = li.head->next;
while(t!=li.tail){
append(t->data);
t = t->next;
}
return *this;
}
template <typename T>
list<T> list<T>::operator+(const list<T>& li){
auto rl = this->copy();

node* t = li.head->next;
while(t!=li.tail){
rl.append(t->data);
t = t->next;
}
return rl;
}
template <typename T>
void list<T>::operator+=(list<T>& li){
if(&li == this){
std::cout << "ERROR: self += detected. plz use + instead.";
exit(1);
return;
}
/* O1,但是引用的li会清空 */
/* 把中间接上 */
tail->prev->next = li.head->next;
li.head->next->prev = tail->prev;
/* 把结尾接上 */
tail->prev = li.tail->prev;
tail->prev->next = tail;
/* 更新size */
_size+=li.size();
/* 让li首尾相接置空,但是不删除里面的元素(里面的元素归this了.) */
li.head->next = li.tail;
li.tail->prev = li.head;
li._size = 0;
}
template <typename T>
void list<T>::operator+=(const T& dta){
append(dta);
}
// list<T> list<T>::operator()(const int,const int,con s){}
template <typename T>
list<T> list<T>::copy(){
list<T> returnlist;
for (int i = 0; i < _size; ++i)
{
returnlist.append((*this)[i]);
}
return returnlist;
}

template <typename T>
list<T> list<T>::slice(int p1, int p2, int p3) const{
list<T> returnlist;
if(p3>0){
for (int i = p1; i < p2; i+=p3)
{
returnlist.append((*this)[i]);
}
}
else if(p3<0){
for (int i = p1; i > p2; i+=p3)
{
returnlist.append((*this)[i]);
}
}
return returnlist;
}

template <typename T>
list<T>::list(){
// cout << "list() called"<<endl;
head = new node;
tail = new node;

resetTemp();

head->next = tail;
tail->prev = head;
_size = 0;
}
template <typename T>
list<T>::list(const list<T>& li):list(){
operator=(li);
}
template <typename T>
void list<T>::clear(){
node *t = head->next;
while(t!=tail){
t = t->next;
delete t->prev;
}
head->next = tail;
tail->prev = head;
resetTemp();
_size=0;
}
template <typename T>
list<T>::~list(){
// cout << "~list called for:"<<*this<<endl;
clear();
delete head;
delete tail;
head = nullptr;tail = nullptr;temp = nullptr;
}
template <typename T>
int list<T>::append(const T& dta){
temp = new node(dta);
tempindex = _size;

tail->prev->next = temp;
temp->prev = tail->prev;
temp->next = tail;
tail->prev = temp;
_size++;
return 0;
}
template <typename T>
typename list<T>::node* list<T>::get(int i){
if(i>=_size||i<-_size){
LOG("index out range");
exit(-1);
return 0;//这是个无效值
}
int mindis = 0x7fffffff;
int minway = 0;
if(dis(i,0)<mindis)
{mindis = dis(i, 0);minway = 1;}
if(dis(i, -_size)<mindis)
{mindis = dis(i, -_size);minway = 2;}
if(dis(i, _size-1)<mindis)
{mindis = dis(i, _size-1);minway = 3;}
if(dis(i, -1)<mindis)
{mindis = dis(i, -1);minway = 4;}
if(dis(i,tempindex)<mindis)
{mindis = dis(i,tempindex);minway = 5;}
if(dis(i+_size,tempindex)<mindis)
{mindis = dis(i,tempindex);minway = 6;}
switch (minway) {
case 1:return getFromHead(i);
case 2:return getFromHead(i+_size);
case 3:return getFromTail(i-_size);
case 4:return getFromTail(i);
case 5:return getFromTemp(i);
default:return getFromTemp(i+_size);
}

}
template <typename T>
typename list<T>::node* list<T>::getFromHead(int targeti){
// LOG("GFH called\n");
temp = head->next;
int i=0;
while(i!=targeti){
temp = temp->next;
i++;
}
tempindex = targeti;
return temp;
}
template <typename T>
typename list<T>::node* list<T>::getFromTail(int negativeTargeti){
// LOG("GFT called\n");
temp = tail->prev;
int i=-1;
while(i!=negativeTargeti){
temp = temp->prev;
i--;
}
tempindex = negativeTargeti+_size;
return temp;
}
template <typename T>
typename list<T>::node* list<T>::getFromTemp(int targeti){
// LOG("GFTMP called\n");
while(targeti>tempindex)
{
temp = temp->next;
tempindex++;
}
while(targeti<tempindex){
temp = temp->prev;
tempindex--;
}
return temp;
}
template <typename T>
void list<T>::swap(int ia,int ib){
node* a = get(ia);
node* b = get(ib);
swap(a,b);
tempindex = ia;//temp指向b,b的下标变为了ia.
}
template <typename T>
void list<T>::swap(node *a,node *b){
node *anext = a->next;
node *bnext = b->next;
node *aprev = a->prev;
node *bprev = b->prev;
if(a->next==b){
b->prev = aprev;
a->next = bnext;
b->next = a;
a->prev = b;
bnext->prev = a;
aprev->next = b;
}
else if(a->prev==b){
b->next = anext;
a->prev = bprev;
a->next = b;
b->prev = a;
anext->prev = b;
bprev->next = a;
}
else{
a->next = bnext;
b->next = anext;
a->prev = bprev;
b->prev = aprev;
anext->prev = b;
aprev->next = b;
bnext->prev = a;
bprev->next = a;
}
}
template <typename T>
list<T>& list<T>::insert(int i, const T& value){
node *t;
if(i>=_size){
//如果用户做了这样的输入,多半是想插入到末尾,而不是在最后一个位置的前面插入。故直接调用append
append(value);
return *this;
}
if(i<-_size){
i = 0;
}
t = get(i);
if(!t)return *this;
temp = new node(value);
t->prev->next = temp;
temp->prev = t->prev;
temp->next = t;
t->prev = temp;
_size++;
return *this;
}
template <typename T>
T list<T>::pop(int i){
node *t = get(i);
t->prev->next = t->next;
t->next->prev = t->prev;

T dta = t->data;

temp = t->next;//删除元素时,要把那个指向链表中间的temp指针指到一个在链上的节点。
_size--;
delete t;
return dta;
}
template <typename T>
void list<T>::remove(const T& target){
for (int i = 0; i < _size;)
{
if(get(i)->data==target){
pop(i);
}
else{
i++;
}
}
}

}

#endif