【数据结构】双向链表及其基本操

双向链表（Doubly Linked List）及其基本操作

1. 简介

双向链表是一种常见的线性数据结构，它与单向链表相比具有双向遍历的优势。除了拥有指向后继节点的指针外，双向链表还拥有指向前驱节点的指针。这使得在双向链表中可以更有效地实现从后往前的遍历，而不像单向链表那样需要重新遍历整个链表。在某些场景下，双向链表能够更加高效地解决问题。

2. 创建双向链表

2.1 结构声明

#include<bits/stdc++.h>
using namespace std;

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
1
2
3
4
5
6
7
8
9
10

2.2 初始化双向链表(Init)

// 创建一个带头结点的双向循环链表
ListNode* ListInit() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode)); // 分配头结点内存空间
    head->data = -1; // 设定头结点数据为-1
    head->next = head; // 头结点的下一个指向自己，形成循环
    head->prev = head; // 头结点的上一个指向自己，形成循环
    return head; // 返回头结点
}
1
2
3
4
5
6
7
8

2.3 创建双向链表节点

// 创建一个新结点
ListNode* ListCreate(LTDataType x) {
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); // 分配新结点内存空间
    if (!newnode) {
        perror("fail"); // 内存分配失败则输出错误信息
        exit(-1); // 退出程序
    }

    newnode->data = x; // 设置新结点的数据
    newnode->next = NULL; // 设置新结点的下一个为NULL
    newnode->prev = NULL; // 设置新结点的上一个为NULL

    return newnode; // 返回新结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.4 插入节点(Insert)

在双向链表中，由于每个节点都有指向其前一个节点和后一个节点的引用，因此可以更高效地在任意位置插入或删除节点，而不需要像单链表那样遍历查找前一个节点。

关键在于它们的顺序，由于第②步和第③步都用到了p->next。如果第④步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

// 在特定位置插入元素
void ListInsert(ListNode* pos, LTDataType x) {
    assert(pos); // 检查位置是否存在
    ListNode* newnode = ListCreate(x); // 创建新结点

    newnode->next = pos; // 新结点的下一个指向位置结点
    pos->prev->next = newnode; // 位置结点的上一个的下一个指向新结点
    newnode->prev = pos->prev; // 新结点的上一个指向位置结点的上一个
    pos->prev = newnode; // 位置结点的上一个指向新结点
}
	
1
2
3
4
5
6
7
8
9
10
11

2.5 查找结点（Find)

定义了一个名为p的结构体指针，并初始化为指向双链表中的头节点之后的第一个元素。然后，该函数会遍历整个双链表， 当p指向的数据等于给定的值x时，立即返回p。否则，继续将p向后移动一位。一旦p重新回到头节点，循环结束且并未找到匹配项，则返回NULL。

// 查找特定元素
ListNode* ListFind(ListNode* head, LTDataType x) {
    assert(head); // 检查头结点是否存在

    ListNode* p = head->next; // 从头结点的下一个开始

    while (p != head) { // 遍历链表直到回到头结点
        if (p->data == x) // 如果找到了相同的数据
            return p; // 返回该结点
        p = p->next; // 移动到下一个结点
    }
    return NULL; // 如果未找到则返回NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.6 删除节点(Erase)

在双向链表中，删除节点时不需要像单链表那样遍历查找前一个节点，因为每个节点都有指向前一个节点的引用，所以可以更高效地进行删除操作。

我们要删除指定位置，可以定义一个结构体指针pre保存要删除位置的前一个位置，定义一个结构体指针next保存要删除位置的后一个位置。然后free掉pos，让pre的next指向next，让next的prev指向pre。

// 删除特定位置的元素
void ListErase(ListNode* pos) {
    assert(pos); // 检查位置是否存在

    ListNode* pre = pos->prev; // 找到位置结点的上一个
    ListNode* next = pos->next; // 找到位置结点的下一个

    pre->next = next; // 位置结点的上一个的下一个指向位置结点的下一个
    next->prev = pre; // 位置结点的下一个的上一个指向位置结点的上一个
    free(pos); // 释放位置结点
    pos = NULL; // 将位置结点置为NULL
}

1
2
3
4
5
6
7
8
9
10
11
12
13

2.7 打印双向链表

// 打印链表
void ListPrint(ListNode* head) {
    ListNode* p = head->next; // 从头结点的下一个开始
    if (p == head) // 如果下一个是头结点则说明链表为空
        cout << "NULL"; // 打印NULL
    while (p != head) { // 遍历链表直到回到头结点
        cout << p->data << "->"; // 打印结点数据
        p = p->next; // 移动到下一个结点
    }
    cout << endl; // 换行
}
1
2
3
4
5
6
7
8
9
10
11

2.8 销毁双链表

我们需要释放整个双链表，所以我们需要从第一个节点开始遍历列表。我们将当前节点和下一个节点分别存储在cur和q(保存下一个结点)中。每次迭代都将当前节点设置为下一个节点，直到遍历到头节点为止。此时，我们会释放掉最后一个未被释放的节点并返回。

// 销毁链表
void ListDestory(ListNode* head) {
    assert(head); // 检查头结点是否存在
    ListNode* p = head->next; // 从头结点的下一个开始

    while (p != head) { // 遍历链表直到回到头结点
        ListNode* q = p->next; // 保存下一个结点
        free(p); // 释放当前结点内存
        p = q; // 移动到下一个结点
    }

    free(head); // 释放头结点内存
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 总代码

#include<bits/stdc++.h>
using namespace std;

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

```cpp
// 创建一个带头结点的双向循环链表
ListNode* ListInit() {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode)); // 分配头结点内存空间
    head->data = -1; // 设定头结点数据为-1
    head->next = head; // 头结点的下一个指向自己，形成循环
    head->prev = head; // 头结点的上一个指向自己，形成循环
    return head; // 返回头结点
}

// 创建一个新结点
ListNode* ListCreate(LTDataType x) {
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); // 分配新结点内存空间
    if (!newnode) {
        perror("fail"); // 内存分配失败则输出错误信息
        exit(-1); // 退出程序
    }

    newnode->data = x; // 设置新结点的数据
    newnode->next = NULL; // 设置新结点的下一个为NULL
    newnode->prev = NULL; // 设置新结点的上一个为NULL

    return newnode; // 返回新结点
}

// 打印链表
void ListPrint(ListNode* head) {
    ListNode* p = head->next; // 从头结点的下一个开始
    if (p == head) // 如果下一个是头结点则说明链表为空
        cout << "NULL"; // 打印NULL
    while (p != head) { // 遍历链表直到回到头结点
        cout << p->data << "->"; // 打印结点数据
        p = p->next; // 移动到下一个结点
    }
    cout << endl; // 换行
}

// 在链表末尾插入元素
void ListPushBack(ListNode* head, LTDataType x) {
    assert(head); // 检查头结点是否存在

    ListNode* newnode = ListCreate(x); // 创建新结点

    ListNode* tail = head->prev; // 找到链表末尾结点

    tail->next = newnode; // 末尾结点的下一个指向新结点
    newnode->prev = tail; // 新结点的上一个指向末尾结点
    newnode->next = head; // 新结点的下一个指向头结点
    head->prev = newnode; // 头结点的上一个指向新结点
}

// 删除链表末尾元素
void ListPopBack(ListNode* head) {
    assert(head); // 检查头结点是否存在
    assert(head->next != head); // 检查链表是否非空

    ListNode* tail = head->prev; // 找到链表末尾结点

    head->prev = tail->prev; // 头结点的上一个指向末尾结点的上一个
    tail->prev->next = head; // 末尾结点的上一个的下一个指向头结点

    free(tail); // 释放末尾结点内存
    tail = NULL; // 将末尾结点置为NULL
}

// 在链表开头插入元素
void ListPushFront(ListNode* head, LTDataType x) {
    assert(head); // 检查头结点是否存在

    ListNode* next = head->next; // 找到头结点的下一个

    ListNode* newnode = ListCreate(x); // 创建新结点

    newnode->next = next; // 新结点的下一个指向原先的第一个结点
    next->prev = newnode; // 原先的第一个结点的上一个指向新结点

    head->next = newnode; // 头结点的下一个指向新结点
    newnode->prev = head; // 新结点的上一个指向头结点
}

// 删除链表开头元素
void ListPopFront(ListNode* head) {
    assert(head); // 检查头结点是否存在
    assert(head->next != head); // 检查链表是否非空

    ListNode* p = head->next; // 找到第一个结点
    ListNode* next = p->next; // 找到第一个结点的下一个结点

    head->next = next; // 头结点的下一个指向第一个结点的下一个
    next->prev = head; // 第一个结点的下一个的上一个指向头结点

    free(p); // 释放第一个结点内存
    p = NULL; // 将第一个结点置为NULL
}

// 查找特定元素
ListNode* ListFind(ListNode* head, LTDataType x) {
    assert(head); // 检查头结点是否存在

    ListNode* p = head->next; // 从头结点的下一个开始

    while (p != head) { // 遍历链表直到回到头结点
        if (p->data == x) // 如果找到了相同的数据
            return p; // 返回该结点
        p = p->next; // 移动到下一个结点
    }
    return NULL; // 如果未找到则返回NULL
}

// 在特定位置插入元素
void ListInsert(ListNode* pos, LTDataType x) {
    assert(pos); // 检查位置是否存在

    ListNode* newnode = ListCreate(x); // 创建新结点

    newnode->next = pos; // 新结点的下一个指向位置结点
    pos->prev->next = newnode; // 位置结点的上一个的下一个指向新结点
    newnode->prev = pos->prev; // 新结点的上一个指向位置结点的上一个
    pos->prev = newnode; // 位置结点的上一个指向新结点
}

// 删除特定位置的元素
void ListErase(ListNode* pos) {
    assert(pos); // 检查位置是否存在

    ListNode* pre = pos->prev; // 找到位置结点的上一个
    ListNode* next = pos->next; // 找到位置结点的下一个

    pre->next = next; // 位置结点的上一个的下一个指向位置结点的下一个
    next->prev = pre; // 位置结点的下一个的上一个指向位置结点的上一个
    free(pos); // 释放位置结点
    ```cpp
    pos = NULL; // 将位置结点置为NULL
}

// 销毁链表
void ListDestory(ListNode* head) {
    assert(head); // 检查头结点是否存在

    ListNode* p = head->next; // 从头结点的下一个开始

    while (p != head) { // 遍历链表直到回到头结点
        ListNode* q = p->next; // 保存下一个结点
        free(p); // 释放当前结点内存
        p = q; // 移动到下一个结点
    }

    free(head); // 释放头结点内存
}
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

结论

双向链表提供了更多的灵活性，能够支持更多的操作，但相应地也会占用更多的内存空间。在需要频繁进行双向遍历的场景下，双向链表是一个非常实用的数据结构。