双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素。
双向链表提供了两种迭代列表的方法:从头到尾,或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代。这是双向链表的一个优点。
双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针的双向链表,则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。
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){
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next;
current.next.prev = prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
};
length-- ;
return current.element;
}else{
return false;
}
};
this.remove = function(element){
var current = head,prevIoUs;
if(current.element === element){
head = current.next;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
while(current){
if (current.element = element) {
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next;
current.next.prev = prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
}else{
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if (length === 0) {
return false;
};
var current = head,prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(current){
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.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;
};
}
双向循环链表:将双向链表的头尾指针相连,就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历,查询节点的速度也是最快的。
this.append = function(element){
var node = new Node(element),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),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,prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
if(position === 0){
current.next.prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = 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){
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next;
current.next.prev = prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
}
length--;
return true;
}else{
return false;
}
};
this.remove = function(element){
var current = head,indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck === 0){
current.next.prev = tail;
head = current.next;
}else{
current.next.prev = prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s;
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next;
}
length--;
return true;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
indexCheck++;
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,indexCheck = 0;
if(length === 1){
head = null;
tail = null;
length--;
return current.element;
}
while(indexCheck++ < length){
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current;
current = current.next;
}
prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = head;
tail = prev<a href="/tag/IoU/" target="_blank" class="keywords">IoU</a>s.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;
};
}