数据结构数据结构线性表之双向循环链表
苏丙榅1. 双向循环链表的结构
在上一个章节中为大家详细讲解了双向链表,按照单向链表的思路继续对它进行改进,双向链表的首尾就可以相接,这样就得到了一种新的链表 ——双向循环链表
。
1.1 双向循环链表的节点
双向循环链表是一种特殊的链表结构,链表中的节点不仅有前驱和后继指针,还需要让链表的最后一个节点的后继指针指向第一个节点,第一个节点的前驱指针指向最后一个节点。
假设双向循环链表的节点存储的是整形数据,那么该节点的定义如下:
1 2 3 4 5 6 7
| struct Node { int data = 0; Node* next = nullptr; Node* prev = nullptr; };
|
双向循环链表的节点结构包含三个部分:
- 数据域(data):存储节点的值
- 前驱指针(prev):指向前一个节点
- 后继指针(next):指向后一个节点
在操作双向循环链表的时候通常会定义两个辅助指针:头节点指针
和尾节点指针
,头指针指向链表的第一个节点,尾指针指向链表的最后一个节点。
和前面讲过的链表一样,双向循环链表也可以分为带头结点
的双向循环链表和不带头结点
的双向循环链表,它们在实现细节和使用上存在一些差异。以下是对它们的详细比较:
1.2 带头结点的双向循环链表
定义
优点
简化操作
:由于有头结点,不论链表是否为空,第一个节点的前驱和最后一个节点的后继节点都可以统一处理,简化了插入、删除等操作的代码逻辑。
减少边界检查
:插入和删除操作不需要特别判断是否在链表头部或尾部进行,有头结点作为统一的起始点,减少了边界条件的检查。
缺点
- 额外空间:需要额外的空间来存储头结点,这在一定程度上增加了内存开销。
- 稍复杂的实现:需要特别注意头结点的初始化和管理。
1.3 不带头结点的双向循环链表
定义
优点
节省空间
:不需要额外的头结点,节省了一些内存空间
简单的结构
:结构更加直接,容易理解
缺点
复杂的操作
:插入和删除操作需要特别处理头部和尾部的边界条件,增加了代码的复杂度
更多的边界检查
:需要在每次操作时检查链表是否为空,头部和尾部的特殊情况处理起来较为繁琐
2. 双向链表的操作
2.1 链表的遍历
由于双向循环链表的节点中有前驱和后继指针,所以在遍历它的时候有两种方式:正向遍历
和反向遍历
。
- 正向遍历双向循环链表的过程(从头到尾):
- 从第一个数据节点开始
- 带头结点:从头结点的后继节点开始遍历
- 不带头结点:从第一个节点开始遍历
- 访问当前节点的数据,并通过
next
指针移动到下一个节点
- 重复步骤2,直到到达链表的末尾
- 带头结点:尾节点的后继是头结点
- 不带头结点:尾节点的后继是第一个数据节点(头指针指向的节点)
- 反向遍历双向循环链表的过程(从尾到头):
- 从尾节点开始(前提条件:需要先找到尾节点)
- 访问当前节点的数据,并通过
prev
指针移动到上一个节点
- 重复步骤2,直到到达链表的头部,判定条件为:
- 带头结点:当前节点为
头结点
- 不带头结点:当前节点的
prev
为尾节点
(尾指针指向的节点)
2.2 链表的插入
2.2.1 带头结点的插入
场景1:在头部和中间位置插入新节点
对于带头节点的链表而言,在头部插入节点就是把新的数据节点作为链表的第一个数据节点,它是头结点的后继节点。
在链表的头部和中间位置(pos
)插入新节点需要分以下几步:
- 创建一个新的节点,并初始化,记作
newNode
- 遍历链表找到
pos-1
位置的节点,记作preNode
- 将新节点的后继节点设置为
pos
位置的节点,也就是newNode->next = preNode->next
- 将新节点的前驱节点设置为
pos-1
位置的节点,也就是newNode->prev = preNode
- 重置
pos
位置节点的前驱,设置为newNode
节点,也就是preNode->next->prev = newNode
- 重置
preNode
节点的后继,设置为newNode
,即:preNode->next = newNode
温馨提示:第5、6步不能放到第3、4步之前处理。
下图是将新节点插入到链表的非第一个数据节点的位置:
下图是将新节点作为第一个数据节点插入到链表中:
可以看到,在以上两种情况下插入新节点的处理逻辑是相同的。
场景2:在尾部插入新节点
在链表的尾部添加新节点就是让它作为原来的尾节点的后继,新节点的前驱是原来的尾节点。主要的操作步骤如下:
- 遍历链表并找到它的尾节点,记作
tailNode
- 创建一个新的链表节点,记作
newNode
,并设置它的后继,有两种方式:
newNode->next = 头结点
newNode->next = tailNode->next
- 将
newNode
节点的前驱设置为tailNode
,即:newNode->prev = tailNode
- 更新
tailNode
节点的后继节点,tailNode->next = newNode
- 更新头结点的前驱节点,
头结点->prev = newNode
2.2.2 不带头结点的插入
如果链表没有头结点在进行插入操作的时候就需要判断更多的情况。
在下面描述中,提及的头结点即链表的第一个数据节点。
场景1:空链表
如果链表为空链表,那么新添加的节点就是链表的第一个数据节点
- 如果有头指针需要让头指针指向这个新添加的节点
- 新添加的节点的前驱和后继都是
它自己
场景2:在头部插入新节点
将新的节点插入到链表头部和将新节点插入到链表尾部类似,操作流程如下:
- 遍历链表并找到它的尾节点,记作
tailNode
- 创建一个新的链表节点,记作
newNode
- 让
newNode
节点的next
域指针指向原来的链表头结点
- 让
newNode
节点的prev
域指针指向尾节点tailNode
- 重置旧的头结点的前驱节点,设置为
newNode
- 重置尾节点的后继节点,设置为
newNode
- 如果有头指针需要让头指针前移,指向这个新的头结点
newNode
场景3:在链表中间位置插入新节点
在链表的中间位置(pos
)插入新节点的操作步骤如下:
- 创建一个新的节点,并初始化,记作
newNode
- 遍历链表找到
pos-1
位置的节点,记作preNode
- 将新节点的后继节点设置为
pos
位置的节点,也就是newNode->next = preNode->next
- 将新节点的前驱节点设置为
pos-1
位置的节点,也就是newNode->prev = preNode
- 重置
pos
位置节点的前驱,设置为newNode
节点,也就是preNode->next->prev = newNode
- 重置
preNode
节点的后继,设置为newNode
,即:preNode->next = newNode
温馨提示:第5、6步不能放到第3、4步之前处理。
场景4:在链表尾部插入新节点
在链表的尾部添加新节点主要的操作步骤如下:
- 遍历链表并找到它的尾节点,记作
tailNode
- 创建一个新的链表节点,记作
newNode
,并给它设置后继节点,有两种方式:
newNode->next = 头结点
newNode->next = tailNode->next
- 将
newNode
节点的前驱设置为tailNode
,即:newNode->prev = tailNode
- 更新
tailNode
节点的后继节点,tailNode->next = newNode
- 更新头结点的前驱节点,
头结点->prev = newNode
2.3 链表的删除
2.3.1 带头结点的删除
2.3.2 不带头结点的删除
如果是不带头结点的链表,在进行节点删除的时候会出现链表为空(没有任何节点)的情况,对于这种特殊情况需要单独进行处理。
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 39
| #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); bool insert(int pos, int data); 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
| #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 不带头节点的双向链表
头文件
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
| #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); bool insert(int pos, int data); 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 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
| #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
|