JavaScript數據結構之雙向鏈表和雙向循環(huán)鏈表的實現
更新時間：2017年11月28日 11:52:42 作者：貳拾肆樵
本篇文章主要介紹了JavaScript數據結構之雙向鏈表和雙向循環(huán)鏈表的實現，具有一定的參考價值，感興趣的小伙伴們可以參考一下
雙向鏈表和普通鏈表的區(qū)別在于，在鏈表中，一個節(jié)點只有鏈向下一個節(jié)點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。
雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以訪問一個特定節(jié)點的下一個或前一個元素。在單向鏈表中，如果迭代列表時錯過了要找的元素，就需要回到列表起點，重新開始迭代。這是雙向鏈表的一個優(yōu)點。
雙向鏈表：單向鏈表只能向著一個方向遍歷鏈表節(jié)點，而在節(jié)點指針域中增加了前向指針的雙向鏈表，則可以向著兩個方向遍歷節(jié)點。這使得雙向鏈表也可以在任何一個節(jié)點遍歷整個鏈表。
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;
};
}
雙向循環(huán)鏈表：將雙向鏈表的頭尾指針相連，就構成了雙向循環(huán)鏈表。這種鏈表從任意一個節(jié)點都可以同時向兩個方向進行節(jié)點遍歷，查詢節(jié)點的速度也是最快的。
/*雙向循環(huán)鏈表*/
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;
};
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了詳解Javascript利用echarts畫空氣質量地圖，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-10-10
javascript獲取客戶端IP的小程序，下面的代碼是我在所有windowsNT5.0及以上的系統(tǒng)上都測試通過的，喜歡的朋友可以收藏下2013-11-11
因為要做一個日歷控件,遇到國家法定節(jié)假日,怎么實現此功能呢?這篇文章主要給大家介紹了關于前端判斷節(jié)假日的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-08-08
這篇文章主要為大家詳細介紹了JavaScript實現手風琴效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
這篇文章主要為大家詳細介紹了基于javascript實現碰撞檢測，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要給大家深入的介紹了JavaScript中的for循環(huán)，其中包括ES5中的三種for循環(huán)，分別是簡單for循環(huán)、for-in以及forEach，另外還詳細介紹了ES6新增的一種循環(huán)：for-of ，有需要的朋友可以參考借鑒，下面來一起看看吧。2017-02-02
下面小編就為大家?guī)硪黄猨s調用屏幕寬度的簡單方法。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-11-11
這篇文章主要介紹了javascript 作用于作用域鏈的詳解的相關資料,希望通過本文能幫助到大家，理解掌握這部分內容，需要的朋友可以參考下2017-09-09
動態(tài)創(chuàng)建的表格單元格中的事件實現代碼
好久沒有搞網頁了，今天重新弄了一個 ，做個動態(tài)表格，具體的實現代碼，大家可以自己寫吧2008-12-12
uniapp和uniCloud開發(fā)中常出現的問題及解決匯總
使用uni 開發(fā)一段時間了,下面這篇文章主要給大家介紹了關于uniapp和uniCloud開發(fā)中常出現的問題及解決的相關資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2022-12-12