JavaScript数据结构之双向链表和双向循环链表的实现

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。

双向链表：单向链表只能向着一个方向遍历链表节点，而在节点指针域中增加了前向指针的双向链表，则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。

function DoublyLinkedList() { 
 var Node = function(element) { 
 this.element = element; 
 this.next = null; 
 this.prev = null; 
 }; 
 
 var length = 0, 
 head = null, 
 tail = null; 
 
 this.append = function(element){ 
 var node = Node(element), 
 current, 
 previous; 
 
 if(!head){ 
 head = node; 
 tail = node; 
 }else{ 
 current = head; 
 while(current){ 
 previous = current; 
 current = current.next; 
 } 
 
 node.next = current; 
 current.prev = node; 
 previous.next = node; 
 node.prev = previous; 
 } 
 
 length++; 
 return true; 
 } 
 
 this.insert = function(position,element){ 
 if(position > -1 && position < length){ 
 var node = new Node(element), 
 current = head, 
 previous, 
 index = 0; 
 
 if(position === 0){ 
 
 if(!head){ 
 head = node; 
 tail = node; 
 }else{ 
 node.next = current; 
 current.prev = node; 
 head = node; 
 } 
 
 }else if (position === length -1){ 
 current = tail; 
 current.next = node; 
 node.prev = current; 
 }else { 
 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; 
 } 
 }; 
 
 this.removeAt = function(position){ 
 if(position > -1 && position < length){ 
 var current = head, 
 index = 0, 
 previous; 
 
 if (position === 0) { 
 head = current.next; 
 
 if(length === 1){ 
 tail = null; 
 }else{ 
 head.prev = null; 
 } 
 }else if(position === length - 1){ 
 current = tail; 
 tail = current.prev; 
 tail.next = null; 
 } else{ 
 while(index++ < position){ 
 previous = current; 
 current = current.next; 
 } 
 
 previous.next = current.next; 
 current.next.prev = previous; 
 }; 
 length-- ; 
 
 return current.element; 
 }else{ 
 return false; 
 } 
 }; 
 
 this.remove = function(element){ 
 var current = head, 
 previous; 
 
 if(current.element === element){ 
 head = current.next; 
 } 
 previous = current; 
 current = current.next; 
 
 while(current){ 
 if (current.element = element) { 
 previous.next = current.next; 
 current.next.prev = previous; 
 }else{ 
 previous = current; 
 current = current.next; 
 } 
 } 
 return false; 
 }; 
 
 this.remove = function(){ 
 if (length === 0) { 
 return false; 
 }; 
 
 var current = head, 
 previous; 
 
 if(length === 1){ 
 head = null; 
 tail = null; 
 length--; 
 return current.element; 
 } 
 
 while(current){ 
 previous = current; 
 current = current.next; 
 } 
 
 previous.next = null; 
 length--; 
 return current.element; 
 }; 
 
 this.indexOf = function(element){ 
 var current = head, 
 index = 0; 
 
 while(current && index++ < length){ 
 if (current.element === element) { 
 return index; 
 }; 
 current = current.next; 
 } 
 
 return false; 
 }; 
 
 this.isEmpty = function(){ 
 return length === 0; 
 }; 
 
 this.size = function(){ 
 return length; 
 }; 
 
 this.toString = function(){ 
 var current = head, 
 string = ''; 
 
 while(current){ 
 string += current.element; 
 current = current.next; 
 } 
 return string; 
 }; 
 
 this.getHead = function(){ 
 return head; 
 }; 
 
 this.getTail = function(){ 
 return tail; 
 }; 
} 

双向循环链表：将双向链表的头尾指针相连，就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历，查询节点的速度也是最快的。

/*双向循环链表*/ 
function DoublyCircularLinkedList(){ 
 var Node = function(element){ 
 this.element = element; 
 this.next = null; 
 this.prev = null; 
 }; 
 
 var length = 0, 
 head = null, 
 tail = null; 
 
 this.append = function(element){ 
 var node = new Node(element), 
 current, 
 previous; 
 
 if (!head) { 
 head = node; 
 tail = node; 
 head.prev = tail; 
 tail.next = head; 
 }else{ 
 current = head; 
 
 while(current.next !== head){ 
 previous = current; 
 current = current.next; 
 } 
 
 current.next = node; 
 node.next = head; 
 node.prev = current; 
 }; 
 
 length++; 
 return true; 
 }; 
 
 this.insert = function(position, element){ 
 if(position >= 0 && position <= length){ 
 var node = new Node(element), 
 index = 0, 
 current = head, 
 previous; 
 
 if(position === 0){ 
 
 if(!head){ 
 
 node.next = node; 
 node.tail = node; 
 head = node; 
 tail = node; 
 
 }else{ 
 
 current.prev = node; 
 node.next = current; 
 head = node; 
 node.prev = tail; 
 
 } 
 
 }else if(position === length){ 
 current = tail; 
 
 current.next = node; 
 node.prev = current; 
 tail = node; 
 node.next = head; 
 }else{ 
 
 while(index++ < position){ 
 previous = current; 
 current = current.next; 
 } 
 
 current.prev = node; 
 node.next = current; 
 previous.next = node; 
 node.prev = previous; 
 
 } 
 
 length++; 
 return true; 
 }else{ 
 return false; 
 } 
 }; 
 
 this.removeAt = function(position){ 
 if(position > -1 && position < length){ 
 
 var current = head, 
 index = 0, 
 previous; 
 
 if(position === 0){ 
 
 current.next.previous = tail; 
 head = current.next; 
 
 }else if(position === length - 1){ 
 
 current = tail; 
 
 current.prev.next = head; 
 head.prev = current.prev; 
 tail = current.prev; 
 }else{ 
 
 while(index++ < position){ 
 previous = current; 
 current = current.next; 
 } 
 
 previous.next = current.next; 
 current.next.prev = previous; 
 
 } 
 
 length--; 
 return true; 
 }else{ 
 return false; 
 } 
 }; 
 
 this.remove = function(element){ 
 var current = head, 
 previous, 
 indexCheck = 0; 
 
 while(current && indexCheck < length){ 
 if(current.element === element){ 
 if(indexCheck === 0){ 
 current.next.prev = tail; 
 head = current.next; 
 }else{ 
 current.next.prev = previous; 
 previous.next = current.next; 
 } 
 length--; 
 return true; 
 } 
 
 previous = current; 
 current = current.next; 
 indexCheck++; 
 } 
 
 return false; 
 }; 
 
 this.remove = function(){ 
 if(length === 0){ 
 return false; 
 } 
 
 var current = head, 
 previous, 
 indexCheck = 0; 
 
 if(length === 1){ 
 head = null; 
 tail = null; 
 length--; 
 return current.element; 
 } 
 
 while(indexCheck++ < length){ 
 previous = current; 
 current = current.next; 
 } 
 
 previous.next = head; 
 tail = previous.next; 
 length--; 
 return current.element; 
 }; 
 
 this.indexOf = function(element){ 
 var current = head, 
 index = 0; 
 
 while(current && index++ < length){ 
 if(current.element === element){ 
 return index; 
 } 
 current = current.next; 
 } 
 
 return false; 
 }; 
 
 this.toString = function(){ 
 var current = head, 
 indexCheck = 0, 
 string = ''; 
 
 while(current && indexCheck < length){ 
 string += current.element; 
 indexCheck++; 
 current = current.next; 
 } 
 
 return string; 
 }; 
 
 this.isEmpty = function(){ 
 return length === 0; 
 }; 
 
 this.getHead = function(){ 
 return head; 
 }; 
 
 this.getTail = function(){ 
 return tail; 
 }; 
 
 this.size = function(){ 
 return length; 
 }; 
}