本文版权归博客园和作者吴双本人共同所有，转载和爬虫请注明原文链接 http://www.cnblogs.com/tdws/
下午分享了JavaScript实现单向链表，晚上就来补充下双向链表吧。对链表的实现不是很了解的可以移步：http://www.cnblogs.com/tdws/p/6033209.html
双向链表与链表的不同之处主要在于他的双向查找。因为在这种结构中我们设计了每个节点的prev（向上查找）的引用或指针和next(向下查找)的引用或指针。得益于这种结构你能做到正向和反向的查找。你也可以在查找某个index位置的元素时，根据其长度计算，到底是使用正向还是反向，这取决于你自己。
直接上代码吧，详解在注释里：
先看一下代码的整体结构：
下面是具体实现：
function DoublyLinkedList() {
var Node = function (element) {
this.element = element;
this.next = null; //下一个是谁
this.prev = null; //上一个是谁
};
var head = null;
var length = ;
var tail = ;
this.insert = function (position, element) {
if (position >= && position <= length) {
var node = new Node(element);
var current = head;
var index = ;
var previous;
if (position == ) {
if (head == null) { //空链表
head = node;
tail = node;
} else {
head = node; //新元素作为头部
head.next = current; //头部的下一个节点是旧头部
current.prev = node; //旧头部的上一个节点是新元素
}
} else if (position == length) { //尾部
current = tail;
current.next = node; //旧尾部的下一个节点 是新节点
node.prev = current; //新节点的上一个节点是旧尾部
tail = node; //更新尾部节点为新元素
} else {
while (index < position) {
previous = current;
current = current.next;
index++;
} //遍历后current为当前position的节点
node.next = current; //新节点的next是current
previous.next = node; //上节点的下一个是新元素
node.prev = previous; //新元素的上个节点是previous
current.previous = node; //current的上个节点是新元素
}
length++;
return true;
} else {
return false;
}
};
this.removeAt = function (position) {
if (position > - && position < length) {
var current = head;
var index = ;
var previous;
if (position == ) {
head = current.next; //给head赋值为 下个节点，不关心其是否为null
if (length == ) { //如果长度为1 head已经为null,则将tail置为null
tail = null;
} else { //head已经赋值为下个节点
head.prev = null; //head的prev置为null
}
} else if (position == length - ) { //最后一个元素
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) { //普通中间元素
previous = current.prev;
current = current.next;
} //遍历后得到当前position元素
previous.next = current.next; //当前osition元素的prev指向当前postion元素的下个元素
current.next.prev = previous; //总之越过一个
}
length--;
return current.element;
} else {
return null;
}
};
this.getLength = function () {
return length;
};
this.toString = function () {
var current = head;
var string = '';
while (current) {
string += ',' + current.element;
current = current.next;
}
return string;
};
}
废话也不多说了，关于双向链表的文章网上一搜一大堆。
顺便提到的就是Redis五大数据类型中的List列表类型，我们知道Redis列表我们可以正向查找元素，也可以反向查找元素。这也算是双向链表在实际中的一大用途吧。
Redis相关文章链接 http://www.cnblogs.com/tdws/tag/NoSql/
如果我的点滴分享对你能有点滴帮助，欢迎点击下方红色按钮关注，我将持续输出分享。