循环链表 (Circular Linked List)是另一种形式的链式存储结构。循环链表可以像单向链表一样只有单向引用，也可以像双向链表一样有双向引用。
只有单向引用的循环链表称为单向循环链表，单向循环链表最后一个节点的 next 引用指向头节点 head 而不是 null。
具有双向引用的循环链表叫做双向循环链表，双向链表最后一个节点 tail 的 next 引用指向头节点 head ，头节点 head 的 prev 引用则指向尾节点 tail。
本节主要讲解单向循环链表。
不要担心循环链表会不会造成内存泄漏的问题，循环链表每个节点只存储数据和单个指针，内存复杂度是 O(n)，循环引用不会导致内存翻倍，指针只是内存地址引用。
我们遍历链表时常常根据节点的 next 知否指向 null 来判断链表是否遍历结束。而在循环链表中，该方法不再适用，循环链表中的 next 永远不会指向 null。我们可以根据链表的长度 size 来遍历链表，若链表中不存在 size 属性，那么我们只能根据链表节点的 next 是否指向 head 节点来判断遍历是否终止。循环链表的遍历终止条件：node.next === head。
单向循环链表中创建节点的类没有变化，可以直接使用链表节点的类 Node，单向循环链表可以继承于单向链表。
实现单向链表类
/**
* CircularLinkedList.js
* @date: 2025-03-26
* @description: 单向循环链表
*
*/
import Node from '../../models/Node.js'
import LinkedList from './LinkedList.js'
import { isEqual } from '../../utils/utils.js'
export default class CircularLinkedList extends LinkedList {
constructor(options = { isEqual: isEqual }) {
super(options)
}
}
实现循环链表方法
循环链表的尾结点 tail 的 next 指向了链表的头部节点 head。因此，我们需要重新改写继承的涉及到链表首尾节点操作的方法及涉及到遍历链表的方法（遍历方法改变了）。其他的方法比如：getHead（获取头部节点）、getTail（获取尾部节点）、getSize（获取链表长度）、isEmpty（判断链表是否为空）、clear（清空链表）、getNodeAt（获取指定位置的节点）、indexOf（查找指定值的节点位置）等不需要修改。
首尾节点增删相关方法的修改
增删首尾节点要注意尾结点 tail 的 next 的指向
// push：向尾部添加节点
push(val) {
if (arguments.length === 0) return this.size
const node = new Node(val)
// 直接使用父类的方法进行判断
if (super.isEmpty()) {
this.head = node
node.next = this.head
} else {
// 找到最后一个节点，然后将最后一个节点的next指向新节点，新节点的next指向head节点
let current = this.head
while (current.next !== this.head) {
current = current.next
}
current.next = node
node.next = this.head
}
this.size++
return this.size
}
// pop：删除尾部节点
pop() {
if (super.isEmpty()) return undefined
if (this.size === 1) {
const current = this.head
this.head = null
this.size--
return current.value
} else {
// 获取倒数第二个节点
let pre = super.getNodeAt(this.size - 2)
let current = pre.next
// 倒数第二个节点的 next 绕过最后一个节点指向 head 节点
pre.next = this.head
this.size--
return current.value
}
}
// unshift：向头部添加节点
unshift(val) {
if (arguments.length === 0) return this.size
const node = new Node(val)
if (super.isEmpty()) {
this.head = node
node.next = this.head
} else {
// 获取尾部节点并将其next指向新节点node，新节点node的next指向之前的head节点，然后将head指向新节点
let current = this.head
const tail = super.getTail()
tail.next = node
node.next = current
this.head = node
}
this.size++
return this.size
}
// shift：删除头部节点
shift() {
if (super.isEmpty()) return undefined
const current = this.head
if (this.size === 1) {
this.head = null
this.size--
return current.value
} else {
// 获取尾部节点tail，将其next指向之前head节点后面的那个节点，然后head重新指向之前head节点后面的那个节点
const tail = super.getTail()
tail.next = current.next
this.head = current.next
this.size--
return current.value
}
}
insert方法：任意位置插入节点
insert 方法实现时只要关注节点插入到链表的首尾时这种情况即可，其他插入情况处理方法不变。首尾插入可以使用前面已经实现的方法：unshift 和 push。
// insert：向指定位置插入节点
insert(index, val) {
if (arguments.length < 2) return undefined
if (typeof arguments[0] !== 'number') return undefined
if (index < 0 || index > this.size) return undefined
// 插入到链首
if (index === 0) {
return this.unshift(val)
} else if (index === this.size) {
// 插入到链尾
return this.push(val)
} else {
// 插入到中间位置时处理方法不变
const node = new Node(val)
const pre = super.getNodeAt(index - 1)
const current = pre.next
pre.next = node
node.next = current
this.size++
return this.size
}
}
删除方法 remove 与 removeAt
循环链表中 remove 的方法与父类中的方法是一样的，但是调用的 removeAt 方法实现不一样，所以 remove 方法也要重新定义。同插入类似，我们只需要关注删除首尾节点这种情况即可。删除首尾节点的方法 pop 与 shift 前面已经实现，可以直接调用。
// remove：删除指定值的节点
remove(val) {
if (arguments.length === 0) return undefined
let index = super.indexOf(val)
if (index === -1) return this.size
return this.removeAt(index)
}
// removeAt：删除指定位置的节点
removeAt(index) {
if (arguments.length === 0) return undefined
if (typeof arguments[0] !== 'number') return undefined
if (index < 0 || index >= this.size) return undefined
// 删除首节点
if (index === 0) {
return this.shift()
} else if (index === this.size - 1) {
// 删除尾节点
return this.pop()
} else {
// 删除中间节点，这种情况处理方法不变
const pre = super.getNodeAt(index - 1)
const current = pre.next
pre.next = current.next
this.size--
return current.value
}
}
像链表反转方法 reverse、链表打印方法 toString、获取链表的值方法 values 也需要重写：
// reverse：反转链表
reverse() {
if (super.isEmpty()) return undefined
const tail = super.getTail()
let pre = tail
let current = this.head
for (let i = 0; i < this.size; i++) {
const next = current.next
current.next = pre
pre = current
current = next
}
this.head = tail
return this.head
}
// toString：打印链表
toString() {
// 循环链表输出要注意最后一个结点的判断
if (super.isEmpty()) return ''
let current = this.head
let result = ''
do {
result += current.value + ' -> '
current = current.next
} while (current !== this.head)
// 这里最后加上[HEAD]表示链表最后一个节点又指向了头节点，形成了一个循环
result += '[HEAD]'
return result
}
// values：获取链表所有值
// LinkedList链表类中values方法使用的是next是否存在，这里使用的是next是否等于头节点
// 如果LinkedList类中values方法使用size链表长度判断的话，则不需要重新写values方法
values() {
if (super.isEmpty()) return []
let current = this.head
const values = []
do {
values.push(current.value)
current = current.next
} while (current !== this.head)
return values
}
循环链表的一些方法实现时中要注意链表遍历结束条件：node.next === head，判断不当的话很容易造成死循环。
