不同于单链表，双向链表每个节点除了蕴含数据以外，还包含了别离指向其前节点和后节点的指针
其实双链表与比单链表相比，就是节点上新增了一个指向上一个节点的指针而已
上面我来手写一下双链表，实现一些办法：
<img src="https://pic4.zhimg.com/80/v2-1aa41e01531c94ab3e843da7e831049b_720w.png" alt="img" style="zoom:80%;" />
咱们先实现一个节点构造函数：
class Node { constructor(element) { this.element = element; // 节点数据值 this.next = null; // 前指针 this.prev = null; // 后指针 }}双向链表整体构造
class DoubleLinkedList { constructor() { this.count = 0; // 记录节点数 this.head = null; // 双向链表头部 this.tail = null; // 双向链表尾部 } // 链表尾部增加节点 add(element) {} // 链表指定地位增加一个节点 addAt(index, element) {} // 移除链表指定地位的节点 removeAt(index) {} // 移除链表指定节点 remove(element) {} // 翻转链表 reverse() {} // 替换两个节点的地位 swap() {} // 遍历链表 traverse() {} // 查找某个节点的索引 find() {} // 查问链表是否为空 isEmpty() {} // 查问链表的长度 length() {}}接下来就是实现这一个个的办法了
依据地位（索引）查找节点，接下来的办法会始终用到这个办法，索性将其封装成一个办法，以便调用
getElement(index) { if (index >= 0 && index < this.count) { let node = this.head; // 循环遍历到该节点 for (let i = 0; i < index; i++) { node = node.next; } return node; } return undefined;}1、增加节点
<img src="https://pic4.zhimg.com/80/v2-d71171007ed06c66e076048e51184694_720w.png" alt="img" style="zoom:80%;" />
1.1在尾部增加节点
// 传入一个节点add(element) { // 先创立一个节点 const node = new Node(element); // 如果链表为空，那就是头部节点和尾部节点都是node了 if (this.head === null && this.tail === null) { this.head = node; this.tail = node } // 如果链表已有头部，则在其尾部增加节点即可 else { node.prev = this.tail; this.tail.next = node; this.tail = node; } // 节点总数+1 this.count++;}1.2 链表指定地位增加一个节点
addAt(index, element) { if (index >= 0 && index <= this.count) { const node = new Node(element); // 当在头部插入时 if (index === 0) { this.head.prev = node; node.next = this.head; this.head = node; } // 在尾部插入节点 else if (index === this.count) { this.add(element) this.count--; } // 在两头插入节点 else { let current = this.getElement(index); // 先设置新增节点与前一个节点的关系 node.prev = current.prev; current.prev.next = node; // 再设置新增与后一个节点的关系 node.next = current; current.prev = node } this.count++; return true } return false;}2、移除节点
<img src="https://pic1.zhimg.com/80/v2-90d433c7a304d9614996bc26eafea438_720w.png" alt="img" style="zoom:80%;" />
2.1、移除链表指定地位的节点
removeAt(index) { if (index >= 0 && index < this.count) { // 移除头节点 if (index === 0) { this.head = this.head.next; this.head.prev = null; } // 移除尾部节点 else if (index === this.count - 1) { this.tail = this.tail.prev; this.tail.next = null; } // 移除两头节点 else { let current = this.getElement(index); current.next.prev = current.prev current.prev.next = current.next } this.count--; return true } return undefined;}2.2、移除链表指定节点
移除指定节点，首先就是要找到该节点
remove(element) { let current = this.head; while (current) { if (current === element) { // 链表只有一个节点 if (current === this.head && current === this.prev) { this.head = null; this.tail = null; } // 移除头节点 else if (current === this.head) { this.head = this.head.next; this.head.prev = null; } // 移除尾部节点 else if (current === this.tail) { this.tail = this.tail.prev; this.tail.next = null; } // 移除两头节点 else { current.next.prev = current.prev; current.prev.next = current.next; } this.count--; } current = current.next; }}5、翻转链表
reverse() { let current = this.head; let prev = null; // 先将两头的 while (current) { let next = current.next; // 前后倒置 current.next = prev; current.prev = next; prev = current; current = next } this.tail = this.head; this.head = prev}6、替换两个节点的地位
swap(index1, index2) { if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) { let node1 = this.getElement(index1) let node2 = this.getElement(index2) // 让index1 始终小于 index2，不便前面的查找替换 if (index1 > index2) { return this.swap(index2, index1) } // 替换两个节点的数值 [node1.element, node2.element] = [node2.element, node1.element] return true } return undefined;}7、遍历链表
display() { if (!this.isEmpty()) { let current = this.head; let result = ''; while (current) { result += current.element current = current.next if (current) { result += '->'; } } return result; } return undefined;}8、查找某个节点的索引
find(element) { let current = this.head; let index = 0 while (current) { if (current === element) { return index; } current = current.next; index++; } return undefined}9、查问链表是否为空
isEmpty() { return this.count === 0}10、查问链表的长度
length() { return this.count;}整合一下：
// 实现一个节点构造函数class Node { constructor(element) { this.element = element; this.next = null; this.prev = null; }}// 双向链表class DoubleLinkedList { constructor() { this.count = 0; // 记录节点数 this.head = null; // 双向链表头部 this.tail = null; // 双向链表尾部 } // 遍历一个办法，循环到指标地位 getElement(index) { if (index >= 0 && index < this.count) { let node = this.head; for (let i = 0; i < index; i++) { node = node.next; } return node; } return undefined; } // 链表尾部增加节点 add(element) { // 先创立一个节点 const node = new Node(element); // 如果链表为空 if (this.head === null && this.tail === null) { this.head = node; this.tail = node } // 如果链表已有头部，则在其尾部增加节点即可 else { node.prev = this.tail; this.tail.next = node; this.tail = node; } this.count++; } // 链表指定地位增加一个节点 addAt(index, element) { if (index >= 0 && index <= this.count) { const node = new Node(element); // 当在头部插入时 if (index === 0) { this.head.prev = node; node.next = this.head; this.head = node; } else if (index === this.count) { this.add(element) this.count--; } // 非头部插入时 else { let current = this.getElement(index); // 先设置新增节点与前一个节点的关系 node.prev = current.prev; current.prev.next = node; // 再设置新增与后一个节点的关系 node.next = current; current.prev = node } this.count++; return true } return false; } // 移除链表指定地位的节点 removeAt(index) { if (index >= 0 && index < this.count) { // 移除头节点 if (index === 0) { this.head = this.head.next; this.head.prev = null; } // 移除尾部节点 else if (index === this.count - 1) { this.tail = this.tail.prev; this.tail.next = null; } // 移除两头节点 else { let current = this.getElement(index); current.next.prev = current.prev current.prev.next = current.next } this.count--; return true } return undefined; } // 移除链表指定节点 remove(element) { let current = this.head; while (current) { if (current === element) { // 链表只有一个节点 if (current === this.head && current === this.prev) { this.head = null; this.tail = null; } // 移除头节点 else if (current === this.head) { this.head = this.head.next; this.head.prev = null; } // 移除尾部节点 else if (current === this.tail) { this.tail = this.tail.prev; this.tail.next = null; } // 移除两头节点 else { current.next.prev = current.prev; current.prev.next = current.next; } this.count--; } current = current.next; } } // 翻转链表 reverse() { let current = this.head; let prev = null; while (current) { let next = current.next; // 前后倒置 current.next = prev; current.prev = next; prev = current; current = next } this.tail = this.head; this.head = prev } // 替换两个节点的地位 swap(index1, index2) { if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) { let node1 = this.getElement(index1) let node2 = this.getElement(index2) // 让index1 始终小于 index2，不便前面的查找替换 if (index1 > index2) { return this.swap(index2, index1) } // 替换两个节点的数值 [node1.element, node2.element] = [node2.element, node1.element] return true } return undefined; } // 遍历链表 display() { if (!this.isEmpty()) { let current = this.head; let result = ''; while (current) { result += current.element current = current.next if (current) { result += '->'; } } return result; } return undefined; } // 查找某个节点的索引 find(element) { let current = this.head; let index = 0 while (current) { if (current === element) { return index; } current = current.next; index++; } return undefined } // 查问链表是否为空 isEmpty() { return this.count === 0 } // 查问链表的长度 length() { return this.count; }}咱们来调用一下：
// 先实例化一个双向链表对象let DLL = new DoubleLinkedList();// 尾部增加DLL.add(1);DLL.add(2);// 任意地位增加DLL.addAt(0, 3);DLL.addAt(3, 6);// 遍历console.log(DLL.display()); // 3->1->2->6// 依据地位删除DLL.removeAt(3);// 替换两个节点DLL.swap(0, 2)console.log(DLL.display()); // 2->1->3// 翻转DLL.reverse();// 链表是否为空console.log(DLL.isEmpty()); // false// 链表长度console.log(DLL.length()); // 3总结：
- 所以你会发现实现一个链表无非也就是增（增加节点）删（删除节点）改（替换）查（遍历）
- 增加和删除节点无非就是批改节点的指针指向而已