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

前端之家收集整理的这篇文章主要介绍了JavaScript数据结构之双向链表和双向循环链表的实现前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

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

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

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){ 
      prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current; 
      current = current.next; 
    } 

    prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next; 
    current.next.prev = prev<a href="https://www.jb51.cc/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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current; 
current = current.next; 

while(current){ 
  if (current.element = element) { 
    prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next; 
    current.next.prev = prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s; 
  }else{ 
    prev<a href="https://www.jb51.cc/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="https://www.jb51.cc/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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current; 
  current = current.next; 
} 

prev<a href="https://www.jb51.cc/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;
};
}

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

var length = 0,tail = null;

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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s; 

  if(position === 0){ 

    current.next.prev<a href="https://www.jb51.cc/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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current; 
      current = current.next; 
    } 

    prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next; 
    current.next.prev = prev<a href="https://www.jb51.cc/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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s; 
      prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = current.next; 
    } 
    length--; 
    return true; 
  } 

  prev<a href="https://www.jb51.cc/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="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s = current; 
  current = current.next; 
} 

prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank" class="keywords">IoU</a>s.next = head; 
tail = prev<a href="https://www.jb51.cc/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;
};
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程之家。

原文链接:https://www.f2er.com/js/34975.html

猜你在找的JavaScript相关文章