1.概念
上一个文章里我们已经了解到链表结构，链表的特点是长度不固定，不用担心插入新元素的时候新增位置的问题。插入一个元素的时候，只要找到插入点就可以了，不需要整体移动整个结构。
这里我们了解一下双向链表的结构。尽管从链表中头节点遍历到尾节点很容易，但是反过来，从后向前遍历就没有那么简单。通过给Node对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时祥链表中插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后续。但是在从链表中删除节点的时候效率更高了，不需要再查找待删除节点的前驱节点了。如下图1演示了双向链表的工作原理。
图1
首先是要为Node类增加一个previouse属性，这个属性指向当前节点的前驱：
function Node(element){ this.element = element; this.next = null; this.previous = null; }
双向链表的insert()方法和单项链表的类似，但是需要设置新节点的previouse属性，是其指向该节点的前驱。该方法的定义如下：
function insert(newElement , item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; newNode.previous = current; current.next = newNode; }
双向链表的删除remove()方法币单项链表的效率更高，因为不需要查找前驱节点了。首选需要在链表中找出存储待删除数据的节点，然后设置该节点的next属性，使其指向待删除节点的后续。设置该节点的后续的previouse的属性，使其指向待删除节点的前驱。如下图2展示删除节点的过程：
图2
remove()方法的定义如下：
function remove(item){ var currNode = this.find(item); if(!(currNode.next == null)){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } }
为了实现反向显示链表中元素的任务，需要给链表增加一个工具方法，用来查找链表中最后一个节点。findLast()方法找出链表中最后一个节点，同时免除从前往后遍历之苦。如下：
function findLast(){ var currNode = this.head; while (!(currNode.next == null)){ currNode = currNode.next; } return currNode; }
有了这个工具方法之后就，就可以很容易的写出反向显示双向链表的元素的方法，dispReverse()方法如下所示：
function dispReverse(){ var currNode = this.head; currNode = this.findLast(); while (!(currNode.previous == null)){ document.write(currNode.element + ' '); currNode = currNode.previous; } }
2.代码实现
双向链表就上面一些特性，下面是完整的代码实现和测试代码：
function Node(element){ this.element = element; this.next = null; this.previous = 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 dispReverse(){ var currNode = this.head; currNode = this.findLast(); while (!(currNode.previous == null)){ document.write(currNode.element + ' '); currNode = currNode.previous; } } function findLast(){ var currNode = this.head; while (!(currNode.next == null)){ currNode = currNode.next; } return currNode; } function remove(item){ var currNode = this.find(item); if(!(currNode.next == null)){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } } function display(){ var currNode = this.head; while (!(currNode.next == null)){ document.write(currNode.next.element + ' '); currNode = currNode.next; } } function find(item){ var currNode = this.head; while (currNode.element != item){ currNode = currNode.next; } return currNode; } function insert(newElement , item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; newNode.previous = current; current.next = newNode; } var cities = new LList(); cities.insert('Conway','head'); cities.insert('Russellville', 'Conway'); cities.insert('Carlisle', 'Russellville'); cities.insert('Alma' , 'Carlisle'); cities.display(); document.write('<br>'); cities.remove('Carlisle'); cities.display(); document.write('<br>'); cities.dispReverse();
作者：Tyler Ning
出处：http://www.cnblogs.com/tylerdonet/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，如有问题，可以通过以下邮箱地址williamningdong@gmail.com 联系我，非常感谢。
