线性表之双向链表

1. 双向链表的结构

对于单向链表和单向循环链表而言有一个共同的特点，就是链表的每个节点都只有一个指向后继节点的指针，通过这个指针我们就可以从前往后完成对链表的遍历。但是开弓没有回头箭，遍历到尾节点之后再想要回到头结点，是无能为力的。

1.1 双向链表的节点

为了克服链表单向性这一缺点，聪明的程序猿们便进行了改进，设计出了双向链表。双向链表（Doubly Linked List）是一种常见的数据结构，与单向链表不同的是，双向链表中的每个节点包含两个指针，一个指向前驱节点，一个指向后继节点。双向链表的这种特性使得我们可以从任意节点高效地向前或向后遍历。

假设双向链表的节点存储的是整形数据，那么该节点的定义如下：

1
2
3
4
5
6
7
// 定义一个节点，此为 C++ 语法
struct Node
{
    int data = 0;
    Node* next = nullptr;
    Node* prev = nullptr;
};

双向链表的节点结构包含三个部分：

  • 数据域（data）：存储节点的值
  • 前驱指针（prev）：指向前一个节点
  • 后继指针（next）：指向后一个节点

在操作双向链表的时候通常会定义两个辅助指针：头节点指针和尾节点指针，头指针指向链表的第一个节点，尾指针指向链表的最后一个节点。

和单向链表一样，双向链表也可以分为带头结点的双向链表和不带头结点的双向链表，它们在实现细节和使用上存在一些差异。以下是对它们的详细比较：

1.2 带头结点的双向链表

  • 定义

    • 带头结点的双向链表包含一个特殊的头结点，该头结点不存储有效数据，仅用于指示链表的开始位置。

    • 头结点的前驱指向nullptr，最后一个链表节点的后继也指向nullptr。

  • 优点

    • 简化操作：由于有头结点，不论链表是否为空，第一个节点的前驱和最后一个节点的后继节点都可以统一处理，简化了插入、删除等操作的代码逻辑。
    • 减少边界检查：插入和删除操作不需要特别判断是否在链表头部或尾部进行，有头结点作为统一的起始点，减少了边界条件的检查。

  • 缺点

    • 额外空间：需要额外的空间来存储头结点，这在一定程度上增加了内存开销。
    • 稍复杂的实现：需要特别注意头结点的初始化和管理。

1.3 不带头结点的双向链表

  • 定义

    • 不带头结点的双向链表从第一个实际存储数据的节点开始

    • 第一个节点的前驱和最后一个节点的后继都指向nullptr

  • 优点

    • 节省空间：不需要额外的头结点，节省了一些内存空间
    • 简单的结构：结构更加直接，容易理解

  • 缺点

    • 复杂的操作：插入和删除操作需要特别处理头部和尾部的边界条件，增加了代码的复杂度
    • 更多的边界检查：需要在每次操作时检查链表是否为空，头部和尾部的特殊情况处理起来较为繁琐

2. 双向链表的操作

2.1 链表的遍历

由于双向链表的节点中有前驱和后继指针，所以在遍历它的时候有两种方式：正向遍历和反向遍历。

  • 正向遍历双向链表的过程（从头到尾）：
    1. 从第一个数据节点开始
      • 带头结点：从头结点的后继节点开始遍历
      • 不带头结点：从第一个节点开始遍历
    2. 访问当前节点的数据，并通过next指针移动到下一个节点
    3. 重复步骤2，直到到达链表的末尾（即当前节点的next为nullptr）
  • 反向遍历双向链表的过程（从尾到头）：
    1. 从尾节点开始（前提条件：需要先找到尾节点）
    2. 访问当前节点的数据，并通过prev指针移动到上一个节点
    3. 重复步骤2，直到到达链表的头部，判定条件为：
      • 带头结点：当前节点为头结点
      • 不带头结点：当前节点的prev为nullptr

2.2 链表的插入

2.2.1 带头结点的插入

  • 场景1：在头部和中间位置插入新节点

    对于带头节点的链表而言，在头部插入节点就是把新的数据节点作为链表的第一个数据节点，它是头结点的后继节点。

    在链表的头部和中间位置（pos）插入新节点需要分以下几步：

    1. 创建一个新的节点，并初始化，记作newNode
    2. 遍历链表找到pos-1位置的节点，记作preNode
    3. 将新节点的后继节点设置为pos位置的节点，也就是newNode->next = preNode->next
    4. 将新节点的前驱节点设置为pos-1位置的节点，也就是newNode->prev = preNode
    5. 重置pos位置节点的前驱，设置为newNode节点，也就是preNode->next->prev = newNode
    6. 重置preNode节点的后继，设置为newNode，即：preNode->next = newNode

    温馨提示：第5、6步不能放到第3、4步之前处理。

    下图是将新节点插入到链表的非第一个数据节点的位置：

    下图是将新节点作为第一个数据节点插入到链表中：

    可以看到，在以上两种情况下插入新节点的处理逻辑是相同的。

  • 场景2：在尾部插入新节点

    在链表的尾部添加新节点就是让它作为原来的尾节点的后继，新节点的前驱是原来的尾节点。主要的操作步骤如下：

    1. 遍历链表并找到它的尾节点，记作tailNode
    2. 创建一个新的链表节点，记作newNode，并设置它的后继，有两种方式：
      • newNode->next = nullptr
      • newNode->next = tailNode->next
    3. 将newNode节点的前驱设置为tailNode，即：newNode->prev = tailNode
    4. 更新tailNode节点的后继节点，tailNode->next = newNode
    image-20240627004429447

2.2.2 不带头结点的插入

如果链表没有头结点在进行插入操作的时候就需要判断更多的情况。

在下面描述中，提及的头结点即链表的第一个数据节点。

  • 场景1：空链表

    如果链表为空链表，那么新添加的节点就是链表的第一个数据节点

    • 如果有头指针需要让头指针指向这个新添加的节点
    • 新添加的节点的前驱和后继都是nullptr
    image-20240627005157707

  • 场景2：在头部插入新节点

    将新的节点插入到链表头部的操作相对简单，操作流程如下：

    1. 创建一个新的链表节点，记作newNode
    2. 让newNode节点的next域指针指向原来的链表头结点
    3. 将newNode节点的前驱设置为nullptr
    4. 将旧的头结点的前驱设置为newNode
    5. 如果有头指针需要让头指针前移，指向这个新的头结点newNode

  • 场景3：在链表中间位置插入新节点

    在链表的中间位置（pos）插入新节点的操作步骤如下：

    1. 创建一个新的节点，并初始化，记作newNode
    2. 遍历链表找到pos-1位置的节点，记作preNode
    3. 将新节点的后继节点设置为pos位置的节点，也就是newNode->next = preNode->next
    4. 将新节点的前驱节点设置为pos-1位置的节点，也就是newNode->prev = preNode
    5. 重置pos位置节点的前驱，设置为newNode节点，也就是preNode->next->prev = newNode
    6. 重置preNode节点的后继，设置为newNode，即：preNode->next = newNode

    温馨提示：第5、6步不能放到第3、4步之前处理。

  • 场景4：在链表尾部插入新节点

    在链表的尾部添加新节点主要的操作步骤如下：

    1. 遍历链表并找到它的尾节点，记作tailNode
    2. 创建一个新的链表节点，记作newNode，并设置它的后继，有两种方式：
      • newNode->next = nullptr
      • newNode->next = tailNode->next
    3. 将newNode节点的前驱设置为tailNode，即：newNode->prev = tailNode
    4. 更新tailNode节点的后继节点，tailNode->next = newNode

2.3 链表的删除

2.3.1 带头结点的删除

  • 场景1：删除头部和中间位置的节点

    对于带头结点的链表而言，所谓的删除头部节点指的就是删除链表中的第一个数据节点。

    删除头部和中间位置（pos）的节点的处理流程如下：

    1. 遍历链表，搜索链表的节点，找到要删除的节点的上一个节点（pos-1），记作preNode
    2. 通过preNode找到要删除的节点，记作delNode
      • delNode = preNode->next
    3. 更新preNode节点的后继为pos+1位置的节点，即：preNode->next = delNode->next
    4. 更新pos+1位置节点的前驱为preNode，即：delNode->next->prev = prevNode
    5. 释放delNode节点指向的内存资源

    下图为删除链表第一个数据节点的示意图:

    下图为删除链表中间位置的数据节点的示意图:

  • 场景2：删除尾部节点

    删除链表尾部节点的处理流程如下:

    1. 遍历链表找到链表的倒数第二个（pos-1位置）节点，记作preNode
    2. 通过preNode找到要删除的节点，记作delNode
      • delNode = preNode->next
    3. 让preNode节点的后继指针指向空，有两种处理方式
      • preNode->next = nullptr
      • preNode->next = delNode->next
    4. 释放delNode节点指向的内存资源

2.3.2 不带头结点的删除

如果是不带头结点的链表，在进行节点删除的时候会出现链表为空（没有任何节点）的情况，对于这种特殊情况需要单独进行处理。

  • 场景1：删除链表中唯一的数据节点

    删除了链表中唯一的数据节点之后，链表中就没有任何节点了。另外，如果有头指针，在进行了删除操作之后，应该让它指向一个空地址。

  • 场景2：删除链表的第一个数据节点

    删除链表的第一个数据节点的操作如下：

    1. 通过头指针找到链表的第一个数据节点，将其记作delNode
    2. 找到delNode节点的后继，记作nextNode，即：nextNode = delNode->next
    3. 重置nextNode节点的前驱，设置为nullptr
    4. 链表头指针后移一个节点，指向nextNode
    5. 释放delNode节点占用的内存资源

  • 场景3：删除链表中间位置的数据节点

    删除链表中间位置的节点的处理流程如下：

    1. 遍历链表，搜索链表的节点，找到要删除的节点的上一个节点（pos-1），记作preNode
    2. 通过preNode找到要删除的节点，记作delNode
      • delNode = preNode->next
    3. 更新preNode节点的后继为pos+1位置的节点，即：preNode->next = delNode->next
    4. 更新pos+1位置节点的前驱为preNode，即：delNode->next->prev = prevNode
    5. 释放delNode节点指向的内存资源

  • 场景4：删除链表尾部的数据节点

    删除链表尾部节点的处理流程如下:

    1. 遍历链表找到链表的倒数第二个（pos-1位置）节点，记作preNode
    2. 通过preNode找到要删除的节点，记作delNode
      • delNode = preNode->next
    3. 将preNode节点的后继指针设置为空，有两种处理方式
      • preNode->next = nullptr
      • preNode->next = delNode->next
    4. 释放delNode节点指向的内存资源

3. 双向链表的实现

3.1 带头结点的双向链表

在进行链表操作的时候，为了能够提高操作效率以及使用起来更加方便，除了给链表添加一个头指针以外，还可以提供一个尾指针，有了尾指针之后访问链表尾节点的时候时间复杂度就从O(n)变成了O(1)。同理，给链表添加了长度成员之后，每次想要得到链表的长度，就不需要进行遍历了。

头文件

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
// DoubleLinkList.h
#pragma once
struct Node
{
    Node(int value) : data(value) {}
    int data;
    Node* next = nullptr;  
    Node* prior = nullptr; 
};

// 双向链表
class DLinkList
{
public:
    DLinkList();
    ~DLinkList();
    // 判断链表是否为空
    bool isEmpty();
    // 得到链表长度
    int length();
    // 数据添加到链表头部
    void prepend(int data);
    // 数据添加到链表尾部
    void append(int data);
    // 数据插入到链表任意位置, 第一个数据元素 pos=1
    bool insert(int pos, int data);
    // 搜索数值, 返回节点和位置, 没找到返回nullptr
    Node* find(int data, int& pos);
    // 删除节点
    bool remove(int pos);
    // 遍历链表
    void display();

private:
    int m_length = 0;
    Node* m_head = nullptr;
    Node* m_tail = nullptr;
};

关于上面链表类中的各个操作函数都有对应的注释说明，在此就不再赘述了。

源文件

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
// DoubleLinkList.cpp
#include "DoubleLinkList.h"
#include <iostream>
using namespace std;

DLinkList::DLinkList() : m_head(new Node(0))
{
    m_head->next = nullptr;
    m_head->prior = nullptr;
    m_tail = m_head;
}

DLinkList::~DLinkList()
{
    while (length())
    {
        remove(1);
    }
    delete m_head;
}

bool DLinkList::isEmpty()
{
    return m_head->next == nullptr;
}

int DLinkList::length()
{
    return m_length;
}

void DLinkList::prepend(int data)
{
    Node* node = new Node(data);
    node->next = m_head->next;
    node->prior = m_head;
    if (m_head->next != nullptr)
    {
        m_head->next->prior = node;
    }
    else
    {
        m_tail = node;
    }
    m_head->next = node;
    m_length++;
}

void DLinkList::append(int data)
{
    Node* node = new Node(data);
    m_tail->next = node;
    node->prior = m_tail;
    m_tail = node;
    m_length++;
}

bool DLinkList::insert(int pos, int data)
{
    if (pos<1 || pos>length() + 1)
    {
        cout << "链表插入数据失败, 无效的位置" << endl;
        return false;
    }
    Node* p = m_head;
    int j = 0;
    while (j < pos - 1 && p != nullptr)
    {
        p = p->next;
        j++;
    }
    Node* pNode = new Node(data);
    pNode->next = p->next;
    pNode->prior = p;
    if (m_head->next != nullptr)
    {
        p->next->prior = pNode;
    }
    else
    {
        m_tail = pNode;
    }
    p->next = pNode;
    m_length++;

    return true;
}

Node* DLinkList::find(int data, int& pos)
{
    pos = 1;
    Node* p = m_head->next;
    while (p != nullptr && p->data != data)
    {
        p = p->next;
        pos++;
    }
    return p;
}

bool DLinkList::remove(int pos)
{
    if (pos<1 || pos>length())
    {
        cout << "删除链表节点失败, 位置无效" << endl;
        return false;
    }
    Node* p = m_head;
    for (int i = 0; i < pos - 1; ++i)
    {
        p = p->next;
    }
    Node* delNode = p->next;
    p->next = delNode->next;
    if (delNode->next != nullptr)
    {
        delNode->next->prior = p;
    }
    else
    {
        m_tail = p;
    }
    cout << "删除链表节点: " << delNode->data << endl;
    delete delNode;
    m_length--;

    return true;
}

void DLinkList::display()
{
    if (m_head->next == nullptr)
    {
        cout << "空链表" << endl;
        return;
    }
    cout << "从头到尾遍历: " << endl;
    for (Node* item = m_head->next; item != nullptr; item = item->next)
    {
        cout << item->data << " ";
    }
    cout << endl;

    cout << "从尾到头遍历: " << endl;
    for (Node* item = m_tail; item != m_head; item = item->prior)
    {
        cout << item->data << " ";
    }
    cout << endl;
}

int main()
{
    DLinkList lst;
    lst.insert(1, 12);
    lst.append(8);
    lst.insert(2, 7);
    lst.insert(2, 6);
    lst.insert(1, 5);
    lst.insert(2, 4);
    lst.append(3);
    lst.prepend(9);
    lst.display();
    cout << "当前链表的长度为: " << lst.length() << endl;
    cout << "========== 测试搜索和删除=========" << endl;
    DLinkList lst1;
    lst1.append(10);
    lst1.append(20);
    lst1.append(30);
    lst1.append(40);
    lst1.append(50);
    lst1.display();
    int pos;
    Node* node = lst1.find(10, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(30, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(50, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();
    cout << "当前链表的长度为: " << lst1.length() << endl;

    return 0;
}

在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部（第一个数据节点）、中间、尾部。

执行程序，终端输出的信息为：

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
从头到尾遍历:
9 5 4 12 6 7 8 3
从尾到头遍历:
3 8 7 6 12 4 5 9
当前链表的长度为: 8
========== 测试搜索和删除=========
从头到尾遍历:
10 20 30 40 50
从尾到头遍历:
50 40 30 20 10
搜索到的节点位置: 1, 值为: 10
删除链表节点: 10
从头到尾遍历:
20 30 40 50
从尾到头遍历:
50 40 30 20
搜索到的节点位置: 2, 值为: 30
删除链表节点: 30
从头到尾遍历:
20 40 50
从尾到头遍历:
50 40 20
搜索到的节点位置: 3, 值为: 50
删除链表节点: 50
从头到尾遍历:
20 40
从尾到头遍历:
40 20
当前链表的长度为: 2
删除链表节点: 20
删除链表节点: 40
删除链表节点: 9
删除链表节点: 5
删除链表节点: 4
删除链表节点: 12
删除链表节点: 6
删除链表节点: 7
删除链表节点: 8
删除链表节点: 3

对于上面链表类中的某些API函数带有一个整形的节点位置pos，该位置的值是从1开始的，也就是说链表中第一个数据节点的位置是1。

3.2 不带头节点的双向链表

头文件

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
// DoubleLinkList1.h
#pragma once
struct Node
{
    Node(int value) : data(value) {}
    int data;
    Node* next; 
    Node* prior;
};

class DLinkList1
{
public:
    DLinkList1();
    ~DLinkList1();
    // 判断链表是否为空
    bool isEmpty();
    // 得到链表长度
    int length();
    // 数据添加到链表头部
    void prepend(int data);
    // 数据添加到链表尾部
    void append(int data);
    // 数据插入到链表任意位置, 第一个数据元素 pos=1
    bool insert(int pos, int data);
    // 搜索数值, 返回节点和位置, 没找到返回nullptr
    Node* find(int data, int& pos);
    // 删除节点
    bool remove(int pos);
    // 遍历链表
    void display();

private:
    int m_length = 0;
    Node* m_head = nullptr;
    Node* m_tail = nullptr;
};

源文件

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
// DoubleLinkList1.cpp
#include "DoubleLinkList1.h"
#include "test.h"
#include <iostream>
using namespace std;

DLinkList1::DLinkList1()
{
}

DLinkList1::~DLinkList1()
{
    while (length())
    {
        remove(1);
    }
}

bool DLinkList1::isEmpty()
{
    return m_head == nullptr;
}

int DLinkList1::length()
{
    return m_length;
}

void DLinkList1::prepend(int data)
{
    Node* pNode = new Node(data);
    pNode->next = m_head;
    pNode->prior = nullptr;
    if (m_head != nullptr)
    {
        m_head->prior = pNode;
    }
    else
    {
        m_tail = pNode;
    }
    m_head = pNode;
    m_length++;
}

void DLinkList1::append(int data)
{
    Node* node = new Node(data);
    node->prior = node->next = nullptr;
    if (m_head == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        node->prior = m_tail;
        m_tail->next = node;
        m_tail = node;
    }
    m_length++;
}

bool DLinkList1::insert(int pos, int data)
{
    if (pos<1 || pos>length() + 1)
    {
        cout << "链表插入数据失败, 无效的位置" << endl;
        return false;
    }
    Node* pNode = new Node(data);
    if (pos == 1)
    {
        prepend(data);
        return true;
    }
    else
    {
        Node* p = m_head;
        int j = 1;
        while (j < pos - 1)
        {
            p = p->next;
            j++;
        }
        Node* pNode = new Node(data);
        pNode->next = p->next;
        pNode->prior = p;
        if (p->next != nullptr)
        {
            p->next->prior = pNode;
        }
        else
        {
            m_tail = pNode;
        }
        p->next = pNode;
        m_length++;
    }
    return true;
}

Node* DLinkList1::find(int data, int& pos)
{
    pos = 1;
    Node* p = m_head;
    while (p != nullptr && p->data != data)
    {
        p = p->next;
        pos++;
    }
    return p;
}

bool DLinkList1::remove(int pos)
{
    if (pos<1 || pos>length())
    {
        cout << "删除链表节点失败, 位置无效" << endl;
        return false;
    }
    if (pos == 1)
    {
        Node* p = m_head;
        m_head = m_head->next;
        if (m_head != nullptr)
        {
            m_head->prior = nullptr;
        }
        cout << "删除链表节点: " << p->data << endl;
        delete p;
    }
    else
    {
        Node* p = m_head;
        int j = 1;
        while (j < pos - 1)
        {
            p = p->next;
            j++;
        }
        Node* delNode = p->next;
        p->next = delNode->next;
        if (p->next != nullptr)
        {
            p->next->prior = p;
        }
        else
        {
            m_tail = p;
        }
        cout << "删除链表节点: " << delNode->data << endl;
        delete delNode;
    }
    m_length--;
    return true;
}

void DLinkList1::display()
{
    if (m_head == nullptr)
    {
        cout << "空链表" << endl;
        return;
    }
    cout << "从头到尾遍历: " << endl;
    for (Node* item = m_head; item != nullptr; item = item->next)
    {
        cout << item->data << " ";
    }
    cout << endl;

    cout << "从尾到头遍历: " << endl;
    for (Node* item = m_tail; item != nullptr; item = item->prior)
    {
        cout << item->data << " ";
    }
    cout << endl;
}

int main()
{
    DLinkList1 lst;
    lst.insert(1, 12);
    lst.append(8);
    lst.insert(2, 7);
    lst.insert(2, 6);
    lst.insert(1, 5);
    lst.insert(2, 4);
    lst.append(3);
    lst.prepend(9);
    lst.display();
    cout << "当前链表的长度为: " << lst.length() << endl;
    cout << "========== 测试搜索和删除=========" << endl;
    DLinkList1 lst1;
    lst1.append(10);
    lst1.append(20);
    lst1.append(30);
    lst1.append(40);
    lst1.append(50);
    lst1.display();
    int pos;
    Node* node = lst1.find(10, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(30, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();

    node = lst1.find(50, pos);
    cout << "搜索到的节点位置: " << pos << ", 值为: " << node->data << endl;
    lst1.remove(pos);
    lst1.display();
    cout << "当前链表的长度为: " << lst1.length() << endl;

    return 0;
}

在上面的代码中，insert和remove函数支持操作的链表位置有三处：头部、中间、尾部。

执行程序，终端打印的信息如下：

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
从头到尾遍历:
9 5 4 12 6 7 8 3
从尾到头遍历:
3 8 7 6 12 4 5 9
当前链表的长度为: 8
========== 测试搜索和删除=========
从头到尾遍历:
10 20 30 40 50
从尾到头遍历:
50 40 30 20 10
搜索到的节点位置: 1, 值为: 10
删除链表节点: 10
从头到尾遍历:
20 30 40 50
从尾到头遍历:
50 40 30 20
搜索到的节点位置: 2, 值为: 30
删除链表节点: 30
从头到尾遍历:
20 40 50
从尾到头遍历:
50 40 20
搜索到的节点位置: 3, 值为: 50
删除链表节点: 50
从头到尾遍历:
20 40
从尾到头遍历:
40 20
当前链表的长度为: 2
删除链表节点: 20
删除链表节点: 40
删除链表节点: 9
删除链表节点: 5
删除链表节点: 4
删除链表节点: 12
删除链表节点: 6
删除链表节点: 7
删除链表节点: 8
删除链表节点: 3

和单向链表一样，通过对上面两份代码的代码量进行比较，可以很直观地看出不带头结点的双向链表在处理节点的插入、删除的时候确实要麻烦很多，需要判断的情况越多，出bug的概率就越大。