怒肝 JavaScript 数据结构 — 循环链表篇
大家好，我是杨成功。
前两篇我们分别介绍了链表与双向链表，链表的基本功能我们都实现了。
其实总结起来，我们讲到的链表也好，双向链表也好，组成每一个链表的元素就好比一个一个铁环，连接起来，就组成了一条长长的铁链。
我们在这条铁链上可以找到任意一个铁环，可以在任意一处增加或去掉铁环。但不管怎么样，这只是一条链子。那我们能不能把这条链子的首部和尾部连起来，变成一个圆圈呢？
当然可以。首尾相连之后，就变成了我们今天的主角 —— 循环链表。
实现循环链表
上面我们举例解释了什么是循环链表，原理很简单，相信大家已经明白了。循环链表可以有单向引用，也可以有双向引用。
单向循环链表的结构如下：
双向循环链表如下：
双向循环链表只不过比单项多了一个 prev 的属性，其他都一样。所以我们不需要两种循环各实现一次，直接实现一个双向循环链表即可。
如果不清楚双向链表的实现，请看上一篇 怒肝 JavaScript 数据结构 — 双向链表篇。
与上篇一样，同样用 class extends 的方式继承双向链表：
class CircLinkedList extends DoubLinkedList {
constructor(equalFn) {
super(equalFn)
}
}
CircLinkedList 类继承后没有额外的属性，只需要修改新增和删除方法。
升级 insert 方法
既然要做首尾连接，那么在新添加元素的时候，就要将表头表尾关联。
我们不需要重写，只需要在双向链表原有的 insert 方法加关联逻辑即可：
insert(item, index) {
if(index >= 0 && index <= this.count) {
let node = new DoubNode(item)
let current = this.head;
if(index === 0) {
if(!this.head) {
this.head = node
this.tail = node
} else {
node.next = current
current.prev = node
this.head = node
}
// 1. 首位改变循环
this.tail.next = this.head
this.head.prev = this.tail
} else if(index === this.count) {
current = this.tail
current.next = node
node.prev = current
this.tail = node
// 2. 末尾改变循环
this.tail.next = this.head
this.head.prev = this.tail
} else {
let previous = this.getItemAt(index - 1)
current = previous.next
previous.next = node
node.prev = previous
node.next = current
current.prev = node
}
this.count++;
return true;
}
return false;
}
你看，上面的方法非常简单，只需要在第一位和最后一位插入时，互相设置一下引用：
this.tail.next = this.head
this.head.prev = this.tail
这样就可以了，中间元素的添加不需要做处理。
升级 removeAt 方法
与上面方法的逻辑一样，在双向链表的的 removeAt 基础上实现，在删除表头和表尾的时候，重新设置引用：
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) {
if (!current) {
return undefined;
}
this.head = current.next;
// 1. 首位改变循环
this.tail.next = this.head
this.head.prev = this.tail
} else if (index === this.count) {
current = this.tail;
this.tail = current.prev;
// 2. 末尾改变循环
this.tail.next = this.head
this.head.prev = this.tail
} else {
current = this.getItemAt(index);
let previous = current.prev;
previous.next = current.next;
current.next.prev = previous;
}
this.count--;
return current.value;
}
return undefined;
}
这里与上面 insert 方法添加的内容是一样的：
this.tail.next = this.head
this.head.prev = this.tail
也是在删除表头或表尾之后，重新赋值并互相设置引用。
使用双向循环链表
首先向链表中添加三个元素，使其按顺序排列：
var circ = new CircLinkedList();
circ.insert("北京", 0);
circ.insert("上海", 1);
circ.insert("广州", 2);
console.log(circ.toString()); // 北京,上海,广州
接着打印表头与其前后的值：
console.log(circ.head.value); // 北京
console.log(circ.head.prev.value); // 广州
console.log(circ.head.next.value); // 上海
再看表尾与其前后的值：
console.log(circ.tail.value); // 广州
console.log(circ.tail.prev.value); // 上海
console.log(circ.tail.next.value); // 北京
根据测试结果发现，双向循环链表的任意一个元素，它的 prev 和 next 属性永远不为空，因为双向循环是一个圈，所以任意一个元素都有前后值。
总结
本篇介绍了循环链表的概念，应该是本系列最简单的内容了。下一篇我们介绍有序链表。
本文来源公众号：程序员成功。这是学习 JavaScript 数据结构与算法的第 12 篇，本系列会连续更新一个月。