大家好,我是杨成功。
前两篇我们分别介绍了链表与双向链表,链表的基本功能我们都实现了。
其实总结起来,我们讲到的链表也好,双向链表也好,组成每一个链表的元素就好比一个一个铁环,连接起来,就组成了一条长长的铁链。
我们在这条铁链上可以找到任意一个铁环,可以在任意一处增加或去掉铁环。但不管怎么样,这只是一条链子。那我们能不能把这条链子的首部和尾部连起来,变成一个圆圈呢?
当然可以。首尾相连之后,就变成了我们今天的主角 —— 循环链表。
上面我们举例解释了什么是循环链表,原理很简单,相信大家已经明白了。循环链表可以有单向引用,也可以有双向引用。
单向循环链表的结构如下:
双向循环链表如下:
双向循环链表只不过比单项多了一个 prev
的属性,其他都一样。所以我们不需要两种循环各实现一次,直接实现一个双向循环链表即可。
如果不清楚双向链表的实现,请看上一篇 怒肝 JavaScript 数据结构 — 双向链表篇。
与上篇一样,同样用 class extends 的方式继承双向链表:
class CircLinkedList extends DoubLinkedList {
constructor(equalFn) {
super(equalFn)
}
}
CircLinkedList
类继承后没有额外的属性,只需要修改新增和删除方法。
既然要做首尾连接,那么在新添加元素的时候,就要将表头表尾关联。
我们不需要重写,只需要在双向链表原有的 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(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 篇,本系列会连续更新一个月。