Javascript中的双链表类
这是DoublyLinkedList类的完整实现-
示例
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
insert(data, position = this.length) {
let node = new this.Node(data);
//列表当前为空
if (this.head === null) {
this.head = node;
this.tail = node;
this.length++;
return this.head;
}
//头插入
if (position == 0) {
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
return this.head;
}
let iter = 1;
let currNode = this.head;
while (currNode.next != null && iter < position) {
currNode = currNode.next; iter++;
}
//使新节点指向列表中的下一个节点
node.next = currNode.next;
//将下一个节点的上一个点设为new-
node if (currNode.next != null) {
currNode.next.prev = node;
}
//使我们的节点指向上一个节点
node.prev = currNode;
//使上一个节点的下一个指向新节点
currNode.next = node;
//检查插入的元素是否在尾部，如果是，则使尾部指向它
if (this.tail.next != null) {
this.tail = this.tail.next;
}
this.length++;
return node;
}
remove(data, position = 0) {
if (this.length === 0) {
console.log("List is already empty");
return;
}
this.length--;
let currNode = this.head;
if (position <= 0) {
this.head = this.head.next;
this.head.prev = null;
} else if (position >= this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
let iter = 0;
while (iter < position) {
currNode = currNode.next;
iter++;
}
currNode.next = currNode.next.next;
currNode.next.prev = currNode;
}
return currNode;
}
display() {
let currNode = this.head;
while (currNode != null) {
console.log(currNode.data + " <-> ");
currNode = currNode.next;
}
}
}
DoublyLinkedList.prototype.Node = class {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
};