线性表之单向循环链表

1. 单向循环链表的结构

在上一个章节中为大家详细讲解了单向链表,由于它的每个节点只有一个指向后继节点的指针,通过这个指针我们只能从前往后对链表进行遍历。当遍历到链表尾部的时候再想回到从前是绝对不可能了。想要实现从链表尾部往前遍历有两种解决方案就是使用循环链表或者双向链表

1.1 单向循环链表

循环链表又分为单向循环链表双向循环链表,我们先来研究单向循环链表将单向链表的尾节点的后继指针由指向空指针改成指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就称之为单向循环链表。

在单向循环链表中的每个节点的结构和单向链表是相同的,假设单向循环链表的节点存储的是整形数据,那么该节点的定义如下:

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

1.2 头结点

如果对单向循环链表再次进行细分可以分为两类:带头结点的单向循环链表不带头结点的单向循环链表

下图是不带头结点的单向循环链表:

image-20240625001655920

如果单向循环链表不带头结点,它的尾节点的后继指针指向的是链表的第一个数据节点,辅助指针头指针指向的也是链表的第一个数据节点。

下图是带头结点的单向循环链表:

如果单向循环链表带头结点,它的尾节点的后继指针指向的是链表的头节点,辅助指针头指针指向的也是链表的头节点。

1.3 特殊情况

对于单向循环链表而言,不论是带头结点还是不带头结点,当链表中只有一个节点的时候会出现当前节点的后继节点还是当前节点的情况

如果是带头结点的单向循环链表并且链表中只要一个节点,那么这个节点肯定是头结点,此时头结点的后继还是头结点。

image-20240625003155710

如果是不带头结点的单向循环链表并且链表中只要一个节点,那么这个节点肯定是数据节点,此时这个数据节点的后继还是它自己。

image-20240625003349069

2. 单向循环链表的操作

2.1 链表的遍历和搜索

关于单向循环链表的遍历与单向链表稍微有些不同,主要步骤如下:

  1. 定义一个辅助指针,让指针指向链表的第一个节点,得到头指针
  2. 根据头节点的next域指针,访问第二个链表节点,再根据第二个节点的next域指针访问第三个链表节点,以此类推……
  3. 判断遍历到的当前节点是不是头指针指向的节点
    • 如果是,链表遍历完成
    • 如果不是,继续向后进行遍历

如果掌握了链表的遍历,想要搜索链表中的某个节点,只需要在遍历链表过程中,对每个节点的值或者节点地址进行判断即可。单向循环链表的搜索方式和单向链表完全相同。

2.2 链表的插入

2.2.1 带头结点的插入

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

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

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

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

    温馨提示:第三步、第四步操作是不能颠倒的。

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

    image-20240625010334111

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

    image-20240625010538892

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

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

    在链表的尾部添加新节点就是让原来的尾节点指向新节点的地址,让新节点的指针域指向空地址。主要的操作步骤如下:

    1. 遍历链表并找到它的尾节点,记作tailNode
    2. 创建一个新的链表节点,记作newNode,并初始化,有两种方式:
      • newNode->next = 头结点
      • newNode->next = tailNode->next
    3. 让尾节点的指针域指向新创建的节点的地址,tailNode->next = newNode
    image-20240625014417069

2.2.2 不带头结点的插入

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

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

  • 场景1:空链表

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

    • 如果有头指针需要让头指针指向这个新添加的节点
    • 新添加的节点的后继节点是它自己
    image-20240625012322529
  • 场景2:在头部插入新节点

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

    1. 创建一个新的链表节点
    2. 让新的链表节点的next域指针指向原来的链表头结点
    3. 更新尾节点的后继指针指向的节点,将其更新为新的头结点
    4. 如果有头指针需要让头指针前移,指向这个新的头结点
    image-20240625103054982
  • 场景3:在链表中间位置插入新节点

    在链表的中间位置(pos)插入新节点的操作步骤如下:

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

    温馨提示:第三步、第四步操作是不能颠倒的。

    image-20240625013959311
  • 场景4:在链表尾部插入新节点

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

    1. 遍历链表并找到它的尾节点,记作tailNode
    2. 创建一个新的链表节点,记作newNode,并初始化,有两种方式:
      • newNode->next = 头结点
      • newNode->next = tailNode->next
    3. 让尾节点的指针域指向新创建的节点的地址,tailNode->next = newNode
    image-20240625014544239

2.3 链表的删除

2.3.1 带头结点的删除

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

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

    删除头部和中间位置(pos)的节点的处理流程如下:

    1. 遍历链表,搜索链表的节点,找到要删除的节点的上一个节点(pos-1),记作preNode
    2. 通过preNode找到要删除的节点,记作delNode
      • delNode = preNode->next
    3. delNode从链表中移除,即preNode->next = delNode->next
    4. 释放delNode节点指向的内存资源

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

    image-20240625015529846

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

    image-20240625015641435
  • 场景2:删除尾部节点

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

    1. 遍历链表找到链表的倒数第二个节点,记作preNode
    2. 通过preNode找到要删除的节点,记作delNode
      • delNode = preNode->next
    3. preNode节点的指针域指向头结点,有两种处理方式
      • preNode->next = 头结点
      • preNode->next = delNode->next
    4. 释放delNode节点指向的内存资源

通过以上分析可以得知:对于带头结点的单向循环链表,删除链表中任意位置的节点的处理流程是可以使用同样的逻辑进行处理的。

2.3.2 不带头结点的删除

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

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

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

    image-20240625021716940
  • 场景2:删除链表的第一个数据节点

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

    1. 通过头指针找到链表的第一个数据节点,将其记作delNode
    2. 遍历找到链表的尾节点,记作tailNode
    3. 更新链表尾节点的后继节点,tailNode->next = delNode->next
    4. 链表头指针后移一个节点
    5. 释放delNode节点占用的内存资源
    image-20240625022201247
  • 场景3:删除链表中间位置的数据节点

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

    1. 遍历链表并搜索,找到要删除的节点的上一个节点,记作preNode
    2. 通过preNode找到要删除的节点,记作delNode
      • delNode = preNode->next
    3. delNode从链表中移除,即preNode->next = delNode->next
    4. 释放delNode节点指向的内存资源
  • 场景4:删除链表尾部的数据节点

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

    1. 遍历链表找到链表的倒数第二个节点,记作preNode
    2. 通过preNode找到要删除的节点,记作delNode
      • delNode = preNode->next
    3. preNode节点的指针域指向头结点,有两种处理方式
      • preNode->next = 头结点
      • 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
// CircularLinkList.h
#pragma once
struct Node
{
int data = 0;
Node* next = nullptr;
};

// 单向循环链表
class LoopLinkList
{
public:
LoopLinkList();
~LoopLinkList();

// 判断链表是否为空
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 = nullptr;
Node* m_tail = nullptr;
int m_length = 0;
};

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

源文件

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

LoopLinkList::LoopLinkList() : m_head(new Node)
{
// 头结点指向自己, 形成环->空链表
m_head->next = m_head;
m_tail = m_head;
}

LoopLinkList::~LoopLinkList()
{
Node* p = m_head->next;
while (p != m_head)
{
Node* del = p;
cout << "删除节点: " << del->data << endl;
p = p->next;
delete del;
}
delete m_head;
}

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

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

void LoopLinkList::prepend(int data)
{
Node* node = new Node;
node->data = data;
if (isEmpty())
{
m_tail = node;
}
node->next = m_head->next;
m_head->next = node;
m_length++;
}

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

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

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

bool LoopLinkList::remove(int pos)
{
if (pos<1 || pos>length())
{
cout << "删除失败, 无效的pos位置" << 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;
delete delNode;
m_length--;
return true;
}

void LoopLinkList::display()
{
if (m_head == m_head->next)
{
cout << "空链表" << endl;
return;
}
cout << "遍历循环单向列表: " << endl;
Node* p = m_head->next;
while (p != m_head)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}

int main()
{
LoopLinkList 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;
LoopLinkList 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;
}

在上面的代码中,insertremove函数支持操作的链表位置有三处:头部(第一个数据节点)、中间、尾部

执行程序,终端输出的信息为:

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
遍历循环单向列表:
9 5 4 12 6 7 8 3
当前链表的长度为: 8
========== 测试搜索和删除=========
遍历循环单向列表:
10 20 30 40 50
搜索到的节点位置: 1, 值为: 10
遍历循环单向列表:
20 30 40 50
搜索到的节点位置: 2, 值为: 30
遍历循环单向列表:
20 40 50
搜索到的节点位置: 3, 值为: 50
遍历循环单向列表:
20 40
当前链表的长度为: 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
38
// CircularLinkList1.h
#pragma once
struct Node
{
Node(int value) : data(value) {}
int data;
Node* next = nullptr;
};

// 单向循环链表
class LoopLinkList1
{
public:
LoopLinkList1();
~LoopLinkList1();

// 判断链表是否为空
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 = nullptr;
Node* m_tail = nullptr;
int m_length = 0;
};

源文件

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

LoopLinkList1::LoopLinkList1()
{
}

LoopLinkList1::~LoopLinkList1()
{
while (!isEmpty())
{
remove(1);
}
}

bool LoopLinkList1::isEmpty()
{
return m_head == nullptr && m_tail == nullptr;
}

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

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

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

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

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

bool LoopLinkList1::remove(int pos)
{
if (pos<1 || pos>length())
{
cout << "删除失败, 无效的pos位置" << endl;
return false;
}
Node* p = m_head;
for (int i = 1; i < pos - 1; ++i)
{
p = p->next;
}
if (pos == 1)
{
if (p->next == m_head)
{
delete m_head;
m_head = m_tail = nullptr;
}
else
{
m_head = m_head->next;
m_tail->next = m_head;
delete p;
}
}
else
{
Node* delNode = p->next;
p->next = delNode->next;
delete delNode;
if (pos == m_length)
{
m_tail = p;
}
}
m_length--;
return true;
}

void LoopLinkList1::display()
{
if (m_head == nullptr)
{
cout << "空链表" << endl;
return;
}
Node* p = m_head;
cout << "遍历链表: ";
do {
cout << p->data << " ";
p = p->next;
} while (p != m_head);
cout << endl;
}

int main()
{
LoopLinkList1 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;
LoopLinkList1 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;
}

在上面的代码中,insertremove函数支持操作的链表位置有三处:头部、中间、尾部

执行程序,终端打印的信息如下:

1
2
3
4
5
6
7
8
9
10
11
遍历链表: 9 5 4 12 6 7 8 3
当前链表的长度为: 8
========== 测试搜索和删除=========
遍历链表: 10 20 30 40 50
搜索到的节点位置: 1, 值为: 10
遍历链表: 20 30 40 50
搜索到的节点位置: 2, 值为: 30
遍历链表: 20 40 50
搜索到的节点位置: 3, 值为: 50
遍历链表: 20 40
当前链表的长度为: 2

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