循环链表
[!Tip] 本节源代码见Github链接🔗
概述
在单向链表、双向链表中，都用NULL值表示链表的结束，但是循环链表没有结束标志，表尾结点的后继指针指向表头结点。
循环链表的数据结构如下图所示：
循环链表的类型声明方式如下所示：
【👉🏻>>点击展开查看代码】
/**
* 循环链表结点
*
* @className: CllNode
* @author: Max Solider
* @date: 2022-10-08 21:48
*/
public class CllNode {
/**
* 结点数据
*/
private int data;
/**
* 后继结点指针
*/
private CllNode next;
public CllNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public CllNode getNext() {
return next;
}
public void setNext(CllNode next) {
this.next = next;
}
}
优缺点及相关应用场景
优点：
在存储上与单向链表相比没有突出的优点，但常与特殊的算法结合使用，应用在特定场景中，如轮训算法。
缺点：
由于循环链表没有结束标记，在遍历链表时需要特别注意，容易进入死循环。
应用：
常用于计算机资源的分配，比如通过轮训算法为进程分配CPU资源，必须确保在所有其他进程使用结束前，没有进程访问系统资源。还可用于实现栈和队列。
基本操作
对循环链表的基本操作包括：
- 遍历计数或输出内容；
- 插入新结点；
- 删除结点。
统计循环链表的结点个数
核心思路：
与单向链表相同，都是依赖结点的后继结点来判断是否遍历结束。但循环链表需要判断结点的后继指针是否指向头结点，而非NULL。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 遍历链表
*
* @author: Max Solider
* @date: 2022/10/8 21:59
* @param headNode
* @return int 链表长度
*/
static int listLength(CllNode headNode) {
if (headNode == null) {
return 0;
}
CllNode currentNode = headNode;
int count = 1;
do {
System.out.println("第" + count + "个结点的值是：" + currentNode.getData());
currentNode = currentNode.getNext();
count++;
} while (currentNode != headNode);
return count - 1;
}
时间复杂度：
时间复杂度是O(n)，用于遍历一次链表。
空间复杂度：
空间复杂度是O(1)，用于存储临时变量。
输出循环链表的内容
和上述统计循环链表结点数量方法相同，不再赘述。
在循环链表的表尾插入结点
核心思路：
在循环链表的表尾插入新结点，包含以下3步：
- 找到表尾结点；
- 将表尾结点的后继指针指向新结点；
- 将新结点的后继指针指向表头结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 表尾插入新结点
*
* @param headNode
* @param newNode
* @return org.example.linkedlist.circular.CllNode
* @author: Max Solider
* @date: 2022/10/8 22:14
*/
CllNode insertTail(CllNode headNode, CllNode newNode) {
if (headNode == null) {
headNode = newNode;
headNode.setNext(newNode);
return headNode;
}
// 找到原表尾结点
CllNode oldTailNode = headNode;
do {
oldTailNode = oldTailNode.getNext();
} while (oldTailNode.getNext() != headNode);
// 插入新表尾结点
oldTailNode.setNext(newNode);
newNode.setNext(headNode);
return headNode;
}
时间复杂度：
时间复杂度是O(n)，用于遍历链表。
空间复杂度：
空间复杂度是O(1)，用于保存临时变量。
在循环链表的表头插入结点
核心思路：
在表头插入新结点，包含以下3步：
- 新结点的后继指针指向原表头结点；
- 表头指针指向新结点；
- 表尾结点的后继指针指向新结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 链表头插入新结点
*
* @author: Max Solider
* @date: 2022/10/8 22:29
* @param headNode
* @param newNode
* @return org.example.linkedlist.circular.CllNode
*/
CllNode insertHead(CllNode headNode, CllNode newNode) {
if (headNode == null) {
headNode = newNode;
headNode.setNext(newNode);
return headNode;
}
if (newNode == null) {
return headNode;
}
// 更新头结点
newNode.setNext(headNode);
headNode = newNode;
// 更新尾结点信息
CllNode tailNode = headNode.getNext();
do {
tailNode = tailNode.getNext();
} while (tailNode.getNext() != headNode.getNext());
tailNode.setNext(headNode);
return headNode;
}
时间复杂度：
时间复杂度是O(n)，用于遍历链表。
空间复杂度：
空间复杂度是O(1)，用于存储临时变量。
删除循环链表中的最后一个结点
核心思路： 删除表尾结点，包含以下3步：
- 找到表尾结点；
- 找到表尾结点的前驱结点，并将它的后继指针指向表头结点；
- 移除表尾结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 删除表尾结点
*
* @param headNode
* @return org.example.linkedlist.circular.CllNode
* @author: Max Solider
* @date: 2022/10/8 22:42
*/
CllNode deleteTail(CllNode headNode) {
if (headNode == null) {
return headNode;
}
if (headNode.getNext() == headNode) {
headNode.setNext(null);
headNode = null;
return headNode;
}
// 找到表尾结点的前驱结点
CllNode currentNode = headNode;
while (currentNode.getNext().getNext() != headNode) {
currentNode = currentNode.getNext();
}
// 更新表尾结点信息
currentNode.getNext().setNext(null);
// 更新表尾结点的前驱结点的信息
currentNode.setNext(headNode);
return headNode;
}
时间复杂度：
时间复杂度是O(n)，用于遍历链表。
空间复杂度：
空间复杂度是O(1)，用于存储临时变量。
删除循环链表中的第一个结点
核心思路：
删除头结点包含以下3步：
- 找到尾结点，将尾结点的后继指针指向原头结点的后继结点；
- 将头指针指向原头结点的后继结点；
- 移除原头结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 删除表头结点
*
* @author: Max Solider
* @date: 2022/10/8 22:54
* @param headNode
* @return org.example.linkedlist.circular.CllNode
*/
CllNode deleteHead(CllNode headNode) {
if (headNode == null) {
return headNode;
}
if (headNode.getNext() == headNode) {
headNode.setNext(null);
headNode = null;
return headNode;
}
// 更新表尾结点
CllNode tailNode = headNode;
while (tailNode.getNext() != headNode) {
tailNode = tailNode.getNext();
}
tailNode.setNext(headNode.getNext());
// 更新头指针
CllNode oldHead = headNode;
headNode = headNode.getNext();
// 更新原头结点
oldHead.setNext(null);
oldHead = null;
return headNode;
}
时间复杂度：
时间复杂度是O(n)，用于遍历链表找到尾结点。
空间复杂度：
空间复杂度是O(1)，用于保存临时变量。