JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

來源：懂視網責編：小采時間：2020-11-27 22:24:40

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現:雙向鏈表和普通鏈表的區別在于，在鏈表中，一個節點只有鏈向下一個節點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或者反過來。我們也可以訪問一個特定節點的下一個

推薦度：

點擊下載本文 文檔為doc格式

導讀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; 
 }; 
}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

推薦度：

點擊下載本文 文檔為doc格式

標簽：數據實現 js

熱門焦點

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

JavaScript數據結構之雙向鏈表和雙向循環鏈表的實現

最新推薦

猜你喜歡

熱門推薦