线性表之双向循环链表-工具盒子

双向循环链表的结构 {#1-双向循环链表的结构} ===========================

在上一个章节中为大家详细讲解了双向链表，按照单向链表的思路继续对它进行改进，双向链表的首尾就可以相接，这样就得到了一种新的链表 ------双向循环链表。

1.1 双向循环链表的节点 {#1-1-双向循环链表的节点}

双向循环链表是一种特殊的链表结构，链表中的节点不仅有前驱和后继指针，还需要让链表的最后一个节点的后继指针指向第一个节点，第一个节点的前驱指针指向最后一个节点。

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

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

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

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

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

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

1.2 带头结点的双向循环链表 {#1-2-带头结点的双向循环链表}

定义
- 带头结点的双向循环链表包含一个特殊的头结点，该头结点不存储有效数据，仅用于指示链表的开始位置。
- 头结点的前驱指向链表的最后一个数据节点，链表的最后一个数据节点的后继指向头结点。
优点
- 简化操作：由于有头结点，不论链表是否为空，第一个节点的前驱和最后一个节点的后继节点都可以统一处理，简化了插入、删除等操作的代码逻辑。
- 减少边界检查：插入和删除操作不需要特别判断是否在链表头部或尾部进行，有头结点作为统一的起始点，减少了边界条件的检查。
缺点
- 额外空间：需要额外的空间来存储头结点，这在一定程度上增加了内存开销。
- 稍复杂的实现：需要特别注意头结点的初始化和管理。

1.3 不带头结点的双向循环链表 {#1-3-不带头结点的双向循环链表}

定义
- 不带头结点的双向链表从第一个实际存储数据的节点开始
- 链表的第一个数据节点的前驱是最后一个数据节点，链表最后一个数据节点的后继是第一个数据节点
优点
- 节省空间：不需要额外的头结点，节省了一些内存空间
- 简单的结构：结构更加直接，容易理解
缺点
- 复杂的操作：插入和删除操作需要特别处理头部和尾部的边界条件，增加了代码的复杂度
- 更多的边界检查：需要在每次操作时检查链表是否为空，头部和尾部的特殊情况处理起来较为繁琐

双向链表的操作 {#2-双向链表的操作} =======================

2.1 链表的遍历 {#2-1-链表的遍历}

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

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

2.2 链表的插入 {#2-2-链表的插入}

2.2.1 带头结点的插入 {#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 = 头结点
  - newNode->next = tailNode->next
3. 将newNode节点的前驱设置为tailNode，即：newNode->prev = tailNode
4. 更新tailNode节点的后继节点，tailNode->next = newNode
5. 更新头结点的前驱节点，头结点->prev = newNode

2.2.2 不带头结点的插入 {#2-2-2-不带头结点的插入}

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

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

场景1：空链表

如果链表为空链表，那么新添加的节点就是链表的第一个数据节点
- 如果有头指针需要让头指针指向这个新添加的节点
- 新添加的节点的前驱和后继都是它自己
场景2：在头部插入新节点

将新的节点插入到链表头部和将新节点插入到链表尾部类似，操作流程如下：
1. 遍历链表并找到它的尾节点，记作tailNode
2. 创建一个新的链表节点，记作newNode
3. 让newNode节点的next域指针指向原来的链表头结点
4. 让newNode节点的prev域指针指向尾节点tailNode
5. 重置旧的头结点的前驱节点，设置为newNode
6. 重置尾节点的后继节点，设置为newNode
7. 如果有头指针需要让头指针前移，指向这个新的头结点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 = 头结点
  - newNode->next = tailNode->next
3. 将newNode节点的前驱设置为tailNode，即：newNode->prev = tailNode
4. 更新tailNode节点的后继节点，tailNode->next = newNode
5. 更新头结点的前驱节点，头结点->prev = newNode

2.3 链表的删除 {#2-3-链表的删除}

2.3.1 带头结点的删除 {#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 = 头结点
  - preNode->next = delNode->next
4. 更新头结点的前驱，设置为pos-1位置的节点，即：头结点->prev = preNode
5. 释放delNode节点指向的内存资源

2.3.2 不带头结点的删除 {#2-3-2-不带头结点的删除}

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

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

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

删除链表的第一个数据节点的操作如下：
1. 通过头指针找到链表的第一个数据节点，将其记作delNode
2. 遍历链表找到它的最后一个节点，将其记作tailNode
3. 更新tailNode节点的后继节点，设置为delNode 节点的后继
  - tailNode->next = delNode->next
4. 更新新头结点的前驱节点，将其设置为尾节点，即：delNode->next->prev = tailNode
5. 链表头指针后移一个节点
6. 释放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 = 头结点
  - preNode->next = delNode->next
4. 更新头结点的前驱，设置为pos-1位置的节点，即：头结点->prev = preNode
5. 释放delNode节点指向的内存资源

双向循环链表的实现 {#3-双向循环链表的实现} ===========================

3.1 带头结点的双向循环链表 {#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 39 | // DoubleCircularLinkList.h #pragma once #include <iostream> using namespace std; struct Node { int data; Node* prev; Node* next; Node(int d) : data(d), prev(nullptr), next(nullptr) {} }; class LoopDLinkList { public: LoopDLinkList(); ~LoopDLinkList(); // 判断链表是否为空 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: Node* m_head; Node* m_tail; int m_length; }; |

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

源文件 {#源文件}

|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 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 | // DoubleCircularLinkList.cpp #include "DoubleCircularLinkList.h" #include <iostream> using namespace std; LoopDLinkList::LoopDLinkList() : m_head(new Node(0)), m_length(0) { m_head->prev = m_head; m_head->next = m_head; m_tail = m_head; } LoopDLinkList::~LoopDLinkList() { Node* current = m_head->next; while (current != m_head) { Node* temp = current; current = current->next; cout << "释放链表节点: " << temp->data << endl; delete temp; } delete m_head; } bool LoopDLinkList::isEmpty() { return m_head->next == m_head; } int LoopDLinkList::length() { return m_length; } void LoopDLinkList::prepend(int data) { Node* newNode = new Node(data); newNode->next = m_head->next; newNode->prev = m_head; m_head->next->prev = newNode; if (isEmpty()) { m_tail = newNode; } m_head->next = newNode; m_length++; } void LoopDLinkList::append(int data) { Node* node = new Node(data); node->next = m_head->next; node->prev = m_head; node->next = m_tail->next; node->prev = m_tail; m_tail->next = node; m_head->prev = node; m_tail = node; m_length++; } bool LoopDLinkList::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 = 0; while (j < pos - 1) { p = p->next; j++; } Node* pNode = new Node(data); pNode->next = p->next; pNode->prev = p; p->next->prev = pNode; if (p->next == m_head) { m_tail = pNode; } p->next = pNode; m_length++; } return true; } Node* LoopDLinkList::find(int data, int& pos) { pos = 0; Node* p = m_head; do { p = p->next; pos++; }while (p != m_head && p->data != data); return p; } bool LoopDLinkList::remove(int pos) { if (pos<1 || pos>length()) { cout << "删除链表节点失败, 位置无效" << endl; return false; } if (pos == 1) { Node* p = m_head; m_head = m_head->next; m_head->prev = p->prev; m_tail->next = m_head; delete p; } else { Node* p = m_head; int j = 0; while (j < pos - 1) { p = p->next; j++; } Node* delNode = p->next; p->next = delNode->next; p->next->prev = p; if (p->next == m_head) { m_tail = p; } delete delNode; } m_length--; return true; } void LoopDLinkList::display() { if (m_head->next == m_head) { cout << "空链表" << endl; return; } cout << "从头到尾遍历: " << endl; for (Node* item = m_head->next; item != m_head; item = item->next) { cout << item->data << " "; } cout << endl; cout << "从尾到头遍历: " << endl; for (Node* item = m_tail; item != m_head; item = item->prev) { cout << item->data << " "; } cout << endl; } int main() { LoopDLinkList lst; cout << "是否为空链表: " << lst.isEmpty() << endl; lst.prepend(18); lst.prepend(19); 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; LoopDLinkList lst1; lst1.insert(1, 10); lst1.insert(2, 20); lst1.insert(3, 30); lst1.insert(4, 40); lst1.insert(5, 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 | 是否为空链表: 1 从头到尾遍历: 9 5 4 12 6 7 19 18 8 3 从尾到头遍历: 3 8 18 19 7 6 12 4 5 9 当前链表的长度为: 10 ========== 测试搜索和删除========= 从头到尾遍历: 10 20 30 40 50 从尾到头遍历: 50 40 30 20 10 搜索到的节点位置: 1, 值为: 10 从头到尾遍历: 20 30 40 50 从尾到头遍历: 50 40 30 20 搜索到的节点位置: 2, 值为: 30 从头到尾遍历: 20 40 50 从尾到头遍历: 50 40 20 搜索到的节点位置: 3, 值为: 50 从头到尾遍历: 20 40 从尾到头遍历: 40 20 当前链表的长度为: 2 释放链表节点: 20 释放链表节点: 40 释放链表节点: 9 释放链表节点: 5 释放链表节点: 4 释放链表节点: 12 释放链表节点: 6 释放链表节点: 7 释放链表节点: 19 释放链表节点: 18 释放链表节点: 8 释放链表节点: 3 |

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

3.2 不带头节点的双向链表 {#3-2-不带头节点的双向链表}

头文件 {#头文件-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 39 40 | // DoubleCircularLinkList1.h #pragma once struct Node { int data; Node* prev; Node* next; Node(int d) : data(d), prev(nullptr), next(nullptr) {} }; class LoopDLinkList1 { public: LoopDLinkList1(); ~LoopDLinkList1(); // 判断链表是否为空 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: // 添加节点 void addNode(int data, bool isHead = true); private: Node* m_head; Node* m_tail; int m_length; }; |

源文件 {#源文件-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 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 | // DoubleCircularLinkList1.cpp #include "11-双向循环链表-不带头结点.h" #include <iostream> using namespace std; LoopDLinkList1::LoopDLinkList1() : m_head(nullptr), m_tail(nullptr) { } LoopDLinkList1::~LoopDLinkList1() { while (length()) { remove(1); } } bool LoopDLinkList1::isEmpty() { return m_head == nullptr && m_tail == nullptr; } int LoopDLinkList1::length() { return m_length; } void LoopDLinkList1::prepend(int data) { addNode(data); } void LoopDLinkList1::append(int data) { addNode(data, false); } bool LoopDLinkList1::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->prev = p; p->next->prev = pNode; if (p->next == m_head) { m_tail = pNode; } p->next = pNode; m_length++; } return true; } Node* LoopDLinkList1::find(int data, int& pos) { pos = 1; Node* p = m_head; while(p->next != m_head && p->data != data) { pos++; p = p->next; }; return p; } bool LoopDLinkList1::remove(int pos) { if (pos<1 || pos>length()) { cout << "删除链表节点失败, 位置无效" << endl; return false; } if (pos == 1) { Node* p = m_head; m_head = m_head->next; m_head->prev = p->prev; m_tail->next = m_head; 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; p->next->prev = p; if (p->next == m_head) { m_head->prev = p; m_tail = p; } delete delNode; } m_length--; return true; } void LoopDLinkList1::display() { if (m_head->next == m_head) { cout << "空链表" << endl; return; } cout << "从头到尾遍历: " << endl; Node* item = m_head; do { cout << item->data << " "; item = item->next; } while (item != m_head); cout << endl; cout << "从尾到头遍历: " << endl; item = m_tail; do { cout << item->data << " "; item = item->prev; } while (item != m_tail); cout << endl; } void LoopDLinkList1::addNode(int data, bool isHead) { Node* pNode = new Node(data); Node** p = isHead ? &m_head : &m_tail; if (isEmpty()) { m_head = m_tail = pNode; m_head->next = m_tail; m_tail->next = m_head; } else { pNode->next = m_head; pNode->prev = m_tail; m_head->prev = pNode; m_tail->next = pNode; *p = pNode; } m_length++; } int main() { LoopDLinkList1 lst; cout << "是否为空链表: " << lst.isEmpty() << endl; 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; LoopDLinkList1 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 | 是否为空链表: 1 从头到尾遍历: 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 从头到尾遍历: 20 40 50 从尾到头遍历: 50 40 20 搜索到的节点位置: 3, 值为: 50 从头到尾遍历: 20 40 从尾到头遍历: 40 20 当前链表的长度为: 2 释放链表头部节点: 20 释放链表头部节点: 40 释放链表头部节点: 9 释放链表头部节点: 5 释放链表头部节点: 4 释放链表头部节点: 12 释放链表头部节点: 6 释放链表头部节点: 7 释放链表头部节点: 8 释放链表头部节点: 3 |