JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表和雙向循環(huán)鏈表的實現(xiàn)
更新時間：2017年11月28日 11:52:42 作者：貳拾肆樵
本篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表和雙向循環(huán)鏈表的實現(xià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)鏈表：將雙向鏈表的頭尾指針相連，就構(gòu)成了雙向循環(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;
};
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表定義與使用方法示例
- 使用JavaScript實現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)的代碼
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)鏈表知識詳解
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
- JavaScript實現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)實例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表各種操作詳解
相關(guān)文章
這篇文章主要為大家詳細介紹了原生js生成圖片驗證碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-10-10
比較詳細的關(guān)于javascript中void(0)的具體含義解釋
比較詳細的關(guān)于javascript中void(0)的具體含義解釋...2007-08-08
這篇文章主要為大家詳細介紹了js實現(xiàn)點擊切換和自動播放的輪播圖，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
使用Taro實現(xiàn)小程序商城的購物車功能模塊的實例代碼
這篇文章主要介紹了使用Taro實現(xiàn)的小程序商城的購物車功能模塊,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06
JavaScript實現(xiàn)數(shù)據(jù)類型的相互轉(zhuǎn)換
這篇文章主要為大家詳細介紹了JavaScript實現(xiàn)數(shù)據(jù)類型的相互轉(zhuǎn)換，感興趣的朋友可以參考一下2016-03-03
超贊的動手創(chuàng)建JavaScript框架的詳細教程
這篇文章主要介紹了動手創(chuàng)建JavaScript框架的詳細教程,包括DOM和各種屬性的調(diào)試等各個方面,超級推薦!需要的朋友可以參考下2015-06-06
這篇文章主要介紹了javascript實現(xiàn)的閉包簡單實現(xiàn)方法,涉及javascript閉包的原理與實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
手機開發(fā)必備技巧：javascript及CSS功能代碼分享
這篇文章主要介紹了手機開發(fā)必備技巧：javascript及CSS功能代碼分享,本文講解了viewport(可視區(qū)域)操作、鏈接操作、javascript事件等內(nèi)容,需要的朋友可以參考下2015-05-05
JavaScript數(shù)組Array對象增加和刪除元素方法總結(jié)
這篇文章主要介紹了JavaScript數(shù)組Array對象增加和刪除元素方法,實例總結(jié)了pop方法、push方法、splice方法、concat方法等的使用技巧,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了微信小程序基于Taro的分享圖片功能實踐詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07