双向链表
双向链表顾名思义，有两条链，即是每个节点都包含一个 prev，next 指向，下面是双向链表的常见操作，手写双向链表的感觉有点嗨！(参考 google 后大神写的代码)
ps: 之前没有想过可以不断改变 tail 的指向来达到不断添加新的节点到链表结尾，学到了，哈哈！
双向链表图示：
代码
// DoublyLinklistNode
class DoublyLinkedListNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
const head = Symbol("head");
const tail = Symbol("tail");
// DoublyLinkedList
class DoublyLinkedList {
constructor() {
this[head] = null;
this[tail] = null;
this.length = 0;
}
add(data) {
const newNode = new DoublyLinkedListNode(data);
if (this[head] === null) {
this[head] = newNode;
} else {
this[tail].next = newNode;
newNode.prev = this[tail];
}
this[tail] = newNode;
this.length++;
}
addHead(data) {
return this.insert(0, data);
}
addTail(data) {
return this.insert(this.size(), data);
}
insert(index, data) {
const newNode = new DoublyLinkedListNode(data);
// add to head
if (index === 0) {
if (this[head] !== null) {
newNode.next = this[head];
this[head].prev = newNode;
}
this[head] = newNode;
return data;
}
// add to tail
if (index === this.size()) {
this[tail].next = newNode;
newNode.prev = this[tail];
this[tail] = newNode;
return data;
}
// add index between 0 ~ this.size()
let current = this[head];
let i = 0;
while (current && i < index) {
current = current.next;
i++;
}
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
return data;
}
get(index) {
let i = 0;
let current = this[head];
while (current && i < index) {
current = current.next;
i++;
}
return current ? current.data : undefined;
}
remove(index) {
if (index < 0) {
throw RangeError(`Index ${index} does in the list.`);
}
if (index === 0) {
const data = this[head].data;
this[head] = this[head].next;
if (this[head] === null) {
this[tail] = null;
} else {
this[head].prev = null;
}
this.length--;
return data;
} else {
let current = this[head];
let i = 0;
while (current && i < index) {
current = current.next;
i++;
}
if (current) {
current.prev.next = current.next;
if (current === this[tail]) {
this[tail] = current.prev;
} else {
current.next.prev = current.prev;
}
this.length--;
return current.data;
}
throw RangeError(`Index ${index} does not in the list.`);
}
}
*values() {
let current = this[head];
while (current) {
yield current.data;
current = current.next;
}
}
*reverse() {
let current = this[tail];
while (current) {
yield current.data;
current = current.prev;
}
}
size() {
return this.length;
}
}
复杂度分析
- 时间复杂度: add: O(1) insert: O(1~n) remove: O(1~n) get: O(1~n)
- 空间复杂度: O(1)