双向链表

双向链表是链表的一种，它的每个节点中都有两个指针，分别指向上一个节点和下一个节点，所以，从双向链表中的任意一个节点开始，都可以很方便的访问他的前驱节点和后继节点。如下图为双向链表的结构图：
link (1).jpg
双向链表与普通链表的区别在于，在普通链表中，一个节点只有一个指向下一个节点的指针域，而在双向链表中，有两个指针域，一个指向下一个节点，另一个指向上一个节点，如上图所示。

实现双向链表

定义节点类

双向链表中的节点只是比普通链表中的节点多了一个 prev 指针，我们的双向链表中的节点类可以继承自普通链表的节点类：

  1. class DoublyNode {
  2.     constructor(element) {
  3.     this.element = element;
  4.     this.prev = null;
  5.     this.next = null;
  6.   }
  7. }

定义双向链表类

DoublyLinkList 类是一种特殊的 LInkList 类，我们只需要扩展

  1. import { defaultEquals } from './utils';
  3. class DoublyLinkList {
  4.     constructor(equalsFn = defaultEquals) {
  5.     // 链表内部的函数，用于比较链表中的元素是否相等
  6.       this.equalsFn = equalsFn;
  7.     // 存储双向链表中的元素个数
  8.     this.count = 0;
  9.     // 保存头节点（注意：head 永远指向头节点）
  10.     this.head = null;
  11.     // 保存尾结点（注意：tail 永远指向尾结点）
  12.     this.tail = null;
  13.   }
  14. }

接下来，我们为双向链表定义一些方法：

append(element) 向双向链表尾部添加一个新元素
insert(element, index) 向双向链表的任意位置插入新元素
getElementAt(index) 返回双向链表中特定位置的元素，若元素不存在，返回 undefined
remove(element) 从双向链表中移除一个元素
removeAt(index) 从双向链表的特定位置移除一个元素
removeHead() 移除首节点
removeTail() 移除尾结点
indexOf(element) 返回指定元素在双向链表中的索引，若没有该元素则返回 -1
head() 返回首节点
tail() 返回尾结点
size() 返回双向链表包含的元素个数，即返回链表的长度
isEmpty() 判断双向链表是否为空
clear() 清空双向链表
toString() 返回表示整个双向链表的字符串
inverseToString() 返回双向链表从头到尾的字符串

append 向双向链表尾部添加一个新元素

向双向链表尾部添加一个新元素时，和向普通链表尾部添加新元素一样，也可能有两中情景：

  • 双向链表为空，添加的是第一个元素

  • 双向链表不为空，向其追加元素

    1. append(element) {
    2.   const node = new DoublyNode();
    4. // 双向链表为空，添加的是第一个元素
    5. if (this.head == null) {
    6.   // 让 head 指向新创建的节点
    7.     this.head = node;
    8.   // 让 tail 属性指向新创建的节点 tail 属性永远指向双向链表的最后一个元素
    9.   this.tail = node;
    10. } else {
    11.   // 双向链表不为空，向双向链表尾部添加元素
    13.   // 将尾部元素的 next 指针指向新节点，新节点就变成了新的尾结点
    14.     this.tail.next = node;
    15.   // 将新创建的节点的 prev 指针指向旧的尾结点
    16.   node.prev = this.tail;
    17.   // tail 属性永远是链表最后一个元素的引用
    18.   this.tail = node;
    19. }
    20. this.count++;
    21. }

    我们来分析一下这两种情景：

第一种情景：向空的双向链表添加一个元素。当我们创建一个双向链表实例时，head 默认会指向 null，也就意味着此时的双向链表是一个空链表，我们是在向双向链表添加第一个元素，因此我们要做的就是让 head 指向这个新建的节点 node，同时也要把 tail 指向 node，即此时的 node 节点既是首节点也是尾结点。

  1. // 双向链表为空，添加的是第一个元素
  2. if (this.head == null) {
  3.   // 让 head 指向新创建的节点
  4.   this.head = node;
  5.   // 让 tail 属性指向新创建的节点 tail 属性永远指向双向链表的最后一个元素
  6.   this.tail = node;
  7. }

第二种情景：向一个不为空的双向链表添加新元素。要向双向链表的尾部添加一个新元素，首先需要找到最后一个元素。在双向链表中，tail 属性永远都是对双向链表最后一个元素的引用，因此我们可以很方便的找到双向链表中的最后一个元素。然后将 tail 的 next 指针指向要添加到双向链表的新节点，再将 tail 属性指向新节点，因为 tail 属性永远都是指向双向链表中的最后一个元素。

  1. else {
  2.   // 双向链表不为空，向双向链表尾部添加元素
  4.   // 将尾部元素的 next 指针指向新节点，新节点就变成了新的尾结点
  5.   this.tail.next = node;
  6.   // 将新创建的节点的 prev 指针指向旧的尾结点
  7.   node.prev = this.tail;
  8.   // tail 属性永远是链表最后一个元素的引用
  9.   this.tail = node;
  10. }

insert 向双向链表的任意位置插入新元素

insert 方法向双向链表的任意位置插入一个新元素。向双向链表中插入新元素时，需要考虑四种情景：

  • 插入的位置不合法，元素插入失败
  • 在双向链表的起点位置插入新元素
  • 在双向链表的尾部插入新元素

  • 在双向链表的中间插入新元素 ```javascript insert(element, index) { // 插入的位置合法，向双向链表中插入新元素 if (index >=0 && index <= this.count) {

    const node = new DoublyNode(element); let current = this.head;

    if (index === 0) {

    1.   // 在双向链表的头部插入元素
    3. if (this.head == null) { // 双向链表为空链表
    4.   // 此时添加的 node 节点既是头节点也是尾节点
    5.     this.head = node;
    6.   this.tail = node;
    7. } else { // 双向链表不为空，此时添加的 node 将会成为 头节点
    9.   // 将 node 节点的 next 指针指向当前的头节点
    10.     node.next = this.head;
    11.   // 将当前的头节点的 prev 指针指向 node 节点
    12.   this.head.prev = node;
    13.   // 将 head 指向 node，node成为新的头节点
    14.   this.head = node;
    15. }

    } else if (index === this.count) {

    1.   // 在双向链表的尾部插入元素，此时添加的 node 将会成为 尾节点
    3. current = this.tail;
    4. // 将当前的尾节点的 next 指针指向 node 节点
    5. current.next = node;
    6. // 将 node 节点的 prev 指针指向当前的尾节点
    7. node.prev = current;
    8. // 将 tail 属性指向 node，node成为新的尾节点
    9. this.tail = node;

    } else {

    1.   // 在双向链表的其他位置插入元素
    3. // 首先获取插入位置的前一个节点
    4. const previous = this.getElementAt(index - 1);
    5. // 插入位置的后一个节点
    6. current = previous.next;
    7. // 将 node 节点插入 previous 和 current 之间
    8. // 则将 node 的 next 指针指向 current，prev 指针指向 previous
    9. node.next = current;
    10. node.prev = previous;
    11. // node 节点插入后，previous 的 next 指针指向 node 节点
    12. previous.next = node;
    13. // current(插入位置的后一个节点) 的 prev 指针指向新插入的 node 节点
    14. current.prev = node;

    }

    // 新节点插入后，双向链表的长度增加 1 this.count++; // 返回 true，表示元素成功插入到双向链表中 return true; }

    // 插入的位置不合法，返回false，表示元素没有添加到双向链表中 return false;

}

  1. 下面我们逐一分析这四种情景：
  3. 第一种情景：插入的位置不合法。由于我们是根据位置（索引）来插入元素，因此在插入前需要先检查越界值，如果越界了，就返回 false，表示元素没有插入到双向链表中。
  4. ```javascript
  5. if (index >=0 && index <= this.count) {
  6. }
  7. // 插入的位置不合法，返回false，表示元素没有添加到双向链表中
  8. return false;

第二种情景：在双向链表的第一个位置(起点) 插入一个新元素。如果双向链表为空，我们只需要把 head 和 tail 属性都指向这个新节点即可，此时的 node 节点既是头节点也是尾结点。如果双向链表不为空，我们就将新加节点 node 的 next 指针指向双向链表中当前的头节点 head，然后将 head 的 prev 指针指向新加节点 node，最后将 head 属性指向 node 节点，新插入的 node 节点就成为了新的头节点。

  1. if (index === 0) {
  2.   // 在双向链表的头部插入元素
  4.   if (this.head == null) { // 双向链表为空链表
  5.     // 此时添加的 node 节点既是头节点也是尾节点
  6.     this.head = node;
  7.     this.tail = node;
  8.   } else { // 双向链表不为空，此时添加的 node 将会成为 头节点
  10.     // 将 node 节点的 next 指针指向当前的头节点
  11.     node.next = this.head;
  12.     // 将当前的头节点的 prev 指针指向 node 节点
  13.     this.head.prev = node;
  14.     // 将 head 指向 node，node成为新的头节点
  15.     this.head = node;
  16.   }
  18. }

第三种情景：在双向链表的尾部添加一个新元素。在这种情景下，我们需要把最后一个节点的 next 指针指向 node 节点，然后把 node 节点的 prev 指针指向双向链表中当前的尾结点，最后将 tail 属性指向 node 节点，这样新添加的node节点就成为了新的尾结点了。

  1. else if (index === this.count) {
  2.   // 在双向链表的尾部插入元素，此时添加的 node 将会成为 尾节点
  4.   current = this.tail;
  5.   // 将当前的尾节点的 next 指针指向 node 节点
  6.   current.next = node;
  7.   // 将 node 节点的 prev 指针指向当前的尾节点
  8.   node.prev = current;
  9.   // 将 tail 属性指向 node，node成为新的尾节点
  10.   this.tail = node;
  12. }

第四种情景：在链表的中间插入一个新元素。在这种情景下，我们需要迭代双向链表找到要插入的位置。调用 getElementAt 方法找到插入位置的前一个节点 previous，然后将 插入位置的下一个节点 previous.next 赋值给 current 变量。我们现在要做的就是在 previous 和 current 之间插入新节点，首先将新插入的节点 node 的next 指针指向 current ，previous 的 next 指针指向 node 节点，然后再将 current 的 prev 指针指向 node 节点，node 节点的 prev 指针指向 previous ，这样，新节点 node 就插入了 previous 和 current 之间。

  1. else {
  2.   // 在双向链表的其他位置插入元素
  4.   // 首先获取插入位置的前一个节点
  5.   const previous = this.getElementAt(index - 1);
  6.   // 插入位置的后一个节点
  7.   current = previous.next;
  8.   // 将 node 节点插入 previous 和 current 之间
  9.   // 则将 node 的 next 指针指向 current，prev 指针指向 previous
  10.   node.next = current;
  11.   node.prev = previous;
  12.   // node 节点插入后，previous 的 next 指针指向 node 节点
  13.   previous.next = node;
  14.   // current(插入位置的后一个节点) 的 prev 指针指向新插入的 node 节点
  15.   current.prev = node;
  17. }

getElementAt() 返回双向链表中特定位置的元素

getElementAt 方法返回双向链表中特定位置的元素，若元素不存在，返回 undefined

  1. getElementAt(index) {
  2.   // 传入的位置合法，迭代双向链表查找目标位置的元素
  3.     if (index >= 0 && index <= this.count) {
  4.     // 从第一个元素迭代双向链表
  5.       let node = this.head;
  6.     for (let i = 0; i < index && node != null; i++) {
  7.       // 迭代整个双向链表直到目标 index，结束循环时，此时的 node 元素是目标index 的前一个元素
  8.       // 因此需要使用 node.next 来获取目标 index 的元素
  9.         node = node.next;
  10.     }
  11.     return node;
  12.   }
  13.   // 传入的位置不合法，即在双向链表中找不到该位置的节点，返回 undefined
  14.   return undefined;
  15. }

代码分析：
我们首先会对传入的 index 参数做合法性检查，如果传入的位置是不合法的参数，我们会返回 undefined，因为这个位置在双向链表中不存在。

然后从双向链表的第一个节点开始，迭代整个链表直到目标index，当结束循环时，node 就是我们要查找的目标节点。

remove 从双向链表中移除一个元素

  1. remove(element) {
  2.     const index = this.indexOf(element);
  3.   return this.removeAt(index)
  4. }

removeAt 从双向链表的特定位置移除一个元素

removeAt 方法从双向链表的特定位置移除一个元素。我们需要处理四种情景：

  • 移除的位置不合法，元素移除失败
  • 移除双向链表中的第一个元素
  • 移除双向链表的最后一个元素
  • 移除双向链表中间的元素
  1. removeAt(index) {
  2.     if (index >= 0 && index < this.count) {
  3.     // current 变量是对双向链表中第一个节点的引用
  4.       let current = this.head;
  5.     if (index === 0) {
  6.         // 删除双向链表的头部元素
  8.       // 删除头部元素，把 head 指向第二个节点即可
  9.       this.head = this.head.next;
  10.       if (this.count === 1) {
  11.         // 链表只有一个节点时，该节点的 prev 指针和 next 指针都为 null
  12.         // 如果链表中只有一个节点，删除了头部节点，就变成了空的双向链表
  13.         // 因此需要将 tail 设为 null
  14.           this.tail = null;
  15.       } else {
  16.         // 将新的头部节点的 prev 指针设为 null
  17.           this.head.prev = null;
  18.       }
  20.     } else if (index === this.count - 1) {
  21.         // 删除双向链表的尾部元素
  23.       current = this.tail;
  24.       // tail 是对最后一个元素的引用，删除最后一个元素，直接将 tail 的引用更新为倒数第二个元素即可
  25.       this.tail = current.prev;
  26.       // 将新的尾部元素的 next 指针设为 null
  27.       this.tail.next = null;
  29.     } else {
  30.         // 删除双向链表的中间元素
  32.       // current 变量就是要删除的元素
  33.       current = this.getElementAt(index);
  34.       // 要删除元素的前一个元素
  35.       const previous = current.prev;
  36.       // 将 previous 的 next 指针指向要删除元素的下一个元素
  37.       previous.next = current.next;
  38.       // 将 要删除元素的下一个元素的 prev 指针指向 previous
  39.       current.next.prev = previous;
  41.     }
  43.     this.count--;
  44.     return current.element;
  45.   }
  47.   return undefined;
  48. }

接下来，我们分析一下这四种情景：

第一种情景：移除的位置不合法。由于 removeAt 方法是根据位置 (index) 移除双向链表中的元素，因此我们首先需要对 index 进行有效性检查。从 0（包括 0 ）到双向链表的长度（count - 1）都是有效的位置。如果 index 不是有效的位置，就返回 undefined，即没有从链表中移除元素。

第二种情景：移除双向链表中的第一个元素。要移除双向链表中的第一个元素，我们把 head 的引用改为双向链表中的第二个元素（current.next）即可，同时还要将链表中的第二个元素的 prev 指针设为null，因为双向链表的第一个元素的 prev 指针永远都为 null（或 undefined）。如果双向链表中只有一个元素，移除了双向链表的第一个元素（也是最后一个元素），那么双向链表就为空了，此时我们还需要将 tail 设为 null。

  1. if (index === 0) {
  2.   // 删除双向链表的头部元素
  4.   // 删除头部元素，把 head 指向第二个节点即可
  5.   this.head = this.head.next;
  6.   if (this.count === 1) {
  7.     // 链表只有一个节点时，该节点的 prev 指针和 next 指针都为 null
  8.     // 如果链表中只有一个节点，删除了头部节点，就变成了空的双向链表
  9.     // 因此需要将 tail 设为 null
  10.     this.tail = null;
  11.   } else {
  12.     // 将新的头部节点的 prev 指针设为 null
  13.     this.head.prev = null;
  14.   }
  15. }

第三种情景：移除双向链表的最后一个元素。因为我们已经有对双向链表最后一个元素的引用，因此我们可以很方便地移除最后一个元素。我们只需将 tail 的引用指向双向链表中倒数第二个元素即可，既然 tail 指向了倒数第二个元素，我们只需要将 next 指针设为 null 就可以了。这样，双向链表中的最后一个元素自然就被移除了。

  1. else if (index === this.count - 1) {
  2.   // 删除双向链表的尾部元素
  4.   current = this.tail;
  5.   // tail 是对最后一个元素的引用，删除最后一个元素，直接将 tail 的引用更新为倒数第二个元素即可
  6.   this.tail = current.prev;
  7.   // 将新的尾部元素的 next 指针设为 null
  8.   this.tail.next = null;
  10. }

第四种情景：从双向链表中间移除一个元素。首先需要迭代双向链表，直到找到要移除的位置。我们将要移除的元素赋值给 current 变量，那么要移除元素的上一个元素就是 previous = current.prev，要移除元素的下一个元素就是
current.next，我们只需要将 previous 的 next 指针指向 current.next，current.next 的 prev 指针指向 previous ，就可以断开与要移除元素的连接，从而将要移除元素移除掉。

  1. else {
  2.   // 删除双向链表的中间元素
  4.   // current 变量就是要删除的元素
  5.   current = this.getElementAt(index);
  6.   // 要删除元素的前一个元素
  7.   const previous = current.prev;
  8.   // 将 previous 的 next 指针指向要删除元素的下一个元素
  9.   previous.next = current.next;
  10.   // 将 要删除元素的下一个元素的 prev 指针指向 previous
  11.   current.next.prev = previous;
  12. }

removeHead 移除首节点

  1. removeHead() {
  2.   if (this.head == null) {
  3.       return undefined;
  4.   }
  6.   const current = this.head;
  8.  // 删除头部元素，把 head 指向第二个节点即可
  9.   this.head = this.head.next;
  10.   if (this.count === 1) {
  11.     // 链表只有一个节点时，该节点的 prev 指针和 next 指针都为 null
  12.     // 如果链表中只有一个节点，删除了头部节点，就变成了空的双向链表
  13.     // 因此需要将 tail 设为 null
  14.     this.tail = null;
  15.   } else {
  16.     // 将新的头部节点的 prev 指针设为 null
  17.     this.head.prev = null;
  18.   }
  20.   return current.element;
  21. }

如果双向链表只有一个节点，移除首节点，双向链表就为空了，此时除了要将 head 设为 null，还需要将 tail 也设为 null；
如果双向链表中不止一个节点，移除首节点，只需将 head 指向双向链表的第二个节点，然后将第二个节点的 prev 指针设为 null 就可以了。

removeTail 移除尾结点

  1. removeTail() {
  2.   // 空链表
  3.   if (this.head == null) {
  4.       return undefined;
  5.   }
  7.   // current 变量是对尾结点的引用
  8.     const current = this.tail;
  9.   // tail 是对最后一个元素的引用，删除最后一个元素，直接将 tail 的引用更新为倒数第二个元素即可
  10.   this.tail = current.prev;
  11.   // 将新的尾部元素的 next 指针设为 null
  12.   this.tail.next = null;
  13.   return current.element;
  14. }

因为 tail 属性是对双向链表的最后一个节点的引用，要移除尾节点，直接将 tail 的引用更新为双向链表的倒数第二个节点，并将倒数第二个节点的 next 指针设为 null 即可。

indexOf 返回指定元素在双向链表中的索引

indexOf 方法接收一个元素的值，如果在双向链表中找到了它，就返回该元素的位置，否则就返回 -1，表示在双向链表中没有找到该元素

  1. indexOf(element) {
  2.   // current 变量是对双向链表中第一个元素（即首节点）的引用
  3.     let current = this.head;
  4.   // 迭代链表，从 head（索引为 0）开始
  5.   let index = 0;
  6.   while(current != null) {
  7.     // 比较当前节点的元素与目标元素是否相等，若相等，当前节点就是我们要找的节点，返回当前节点的位置
  8.       if (this.equalsFn(element, current.element)) {
  9.         return index;
  10.     }
  12.     // 不是我们要找的节点，继续迭代下一个节点
  13.     index++;
  14.     current = current.next;
  15.   }
  17.   // 双向链表为空或者迭代到双向链表尾部，没有找到目标元素，返回 -1
  18.   return -1
  19. }

代码分析：

从双向链表中查找某个节点的位置，需要对双向链表进行迭代。我们从第一个元素 head (索引 0) 开始，一直到 current 为 null为止，也就是迭代到双向链表的尾部。

在每次迭代时，我们都会验证 current 节点的元素和目标元素是否相等，如果相等，当前位置的元素就是我们要找的元素，返回该元素的位置。如果不是我们要找的元素，则继续迭代下一个节点。

如果双向链表为空或者迭代到了双向链表的尾部，都没有找到我们想要的元素，就返回 -1。

head 返回首节点

  1. head() {
  2.     return this.head;
  3. }

tail 返回尾结点

  1. tail() {
  2.     return this.tail;
  3. }

size 返回双向链表包含的元素个数

size 方法返回双向链表的节点个数，即返回双向链表的长度。DoublyLinkList 是我们自己构建的类，其长度是我们使用 count 变量来控制的，因此返回双向链表的长度，就是返回 count 变量。

  1. size() {
  2.     return this.count;
  3. }

isEmpty 判断双向链表是否为空

isEmpty 方法判断双向链表是否为空。如果双向链表中没有元素，isEmpty 就会返回 true，否则返回 false

  1. isEmpty() {
  2.     return this.size() === 0
  3. }

clear 清空双向链表

  1. clear() {
  2.     this.head = null;
  3.   this.tail = null;
  4.   this.count = 0;
  5. }

toString() 返回表示整个双向链表的字符串

toString 方法将 DoublyLinkList 对象转换成一个字符串，然后返回双向链表内容的字符串。

  1. toString() {
  2.     if (this.head == null) {
  3.       return '';
  4.   }
  6.   let objString = `${this.head.element}`;
  7.   let current = this.head.next;
  8.   while(current != null) {
  9.       objString = `${objString}, ${current.element}`;
  10.     current = current.next;
  11.   }
  13.   return objString;
  14. }

代码分析：

首先，如果双向链表为空，我们就返回一个空字符串；

如果双向链表不为空，我们首先用双向链表第一个元素的值来初始化方法返回的字符串objString。然后迭双向代链表的所有其它元素，将元素值添加到字符串 objString 上；

当迭代完双向链表后，返回双向链表内容的字符串。

inverseToString() 返回双向链表从尾到头的字符串

inverseToString 方法将 DoublyLinkList 对象转换成一个字符串，然后返回双向链表从尾到头的字符串。

  1. inverseToString() {
  2.     if (this.tail != null) {
  3.       return ''
  4.   }
  6.   let objString = `${this.tail.element}`;
  7.   let previous = this.tail.prev;
  8.   while(previous != null) {
  9.       objString = `${objString}, ${previous.element}`;
  10.     previous = previous.prev;
  11.   }
  13.   return 
  14. }

代码分析：

首先，如果双向链表为空，我们就返回一个空字符串；

如果双向链表不为空，我们首先用双向链表的尾部元素的值来初始化方法返回的字符串objString。然后从尾部开始往前迭双向代链表的所有其它元素，将元素值添加到字符串 objString 上；

当迭代完双向链表后，返回双向链表内容的字符串。

完整代码

  1. function defaultEquals(a, b) {
  2.   return a === b;
  3. }
  5. class DoublyNode {
  6.   constructor(element) {
  7.     this.element = element;
  8.     this.prev = null;
  9.     this.next = null;
  10.   }
  11. }
  14. class DoublyLinkList {
  15.     constructor(equalsFn = defaultEquals) {
  16.       this.equalsFn = equalsFn;
  17.     this.count = 0;
  18.     this.head = null;
  19.     this.tail = null;
  20.   }
  22.   append(element) {
  23.       const node = new DoublyNode(element);
  24.     if (this.head == null) {
  25.         this.head = node;
  26.       this.tail = node;
  27.     } else {
  28.         this.tail.next = node;
  29.       node.prev = this.tail;
  30.       this.tail = node;
  31.     }
  32.     this.count++;
  33.   }
  35.   insert(element, index) {
  36.       if (index >=0 && index <= this.count) {
  37.         const node = new DoublyNode(element);
  38.       let current = this.head;
  39.       if (index === 0) {
  40.           if (this.head == null) {
  41.             this.head = node;
  42.           this.tail = node;
  43.         } else {
  44.             node.next = this.head;
  45.           this.head.prev = node;
  46.           this.head = node;
  47.         }
  48.       } else if (index === this.count) {
  49.           current = this.tail;
  50.         current.next = node;
  51.         node.prev = current;
  52.         this.tail = node
  53.       } else {
  54.           const previous = this.getElementAt(index);
  55.         current = previous.next;
  56.         node.next = current;
  57.         node.prev = previous;
  58.         current.prev = node;
  59.         previous.next = node;
  60.       }
  62.       this.count++;
  63.       return true;
  64.     }
  66.     return false;
  67.   }
  69.   getElementAt(index) {
  70.       if (index >= 0 && index <= this.count) {
  71.         let node = this.head;
  72.       for (let i = 0; i < index && node != null; i++) {
  73.           node = node.next;
  74.       }
  75.       return node;
  76.     }
  78.     return undefined;
  79.   }
  81.   remove(element) {
  82.       const index = this.indexOf(element);
  83.     return this.removeAt(index);
  84.   }
  86.   removeAt(index) {
  87.       if (index >= 0 && index < this.count) {
  88.         let current = this.head;
  89.       if (index === 0) {
  90.         this.head = this.head.next;
  91.         if (this.count === 1) {
  92.             this.tail = null;
  93.         } else {
  94.             this.head.prev = null;
  95.         }
  96.       } else if (index === this.count - 1) {
  97.         current = this.tail;
  98.         this.tail = current.prev;
  99.         this.tail.next = null;
  100.       } else {
  101.           current = this.getElementAt(index);
  102.         const previous = current.prev;
  103.         previous.next = current.next;
  104.         current.next.prev = previous;
  105.       }
  107.       this.count--;
  108.       return current.element;
  109.     }
  111.     return undefined;
  112.   }
  114.   removeHead() {
  115.       if (this.head == null) {
  116.         return undefined;
  117.     }
  119.     const current = this.head;
  120.     this.head = this.head.next;
  121.     if (this.count === 1) {
  122.         this.tail = null;
  123.     } else {
  124.         this.head.prev = null;
  125.     }
  127.     return current.element;
  128.   }
  130.   removeTail() {
  131.       if (this.head = null) {
  132.         return undefined;
  133.     }
  135.     const current = this.tail;
  136.     this.tail = current.prev;
  137.     this.tail.next = null;
  139.     return current.element;
  140.   }
  142.   indexOf(element) {
  143.       let current = this.head;
  144.     let index = 0;
  145.     while(current != null) {
  146.         if (this.equalsFn(element, current.element)) {
  147.           return index;
  148.       }
  150.       index++;
  151.       current = current.next;
  152.     }
  154.     return -1;
  155.   }
  157.   head() {
  158.       return this.head;
  159.   }
  161.   tail() {
  162.       return this.tail;
  163.   }
  165.   size() {
  166.       return this.count;
  167.   }
  169.   isEmpty() {
  170.       return this.size() === 0;
  171.   }
  173.   clear() {
  174.       this.head = null;
  175.     this.tail = null;
  176.     this.count = 0;
  177.   }
  179.   toString() {
  180.       if (this.head == null) {
  181.         return '';
  182.     }
  184.     let objString = `${this.head.element}`;
  185.     let current = this.head.next;
  186.     while(current != null) {
  187.         objString = `${objString}, ${current.element}`;
  188.       current = current.next;
  189.     }
  191.     return objString;
  192.   }
  194.   inverseToString() {
  195.       if (this.head == null) {
  196.         return '';
  197.     }
  199.     let objString = `${this.tail.element}`;
  200.     let previous = this.tail.prev;
  201.     while(previous != null) {
  202.         objString = `${objString}, ${previous.element}`;
  203.       previous = previous.prev;
  204.     }
  206.     return objString;
  207.   }
  210. }

双向链表的应用

基于双向链表实现栈

使用双向链表来实现栈，而不是链表，是因为相对于栈来说，我们会向链表尾部添加元素，也会从链表尾部移除元素，我们实现的双向链表有最后一个元素的引用，无需迭代就能获取它。双向链表可以直接获取尾部的元素，减少过程消耗，它的时间复杂度和原始的 Stack 实现相同，为 O(1)。

  1. class Stack {
  2.     constructor() {
  3.       this.items = new DoublyList();
  4.   }
  6.   // 添加元素到栈
  7.   push(element) {
  8.       this.items.append(element);
  9.   }
  11.   // 从栈顶移除元素
  12.   pop() {
  13.       if (this.isEmpty()) {
  14.         return undefined;
  15.     }
  16.     return this.items.removeAt(this.size() - 1); 
  17.   }
  19.   // 查看栈顶元素
  20.   peek() {
  21.     if (this.isEmpty()) {
  22.         return undefined'
  23.     }
  24.       return this.items.tail();
  25.   }
  27.   // 检查栈是否为空
  28.   isEmtpy() {
  29.       return this.items.isEmpty();
  30.   }
  32.   // 清空栈
  33.   clear() {
  34.       this.items.clear()
  35.   }
  37.   // 返回栈里的元素个数
  38.   size() {
  39.       return this.items.size()
  40.   }
  42.   // 打印栈
  43.   print() {
  44.       return this.items.inverseToString()
  45.   }
  46. }

基于双向链表实现队列

  1. class Queue {
  2.     constructor() {
  3.       this.items = new DoublyList();
  4.   }
  6.   // 入队列
  7.   enqueue(element) {
  8.       this.items.append(element);
  9.   }
  11.   // 出队列
  12.   dequeue() {
  13.       if (this.isEmpty()) {
  14.         return undefined;
  15.     }
  17.     return this.items.removeHead();
  18.   }
  20.   // 返回队首
  21.   head() {
  22.     if (this.isEmpty()) {
  23.         return undefined;
  24.     }
  25.     return this.items.head();
  26.   }
  28.   // 返回队尾
  29.   tail() {
  30.       if(this.isEmpty()) {
  31.         return undefined;
  32.     }
  33.     return this.items.tail();
  34.   }
  36.   // 判断队列是否为空
  37.   isEmpty() {
  38.       return this.items.isEmpty();
  39.   }
  41.   // 清空队列
  42.   clear() {
  43.       this.items.clear();
  44.   }
  46.   // 返回队列长度
  47.   size() {
  48.       this.items.size()
  49.   }
  51.   // 打印队列
  52.   print() {
  53.       this.items.toString()
  54.   }
  55. }

基于双向链表实现双端队列

  1. class Deque {
  2.     constructor() {
  3.       this.items = new DoublyList()
  4.   }
  6.   // 在双端队列的前端添加元素
  7.   addFront(element) {
  8.       this.items.append(element);
  9.   }
  11.   // 在双端队列的后端添加元素
  12.   addBack(element) {
  13.       this.items.insert(element, this.size() - 1);
  14.   }
  16.   // 从双端队列的前端移除第一个元素
  17.   removeFront() {
  18.       if (this.isEmpty()) {
  19.         return undefined;
  20.     }
  21.     return this.items.removeHead();
  22.   }
  24.   // 从双端队列的后端移除一个元素
  25.   removeBack() {
  26.       if (this.isEmpty()) {
  27.         return undefined;
  28.     }
  29.     return this.items.removeTail();
  30.   }
  32.   // 查看双端队列的前端的第一个元素
  33.   peekFront() {
  34.       if (this.isEmpty()) {
  35.         return undefined;
  36.     }
  37.     return this.items.head();
  38.   }
  40.   // 查看双端队列的后端的第一个元素
  41.   peekBack() {
  42.       if (this.isEmpty()) {
  43.         return this.items.tail()
  44.     }
  45.   }
  47.   // 检查双端队列是否为空
  48.   isEmpty() {
  49.       return this.items.isEmpty();
  50.   }
  52.   // 清空双端队列
  53.   clear() {
  54.       return this.items.clear();
  55.   }
  57.   // 返回双端队列的长度
  58.   size() {
  59.       return this.items.size();
  60.   }
  62.   // 输出双端队列从队列前端到队列后端的字符串
  63.   toString() {
  64.       return this.items.toString();
  65.   }
  66. }