小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】双向链表 C++

作者：小小林熬夜学编程 | 2024-04-10 17:04:25

踩

【数据结构】双向链表 C++

一、什么是双向链表

1、定义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表的结构如图（图片来源于网络）：

2、时空复杂度

双向链表的空间复杂度是 $O (n)$ 的，其时间复杂度如下：

操作	时间复杂度
遍历	$O (n)$
访问指定节点	$O (1)$
删除指定编号节点	$O (n)$
删除指定位置节点	$O (1)$
在指定编号的节点后插入节点	$O (n)$
在指定位置的节点后插入节点	$O (1)$
查询前驱、后继	$O (1)$
修改指定编号节点的值	$O (n)$
修改指定位置节点的值	$O (1)$
交换两个 list 容器	$O (1)$

二、双向链表的基本操作

1. 定义双向链表节点

每个节点有三个值：

val：存储每个节点的权值；
last：指向每个节点的前面的第一个节点；
next：指向每个节点的后面的第一个节点；

代码如下：

template<typename T>
struct ListNode{
    T value;
    ListNode<T>* last;
    ListNode<T>* next;
    ListNode():value(0){
        last=NULL,next=NULL;
    }
    ListNode(const T &x):value(x){
        last=NULL,next=NULL;
    }
    ~ListNode(){
        value=0;
        delete last;
        delete next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 创建双向链表类

类里面包含两个节点和一个变量：

headnode：头节点，初始时前驱后继均为空，值为 $- 1$ ；
endnode：尾节点，初始时前驱后继均为空，值为 $- 1$ ；
listsize：记录双向链表的节点个数，不包含头尾节点；

代码如下：

template<typename T>
class list{
    private:
        unsigned listsize;
        ListNode<T>* headnode;
        ListNode<T>* endnode;
};
1
2
3
4
5
6
7

3. 初始化双向链表类

共有四种初始化方式：

list<类型名> a;：此时创建一个空的双向链表；
list<类型名> a(n);：此时创建一个大小为 $n$ 的双向链表，并将所有点的初始值赋为 $0$ ；
list<类型名> a(n,m)：此时创建一个大小为 $n$ 的双向链表，并将所有点的初始值赋为 $m$ ；
list<类型名> a={a1,a2,a3,...,an};：此时创建一个大小为 $n$ 的双向链表，并将第 $i$ 个节点的初始值赋为 $a_i$ ；

第一种初始化方式代码如下：

list():listsize(0){
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
}
1
2
3
4

第二种初始化方式代码如下：

list(const int &size_t):
    listsize(size_t) {
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(int i=0;i<listsize;++i){
        ListNode<T>* newnode=new ListNode<T>(0);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

第三种初始化方式代码如下：

list(
    const int &size_t,
    const int &val
):listsize(size_t){
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(int i=0;i<listsize;++i){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第四种初始化方式代码如下：

typedef std::initializer_list<T> lisval;
list(lisval vals){
    listsize=0;
    headnode=new ListNode<T>(-1);
    endnode=new ListNode<T>(-1);
    ListNode<T>* now=headnode;
    for(auto val:vals){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        newnode->last=now;now->next=newnode;
        now=now->next; ++listsize;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 一些基础的函数

这些函数是除了加点删点之外最常见的几个函数。

size()：获取链表的大小，返回一个 unsigned 值，表示当前链表中普通节点（非头尾节点）的个数。

代码如下：
```
unsigned size() const {
    return listsize;
}
1
2
3
```
empty()：返回当前链表是否为空，如果是，返回 true，否则返回 false。

代码如下：
```
bool empty() const {
    return listsize==0;
}
1
2
3
```

begin()：返回第一个普通节点。

代码如下：

ListNode<T>* begin(
) const {
    return headnode->next;
}
1
2
3
4

end()：返回尾指针。

代码如下：

ListNode<T>* end(
) const {
    return endnode;
}
1
2
3
4

rbegin()：返回最后一个普通节点。

代码如下：

ListNode<T>* rbegin(
) const {
    return endnode->last;
}
1
2
3
4

rend()：返回头指针。

代码如下：

ListNode<T>* rend(
) const {
    return headnode;
}
1
2
3
4

front()：返回第一个普通节点的值。

代码如下：

T front() const {
    return begin()->value;
}
1
2
3

back()：返回最后一个普通节点的值。

代码如下：
```
T back() const {
    return rbegin()->value;
}
1
2
3
```

print()：遍历并输出链表中每个普通节点的值，结尾换行。

代码如下：

void print(
) const {
    if(empty()) return;
    ListNode<T>* now=headnode->next;
    while(now->next!=NULL){
        printf("%d ",now->value);
        now=now->next;
    } putchar('\n');
}
1
2
3
4
5
6
7
8
9

swap(list<类型名> &b)：交换两个 list 容器，实际上是交换头尾指针和 $l i s t s i ze$ 。

代码如下：
```
void swap(list<T> &b){
    ListNode<T>* temp;
    temp=headnode;
    headnode=b.headnode;
    b.headnode=temp;
    temp=endnode;
    endnode=b.endnode;
    b.endnode=temp;
    unsigned size_t=listsize;
    listsize=b.listsize;
    b.listsize=size_t;
}
1
2
3
4
5
6
7
8
9
10
11
12
```

5. 插入节点

共四种方法，代码如下：

void push_back(
    const T &val
){ ++listsize;
    if(endnode->last==NULL){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        headnode->next=newnode;newnode->last=headnode;
        return;
    }
    ListNode<T>* pre=endnode->last;
    ListNode<T>* newnode=new ListNode<T>(val);
    pre->next=newnode;newnode->last=pre;
    newnode->next=endnode;endnode->last=newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

void push_front(
    const T &val
){ ++listsize;
    if(headnode->next==NULL){
        ListNode<T>* newnode=new ListNode<T>(val);
        endnode->last=newnode;newnode->next=endnode;
        headnode->next=newnode;newnode->last=headnode;
        return;
    }
    ListNode<T>* suf=headnode->next;
    ListNode<T>* newnode=new ListNode<T>(val);
    headnode->next=newnode;newnode->last=headnode;
    newnode->next=suf;suf->last=newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

void insert(
    const T &pos,
    const T &val
){  
    int nowpos=0;
    if(pos==0){
        push_front(val);
        ++listsize; return;
    } else if(pos>=listsize){
        push_back(val);
        ++listsize; return;
    }
    ListNode<T>* now=headnode->next;
    while(now->next!=NULL){
        ++nowpos;
        if(nowpos==pos){
            ListNode<T>* newnode=new ListNode<T>(val);
            ListNode<T>* suf=now->next;
            newnode->next=suf;suf->last=newnode;
            newnode->last=now;now->next=newnode;
            ++listsize; return;
        }
        now=now->next;
    }
}
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

void insert(
    ListNode<T>* now,
    const T &val
){
    if(now==endnode){push_back(val); return;}
    ListNode<T>* newnode=new ListNode<T>(val);
    ListNode<T>* suf=now->next;
    newnode->next=suf;suf->last=newnode;
    newnode->last=now;now->next=newnode;
    ++listsize; return;
}
1
2
3
4
5
6
7
8
9
10
11

6. 修改指定位置的值

两种方法，代码如下：

void reassign(
    const T &pos,
    const T &val
){
    if(pos>listsize) return;
    if(empty()||!pos) return;
    ListNode<T>* now=headnode->next;
    int nowpos=0;
    while(now->next!=NULL){
        ++nowpos;
        if(nowpos==pos){
            now->value=val;
            return;
        } now=now->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void reassign(
    ListNode<T>* now,
    const int &val
) const {
    now->value=val;
}
1
2
3
4
5
6

7.删除节点

和插入一样，共有四种，代码如下：

void pop_back(){
    if(empty()) return;
    ListNode<T>* now=endnode->last;
    ListNode<T>* pre=now->last;
    if(pre==headnode){
        endnode->last=NULL;
        headnode->last=NULL;
        --listsize; return;
    }
    endnode->last=pre;
    pre->next=endnode;
    --listsize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

void pop_front(){
    if(empty()) return;
    ListNode<T>* now=headnode->next;
    ListNode<T>* suf=now->next;
    if(suf==endnode){
        endnode->last=NULL;
        headnode->last=NULL;
        --listsize; return;
    }
    headnode->next=suf;
    suf->last=headnode;
    --listsize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

void erase(
    const int &pos
) {
    if(pos>listsize) return;
    if(empty()||!pos) return;
    ListNode<T>* now=headnode->next;
    int nowpos=0;
    while(now!=endnode){
        ++nowpos;
        if(nowpos==pos){
            ListNode<T>* pre=now->last;
            ListNode<T>* suf=now->next;
            if(pre==headnode||suf==endnode){
                endnode->last=NULL;
                headnode->next=NULL;
                delete now;
                --listsize; return;
            }
            pre->next=suf;
            suf->last=pre;
            delete now;
            --listsize; return;
        }
        now=now->next;
    }
}
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

void erase(
    ListNode<T>* now
){  
    if(now==headnode) return;
    if(now==endnode) return;
    if(empty()) return;
    ListNode<T>* pre=now->last;
    ListNode<T>* suf=now->next;
    if(pre==headnode||suf==endnode){
        endnode->last=NULL;
        headnode->last=NULL;
        --listsize; return;
    }
    pre->next=suf;
    suf->last=pre;
    --listsize; return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8. 注销双向链表类

遍历一遍，然后将每个节点都删除就可以了。

代码如下：

~list(){
    ListNode<T>* now=headnode->next;
    while(now!=NULL){
        ListNode<T>* nxt=now->next;
        delete now;now=nxt;
    } delete headnode; listsize=0;
}
1
2
3
4
5
6
7

三、完整代码

~~我知道你们只看这个~~

码风丑陋，不喜勿喷

#include<stdio.h>
#include<stdlib.h>
#include<initializer_list>
namespace STL{
    template<typename T>
    struct ListNode{
        T value;
        ListNode<T>* last;
        ListNode<T>* next;
        ListNode():value({}){
            last=NULL,next=NULL;
        }
        ListNode(const T &x):value(x){
            last=NULL,next=NULL;
        }
        ~ListNode(){
            // value={};
            last=NULL;
            next=NULL;
        }
    };
    template<typename T>
    class list{
        private:
            unsigned listsize;
            ListNode<T>* headnode;
            ListNode<T>* endnode;
        public:
            list():listsize(0){
                headnode=new ListNode<T>(T({-1}));
                endnode=new ListNode<T>(T({-1}));
            }
            list(const int &size_t):
                listsize(size_t) {
                headnode=new ListNode<T>(-1);
                endnode=new ListNode<T>(-1);
                ListNode<T>* now=headnode;
                for(int i=0;i<listsize;++i){
                    ListNode<T>* newnode=new ListNode<T>(0);
                    endnode->last=newnode;newnode->next=endnode;
                    newnode->last=now;now->next=newnode;
                    now=now->next;
                }
            }
            list(
                const int &size_t,
                const int &val
            ):listsize(size_t){
                headnode=new ListNode<T>(-1);
                endnode=new ListNode<T>(-1);
                ListNode<T>* now=headnode;
                for(int i=0;i<listsize;++i){
                    ListNode<T>* newnode=new ListNode<T>(val);
                    endnode->last=newnode;newnode->next=endnode;
                    newnode->last=now;now->next=newnode;
                    now=now->next;
                }
            }
            typedef std::initializer_list<T> lisval;
            list(lisval vals){
                listsize=0;
                headnode=new ListNode<T>(-1);
                endnode=new ListNode<T>(-1);
                ListNode<T>* now=headnode;
                for(auto val:vals){
                    ListNode<T>* newnode=new ListNode<T>(val);
                    endnode->last=newnode;newnode->next=endnode;
                    newnode->last=now;now->next=newnode;
                    now=now->next; ++listsize;
                }
            }
            unsigned size() const {
                return listsize;
            }
            bool empty() const {
                return listsize==0;
            }
            ListNode<T>* begin(
            ) const {
                return headnode->next;
            }
            ListNode<T>* end(
            ) const {
                return endnode;
            }
            ListNode<T>* rbegin(
            ) const {
                return endnode->last;
            }
            ListNode<T>* rend(
            ) const {
                return headnode;
            }
            T front() const {
                return begin()->value;
            }
            T back() const {
                return rbegin()->value;
            }
            void print(
            ) const {
                if(empty()) return;
                ListNode<T>* now=headnode->next;
                while(now->next!=NULL){
                    printf("%lld ",now->value);
                    now=now->next;
                } putchar('\n');
            }
            void push_back(
                const T &val
            ){ ++listsize;
                if(endnode->last==NULL){
                    ListNode<T>* newnode=new ListNode<T>(val);
                    endnode->last=newnode;newnode->next=endnode;
                    headnode->next=newnode;newnode->last=headnode;
                    return;
                }
                ListNode<T>* pre=endnode->last;
                ListNode<T>* newnode=new ListNode<T>(val);
                pre->next=newnode;newnode->last=pre;
                newnode->next=endnode;endnode->last=newnode;
            }
            void push_front(
                const T &val
            ){ ++listsize;
                if(headnode->next==NULL){
                    ListNode<T>* newnode=new ListNode<T>(val);
                    endnode->last=newnode;newnode->next=endnode;
                    headnode->next=newnode;newnode->last=headnode;
                    return;
                }
                ListNode<T>* suf=headnode->next;
                ListNode<T>* newnode=new ListNode<T>(val);
                headnode->next=newnode;newnode->last=headnode;
                newnode->next=suf;suf->last=newnode;
            }
            void insert(
                const T &pos,
                const T &val
            ){  
                int nowpos=0;
                if(pos==0){
                    push_front(val);
                    ++listsize; return;
                } else if(pos>=listsize){
                    push_back(val);
                    ++listsize; return;
                }
                ListNode<T>* now=headnode->next;
                while(now->next!=NULL){
                    ++nowpos;
                    if(nowpos==pos){
                        ListNode<T>* newnode=new ListNode<T>(val);
                        ListNode<T>* suf=now->next;
                        newnode->next=suf;suf->last=newnode;
                        newnode->last=now;now->next=newnode;
                        ++listsize; return;
                    }
                    now=now->next;
                }
            }
            void insert(
                ListNode<T>* now,
                const T &val
            ){
                if(now==endnode){push_back(val); return;}
                ListNode<T>* newnode=new ListNode<T>(val);
                ListNode<T>* suf=now->next;
                newnode->next=suf;suf->last=newnode;
                newnode->last=now;now->next=newnode;
                ++listsize; return;
            }
            void reassign(
                const T &pos,
                const T &val
            ){
                if(pos>listsize) return;
                if(empty()||!pos) return;
                ListNode<T>* now=headnode->next;
                int nowpos=0;
                while(now->next!=NULL){
                    ++nowpos;
                    if(nowpos==pos){
                        now->value=val;
                        return;
                    } now=now->next;
                }
            }
            void reassign(
                ListNode<T>* now,
                const int &val
            ) const {
                now->value=val;
            }
            void pop_back(){
                if(empty()) return;
                ListNode<T>* now=endnode->last;
                ListNode<T>* pre=now->last;
                if(pre==headnode){
                    endnode->last=NULL;
                    headnode->next=NULL;
                    delete now;
                    --listsize; return;
                }
                endnode->last=pre;
                pre->next=endnode;
                delete now;
                --listsize;
            }
            void pop_front(){
                if(empty()) return;
                ListNode<T>* now=headnode->next;
                ListNode<T>* suf=now->next;
                if(suf==endnode){
                    endnode->last=NULL;
                    headnode->next=NULL;
                    delete now;
                    --listsize; return;
                }
                headnode->next=suf;
                suf->last=headnode;
                delete now;
                --listsize;
            }
            void erase(
                const int &pos
            ) {
                if(pos>listsize) return;
                if(empty()||!pos) return;
                ListNode<T>* now=headnode->next;
                int nowpos=0;
                while(now!=endnode){
                    ++nowpos;
                    if(nowpos==pos){
                        ListNode<T>* pre=now->last;
                        ListNode<T>* suf=now->next;
                        if(pre==headnode||suf==endnode){
                            endnode->last=NULL;
                            headnode->next=NULL;
                            delete now;
                            --listsize; return;
                        }
                        pre->next=suf;
                        suf->last=pre;
                        delete now;
                        --listsize; return;
                    }
                    now=now->next;
                }
            }
            void erase(
                ListNode<T>* now
            ){  
                if(now==headnode) return;
                if(now==endnode) return;
                if(empty()) return;
                ListNode<T>* pre=now->last;
                ListNode<T>* suf=now->next;
                if(pre==headnode||suf==endnode){
                    endnode->last=NULL;
                    headnode->last=NULL;
                    delete now;
                    --listsize; return;
                }
                pre->next=suf;
                suf->last=pre;
                delete now;
                --listsize; return;
            }
            void swap(list<T> &b){
                ListNode<T>* temp;
                temp=headnode;
                headnode=b.headnode;
                b.headnode=temp;
                temp=endnode;
                endnode=b.endnode;
                b.endnode=temp;
                unsigned size_t=listsize;
                listsize=b.listsize;
                b.listsize=size_t;
            }
            ~list(){
                ListNode<T>* now=headnode->next;
                while(now!=NULL){
                    ListNode<T>* nxt=now->next;
                    delete now;now=nxt;
                } delete headnode;listsize=0;
            }
    };
}
using STL::list;

signed main(){

    system("pause");
}
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

~~给个赞再走吧~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/399974