这篇文章是JavaScript实现链表数据结构的第三篇文章，本文的主要内容是——双向链表。之前我们已经实现过单向链表和单向循环链表数据结构。
双向链表结构
由名字就可以看出来，和单向链表的结构相比，双向链表的特点在于双向，链表中节点除了next指针之外还有一个prev指针，next和单向链表一样指向当前节点的下一个节点，prev则指向当前节点的前一个节点。双向链表的结构图如下所示：
下面我们就来定义一下相关的数据结构，首先来定义节点的数据结构，除了保存数据之外，每个节点还需要一个指向前一个节点的 prev 指针和指向下一个节点的 next 指针，代码如下：
class Node {
constructor(element, prev, next) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}增(add)、删(remove)、改(update)、查(getNode)
在实现了链表结构之后，接着就是增(add)、删(remove)、改(update)、查(getNode)这些基本方法了。
查(getNode)
这个方法和单向链表的方法实现一样，主要思想是遍历，这里就不再赘述。代码如下：
getNode(index) {
if (index >= this.size) return new Error("index 超出列表长度");
let offset = 0;
let curNode = this.head;
while (offset++ < index && curNode.element) {
curNode = curNode.next;
}
return curNode;
}改(update)
这个方法也是和单向链表一样，找到对应的节点更新数据即可。代码如下：
update(index, element) {
const updateNode = this._getNode(index);
updateNode.element = element;
return updateNode;
}增(add)
这个方法也和单向链表类似，只不过还需要更新prev指针的指向。这里可以分成两种情况讨论：
- 在链表的头节点处插入节点；这种情况下，新插入的节点就是
新头节点，此时需要将旧头节点的prev指针指向新头节点，然后将新头节点的next指向旧头节点；如下图所示：
- 在其他地方插入节点；这种情况下则找到要插入的索引处的前一个节点，将前一个节点的
next指针指向待插入的节点，并将待插入节点的next指针指向前一个节点原本next指向的节点，并将待插入节点的prev指针指向前一个节点；如下图所示：
代码如下：
add(index, element) {
if (arguments.length === 1) {
element = index;
index = this.size;
}
if (index > this.size) throw new Error("index 超出列表长度");
if (index === 0) {
// 在表头插入
const oldHead = this.head;
this.head = new Node(element, null, oldHead);
if (oldHead) oldHead.prev = this.head;
} else {
const prevNode = this._getNode(index - 1);
const newNode = new Node(element, prevNode, prevNode.next);
// 这里需要兼容一下preNode已经是最后一个节点的情况
if (prevNode.next) prevNode.next.prev = newNode;
prevNode.next = newNode;
}
this.size++;
}删(remove)
删除也可以分为两种情况讨论:
- 删除头节点；删除头节点时更新链表的头指针即可；如下图所示：
- 其他情况；当删除链表中的节点时，则注意需要更新删除节点前后两个节点的指针；
remove(index) {
if (index === 0) {
// 如果是删除头节点
this.head = this.head.next;
this.head.prev = null;
} else {
const prevNode = this._getNode(index - 1);
const removeNode = this._getNode(index);
prevNode.next = removeNode.next;
if (removeNode.next) removeNode.next.prev = prevNode;
}
this.size--;
}完整代码
class Node {
constructor(element, prev, next) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
_getNode(index) {
if (index >= this.size) return new Error("index 超出列表长度");
let offset = 0;
let curNode = this.head;
while (offset++ < index && curNode.element) {
curNode = curNode.next;
}
return curNode;
}
getNode(index) {
return this._getNode(index);
}
update(index, element) {
const updateNode = this._getNode(index);
updateNode.element = element;
return updateNode;
}
add(index, element) {
if (arguments.length === 1) {
element = index;
index = this.size;
}
if (index > this.size) throw new Error("index 超出列表长度");
if (index === 0) {
// 在表头插入
const oldHead = this.head;
this.head = new Node(element, null, oldHead);
if (oldHead) oldHead.prev = this.head;
} else {
const prevNode = this._getNode(index - 1);
const newNode = new Node(element, prevNode, prevNode.next);
// 这里需要兼容一下preNode已经是最后一个节点的情况
if (prevNode.next) prevNode.next.prev = newNode;
prevNode.next = newNode;
}
this.size++;
}
remove(index) {
if (index === 0) {
// 如果是删除头节点
this.head = this.head.next;
this.head.prev = null;
} else {
const prevNode = this._getNode(index - 1);
const removeNode = this._getNode(index);
prevNode.next = removeNode.next;
if (removeNode.next) removeNode.next.prev = prevNode;
}
this.size--;
}
display() {
let index = 0;
let curNode = this.head;
let res = "";
while (++index <= this.size && curNode) {
res += `${curNode.element}${index === this.size ? "" : " -> "}`;
curNode = curNode.next;
}
console.log(res);
}
}
