链表有多种不同的类型，双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
单链表的缺陷
单链表只能从头节点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。
从链表的头节点遍历到尾节点很简单，但反过来从后向前遍历则没那么简单。通过给Node对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时，向链表插入一个节点需更多的工作，需指出该节点正确的前驱和后驱。但从链表中删除节点时，效率提高了，无需再查找待删除节点的前驱节点。
function Node(element){
this.element = element;
this.prev = null;
this.next = null;
}
function Llist(){
this.head = new Node('head');
this.find = find;
this.insert = insert;
this.display = display;
this.remove = remove;
this.findLast = findLast;
this.dispReverse = dispReverse;
}
function find(item){
var current = this.head;
while(current.element!=item){
current = current.next
}
return current;
}
//双向链表的插入与单向链表类似，但需设置新节点的prev属性，使其指向该节点的前驱。
function insert(item,element){
var current = this.find(item);
var node = new Node(element);
node.prev = current;
node.next = current.next;
current.next = node;
}
// 双向链表的删除比单向链表效率更高，因为不需要再查找前驱节点。
// 首先需要在链表中找出存储带删除数据的节点，然后设置该节点前驱的next属性，使其指向待删除节点的后继。
// 设置该节点后继的previous属性，使其指向待删除节点的前驱。
function remove(item){
var current = this.find(item);
if(!(current.next==null)){
current.prev.next = current.next;
current.next.prev = current.prev;
current.next = null;
current.prev = null;
}
}
// 查找最后的节点，同时避免从前往后遍历链表。
function findLast(){
var current = this.head;
while(!(current.next==null)){
current = current.next;
}
return current;
}
// 以反序显示链表中元素
function dispReverse(){
var current = this.head;
current = this.findLast();
while(!(current.prev == null)){
print(current.element);
current = current.prev;
}
}
function display(){
var current = this.head;
while(!(current.next==null)){
print(current.next.element)
current = current.next;
}
}
var ll = new Llist();
ll.insert('head','conway');
ll.insert('conway','russellville');
ll.insert('russellville','alma');
ll.display();
print();
ll.remove('conway');
ll.display();
print();
ll.dispReverse();
双向链表实现
双向链表提供了两种迭代列表的方法：从头到尾，或反过来。也可访问一个特定节点的下一个或前一个元素。
在单向链表中，如果迭代列表时错过要找的元素，就需要回到列表起点，重新开始迭代。这就是双向链表的一个优点。
function DoublyLinkedList(){
var Node = function(element){
this.element = element;
this.prev = null;
this.next = null;
};
var length = 0;
var head = null;
var tail = null;
}
在任意位置插入新元素
-
场景1：在链表起点插入新元素
在链表起点插入元素
若链表为空只需把head和tail都指向这个新节点。如果非空，current变量将是对链表中第一个元素的引用。就像在链表中所做的，将node.next设置为current，而head将指向node（它将成为列表中第一个元素）。不同之处在于，我们还需要为指向上一个元素的指针设置一个值。current.prev指针将由指向null变成指向新元素。node.prev指针已经是null，因此无需再更新任何东西。
-
场景2：在链表最后添加新元素
在链表末尾插入元素
因为控制着指向最后一个元素的指针（tail），current变量将引用最后一个元素。然后开始建立第一个链接：node.prev将引用current。current.next指针（指向null）将指向node（由于构造函数，node.next已经指向了null）。最后是更新tail，它将由指向current变为指向node。
-
场景3：在链表中间插入新元素
在链表中间插入新元素
迭代列表直到到达要找的位置，将在current和previous元素之间插入新元素。首先，node.next将指向current，而previous.next将指向node，这样就不会丢失节点之间的链接。然后需要处理所有的链接current.prev将指向node，而node.prev将指向previous。
this.insert = function(position,element){
if(position>=0 && position<=length){
var node = new Node(element);
var current = head;
if(position==0){
if(!head){
head = node;
tail = node;
}else{
node.next = current;
current.prev = node;
head = node;
}
}else if(position === length){
current = tail;
current.next = node;
node.prev = current;
tail = node;
}else{
var index = 0;
var previous;
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node;
node.prev = previous;
}
length++;
return true;
}else{
return false;
}
};
从任意位置移除元素
-
场景1：从头部移除一个元素
current变量是对列表中第一个元素的引用，也就是想要移除的元素。需要做的是改变head的引用，将其从current修改为下一个元素（current.next）。但还需更新current.next指向上一个元素的指针，因为第一个元素的prev指针是null。因此，把head.prev的引用改为null - 因为head也指向列表中新的第一个元素，或者也可以用current.next.prev。由于还需控制tail的引用，可以检查要移除的元素是否是第一个元素。若是则只需把tail设置为null。
双向链表移除第一个元素 -
场景2：从最后一个位置移除元素
既然已有对最后一个元素的引用（tail），就无需找到它而迭代列表。可把tail的引用赋给current变量，把tail的引用更新为列表中倒数第二个元素（current.prev或tail.prev）。既然tail指向倒数第二个元素，就只需把next指针更新为null（tail.next=null）。
从最后一个位置移除元素 -
场景3：从列表中间移除一个元素
首先需要迭代列表直到到达要找的位置，current变量所引用的就是要移除的元素。要移除它可通过更新previous.next和current.next.prev的引用，在列表中跳过它。因此，previous.next将指向current.next，而current.next.prev将指向previous。
从列表中间移除一个元素
this.removeAt = function(position){
//检查越界值
if(position>-1 && position<length){
var current = head;
//移除第一项
if(position===0){
head = current.next;
//若只有一项则更新tail
if(length===1){
tail = null;
}else{
head.prev = null;
}
}else if(position === length-1){//移除最后一项
current = tail;
tail = current.prev;
tail.next = null;
}else{//移除中间相
var index = 0;
var previous;
while(index++ < position){
previous = current;
current = current.next;
}
//将previous和current的下一项链接起来，跳过current。
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
}else{
return null;
}
};
