双向链表
在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素， 如下图所示：
实现一个双向链表类，包含在任意位置插入新元素和从任意位置移除元素两个方法，代码如下：
function DoublyLinkedList() { let Node = function(element){ this.element = element; this.next = null; this.prev = null; //新增的 }; let length = 0; let head = null; let tail = null; //新增的 //这里是方法 //在任意位置插入新元素 this.insert = function(position, element){ //检查越界值 if (position >= 0 && position <= length){ let node = new Node(element), current = head, previous, index = 0; if (position === 0){ //在第一个位置添加 if (!head){ //新增的 {1} head = node; tail = node; } else { node.next = current; current.prev = node; //新增的 {2}current.prev指针将由指向null变为指向新元素 head = node; } } else if (position === length) { //最后一项 //新增的 current = tail; // {3}current变量将引用最后一个元素 current.next = node; node.prev = current; tail = node; } else { while (index++ < position){ //{4} previous = current; current = current.next; } node.next = current; //{5}node.next将指向current previous.next = node; current.prev = node; //新增的 node.prev = previous; //新增的 } length++; //更新列表的长度 return true; } else { return false; } };
// 从任意位置移除元素 this.removeAt = function(position){ //检查越界值 if (position > -1 && position < length){ let current = head, previous, index = 0; //移除第一项 if (position === 0){ head = current.next; // {1}将其从current 改为下一个元素 //如果只有一项，更新tail //新增的 if (length === 1){ // {2}是否是第一个元素，如果是，只需要把tail也设为null tail = null; } else { head.prev = null; // {3}把head.prev的引用改为null } } else if (position === length-1){ //最后一项 //新增的 current = tail; // {4}把tail的引用赋给current变量 tail = current.prev; tail.next = null; } else { while (index++ < position){ // {5} previous = current; current = current.next; } //将previous与current的下一项链接起来——跳过current previous.next = current.next; // {6} current.next.prev = previous; //新增的 } length--; return current.element; } else { return null; } }; }
1. 任意位置插入新元素
1.1分析第一种场景：在列表的第一个位置（列表的起点）插入一个新元素。如果列表为空（行{1} ），只需要把head 和tail 都指向这个新节点。如果不为空，current 变量将是对列表中第一个元素的引用。
就像我们在链表中所做的，把node.next 设为current ，而head 将指向node （它将成为列表中的第一个元素）。不同之处在于，我们还需要为指向上一个元素的指针设一个值。current.prev 指针将由指向
null 变为指向新元素（node—— 行{2} ）。node.prev 指针已经是null ，因此不需要再更新任何东西。下图演示了这个过程：
1.2假如我们要在列表最后添加一个新元素。这是一个特殊情况，因为我们还控制着指向最后一个元素的指针（tail ）。current 变量将引用最后一个元素（行{3} ）。然后开
始建立第一个链接：node.prev 将引用current 。current.next 指针（指向null ）将指向node（由于构造函数，node.next 已经指向了null ）。然后只剩一件事了，就是更新tail ，它将由指
向current 变为指向node 。下图展示了这些行为：
1.3 在列表中间插入一个新元素。就像我们在之前的方法中所做的，迭代列表，直到到达要找的位置（行{4} ）。我们将在current 和previous 元素之间插入新元素。首
先，node.next 将指向current （行{5} ），而previous.next 将指向node ，这样就不会丢失节点之间的链接。然后需要处理所有的链接：current.prev 将指向node ，而node.prev 将指向
previous 。下图展示了这一过程：
2.从任意位置移除元素
2.1我们来看看如何移除第一个元素。current 变量是对列表中第一个元素的引用，也就是我们想移除的元素。需要做的就是改变head 的引用， 将其从current 改为下一个元素
（current.next—— 行{1} ）。但我们还需要更新current.next 指向上一个元素的指针（因为第一个元素的prev 指针是null ）。因此，把head.prev 的引用改为null （行{3}—— 因为head 也
指向列表中新的第一个元素，或者也可以用current.next.prev ）。由于还需要控制tail 的引用，我们可以检查要移除的元素是否是第一个元素，如果是，只需要把tail 也设为null （行{2} ）。
下图勾画了从双向链表移除第一个元素的过程：
2.2 从最后一个位置移除元素。既然已经有了对最后一个元素的引用（tail ），我们就不需要为找到它而迭代列表。这样我们也就可以把tail 的引用赋给current 变量（行{4} ）。
接下来，需要把tail 的引用更新为列表中倒数第二个元素（current.prev ，或者tail.prev也可以）。既然tail 指向了倒数第二个元素，我们就只需要把next 指针更新为null （tail.next
= null ）。下图演示了这一行为：
2.3 从列表中间移除一个元素。首先需要迭代列表，直到到达要找的位置（行{5} ）。current 变量所引用的就是要移除的元素。那么要移除它，我们可以通过更新
previous.next 和current.next.prev 的引用，在列表中跳过它。因此，previous.next 将指向current.next ，而current.next.prev 将指向previous ，如下图所示：
