JavaScript實(shí)現(xiàn)雙向鏈表過程解析
一、什么是雙向鏈表
我們知道單鏈表只能從頭遍歷到尾或從尾遍歷到頭（一般從頭遍歷到尾），即鏈表相連的過程是單向的，實(shí)現(xiàn)的原理是上一個(gè)鏈表中有一個(gè)指向下一個(gè)的引用。它有一個(gè)比較明顯的缺點(diǎn)：
我們可以輕松的到達(dá)下一個(gè)節(jié)點(diǎn)，但是回到前一個(gè)節(jié)點(diǎn)是很困難的，但是，在實(shí)際開發(fā)中，經(jīng)常會(huì)遇到需要回到上一個(gè)節(jié)點(diǎn)的情況，所以這里就需要雙向鏈表。
所謂雙向鏈表就是：既可以從頭遍歷到尾，又可以從尾遍歷到頭的鏈表，但是，雙向鏈表也是有缺點(diǎn)的，比如：每次在插入或刪除某個(gè)節(jié)點(diǎn)的時(shí)候，需要處理四個(gè)節(jié)點(diǎn)的引用，而不是兩個(gè)，并且相對于單鏈表而言，占用內(nèi)存會(huì)更大一些，但是這些缺點(diǎn)和我們使用起來的方便程度相比，是微不足道的。
我們就來看看雙向鏈表的結(jié)構(gòu)圖。如下所示：
雙向鏈表的特點(diǎn)：
- 可以使用一個(gè)head和一個(gè)tail分別指向頭部和尾部的節(jié)點(diǎn)
- 每個(gè)節(jié)點(diǎn)由三部分組成，前一個(gè)節(jié)點(diǎn)的指針（prev）、保存的元素（data）、后一個(gè)節(jié)點(diǎn)的指針（next）
- 雙向鏈表的第一個(gè)節(jié)點(diǎn)的prev是null
- 雙向鏈表的最后的節(jié)點(diǎn)的next是null
我們可以將其抽象為：
知道了雙向鏈表的結(jié)構(gòu)，我們在一起來看看雙向鏈表的封裝。
二、雙向鏈表的封裝
首先，我們封裝一個(gè)DoublyLinkedList類，用于表示鏈表結(jié)構(gòu)，在這個(gè)類里面在封裝一個(gè)內(nèi)部類Node，用于封裝每一個(gè)節(jié)點(diǎn)上的信息（指向前一個(gè)節(jié)點(diǎn)的引用、數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的引用），然后在Node類中保存三個(gè)屬性，一個(gè)是鏈表的長度，一個(gè)是鏈表中的頭結(jié)點(diǎn)，一個(gè)是鏈表的尾節(jié)點(diǎn)。如下所示：
function DoublyLinkedList(){
this.head = null;
this.tail = null;
this.length = 0;
function Node(data){
this.data = data;
this.prev = null;
this.next = null;
}
三、雙向鏈表的常用操作
然后可以在里面添加雙向鏈表常用的操作：
append（element:向列表尾部添加一個(gè)項(xiàng)
insert(position,element):向列表的特定位置插入一個(gè)項(xiàng)
get(position):獲取對應(yīng)位置的元素
indexOf(element):返回元素在列表中的索引，如果列表中沒有該元素則返回-1
update(position，ele):修改某個(gè)位置的元素
removeAt(position):從列表的指定位置移除一項(xiàng)
remove(element):從列表中移除一項(xiàng)
isEmpty():如果鏈表中不包含任何元素，返回true,如果鏈表長度大于0返回false
size():返回鏈表包含的元素個(gè)數(shù)，與數(shù)組的length屬性相關(guān)
toString():由于列表項(xiàng)用到了Node類，需要重寫繼承自JavaScript對象默認(rèn)的toString方法，讓其輸出元素的值
forwardString():返回正向遍歷的節(jié)點(diǎn)字符串形式
backwardString():返回反向遍歷的節(jié)點(diǎn)字符串形式
接下來們就來一個(gè)一個(gè)實(shí)現(xiàn)。
1、append（element)方法-----向列表尾部添加一個(gè)項(xiàng)
這個(gè)方法和單鏈表的方法相似，先創(chuàng)建一個(gè)新列表，在判斷鏈表是否為空，如果為空，則直接讓鏈表的頭部指向新建立的鏈表。如果不為空，則讓新節(jié)點(diǎn)的前驅(qū)指針指向鏈表尾部，鏈表尾部的節(jié)點(diǎn)指向新鏈表。
Doubly.prototype.append = function(data){
var newNode = new Node(data);
if(this.length == 0){
this.head = newNode;
}else{
newNode.prev = this.tail;
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
}
2、將鏈表轉(zhuǎn)化為字符串形式
1、toString():正向輸出元素的值
這個(gè)方法主要是獲取每一個(gè)元素，該方法默認(rèn)獲取鏈表的任何元素都必須從第一個(gè)節(jié)點(diǎn)開始，所以我們可以從頭結(jié)點(diǎn)開始，循環(huán)遍歷每一個(gè)節(jié)點(diǎn)，并且取出其中的element，拼接成字符串，并將字符串返回。具體方法為創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)current，讓這個(gè)臨時(shí)節(jié)點(diǎn)指向雙向鏈表的頭部，然后通過next指針依次向后遍歷，將每次遍歷得到的數(shù)據(jù)進(jìn)行拼接。
DoublyLinkedList.prototype.tostring = function(){
var current = this.head;
var str = '';
while(current){
str += current.data + ' ';
current = current.next;
}
return str;
}
2、forwardString():返回正向遍歷的節(jié)點(diǎn)字符串形式
該方法也是實(shí)現(xiàn)雙向鏈表的正向打印并輸出，所以我們這里可以直接調(diào)用上一個(gè)方法：
DoublyLinkedList.prototype.forwardString = function(){
return this.toString()
}
3、backwardString():返回反向遍歷的節(jié)點(diǎn)字符串形式
這個(gè)方法主要是從后往前遍歷獲取每一個(gè)元素并打印，所以我們可以從尾結(jié)點(diǎn)開始，循環(huán)遍歷每一個(gè)節(jié)點(diǎn)，并且取出其中的element，拼接成字符串，并將字符串返回。具體方法為創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)current，讓這個(gè)臨時(shí)節(jié)點(diǎn)指向雙向鏈表的尾部，然后通過prev指針依次向前遍歷，將每次遍歷得到的數(shù)據(jù)進(jìn)行拼接。
DoublyLinkedList.prototype.backwardString = function(){
var current = this.tail;
var str = '';
//依次向前遍歷，獲取每一個(gè)節(jié)點(diǎn)
while(current){
str += current.data +' ';
current = current.prev;
}
return str;
}
驗(yàn)證：
例如我們通過append()方法創(chuàng)建一個(gè)含有三個(gè)數(shù)據(jù)的雙向鏈表，然后分別將他們正向拼接和反向拼接：
var list = new DoublyLinkedList();
list.append("a");
list.append("b");
list.append("c");
list.append("d");
console.log('toString()方法：'+list.toString());
console.log('forwardString()方法：'+list.forwardString());
console.log('backwardString()方法：'+list.backwardString());
打印結(jié)果為：
驗(yàn)證成功。
3、insert(position,element):向列表的特定位置插入一個(gè)項(xiàng)
這個(gè)方法相對來說是比較復(fù)雜的，首先，先判斷要插入的位置是否越界，在不越界的情況下，在根據(jù)鏈表的情況判斷，如果鏈表為空，則插入節(jié)點(diǎn)為第一個(gè)元素，直接讓頭結(jié)點(diǎn)和尾節(jié)點(diǎn)的指針指向新創(chuàng)建的節(jié)點(diǎn)；如果鏈表不為空，則插入的位置有三種情況：插入到首位，插入到末尾和插入到中間部位。具體操作如下：
DoublyLinkedList.prototype.insert = function(position,data){
var newNode = new Node(data);
//越界判斷，如果不滿足，返回false
if(position<0 || position>this.length){
return false;
}else{
//再次判斷
//如果鏈表為空，直接插入
if(position==0){
this.head = newNode;
this.tail = newNode;
}else {
//如果鏈表不為空
//如果插入位置為末尾
if(position == this.length){
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}else if(position == 0){
//如果插入位置為首位
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}else{
//如果插入位置為中間
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
}
this.length += 1;
}
}
}
驗(yàn)證：如果在1位置插入xl,如下所示:
list.insert(1,'xl') console.log(list.toString());
運(yùn)行結(jié)果為：
驗(yàn)證成功。
4、get(position):獲取對應(yīng)位置的元素
這個(gè)方法首先要判斷位置是否越界，在不越界的情況下，定義一個(gè)臨時(shí)節(jié)點(diǎn)和索引，讓這個(gè)臨時(shí)節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，遍歷臨時(shí)節(jié)點(diǎn)，同時(shí)索引自加，如果遍歷道德節(jié)點(diǎn)的位置等于要獲取元素的位置，則臨時(shí)節(jié)點(diǎn)對應(yīng)位置的元素就是要獲得的元素。
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
return current.data;
}
}
驗(yàn)證：查詢position = 2的元素
console.log('list.get(2):'+list.get(2));
結(jié)果為：
驗(yàn)證成功。
但是，這種查找方式有一個(gè)弊端，即只能從前向后查找，在某些情況下效率就會(huì)很低，所以我們就可以兩頭查找，具體查找方式為：當(dāng)我們要查找的節(jié)點(diǎn)的位置小于或等于鏈表長度的一半，我們就可以從前向后查找，如果要查找的節(jié)點(diǎn)的位置大于長度的一半，我們就從后往前查找。實(shí)現(xiàn)代碼為：
DoublyLinkedList.prototype.get = function(position){
if(position<0 || position>=this.length){
return false;
}else{
var len = Math.floor(this.length/2);
if(position<=len){
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
}else{
var index = this.length-1;
var current = this.tail;
while(index-->position){
current = current.prev;
}
}
return current.data;
}
}
5、indexOf(element):返回元素在列表中的索引
創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)和索引，讓臨時(shí)節(jié)點(diǎn)指向頭結(jié)點(diǎn)，依次向后遍歷，同時(shí)讓索引跟著遞增，如果遍歷的臨時(shí)節(jié)點(diǎn)所得到的元素等于我們指定的元素，則此時(shí)的臨時(shí)節(jié)點(diǎn)的位置就是我們目標(biāo)位置，該位置的索引就是目標(biāo)值的索引。
DoublyLinkedList.prototype.indexOf = function(data){
var current = this.head;
var index = 0;
while(current){
if(current.data === data){
return index;
}
current = current.next;
index ++;
}
return -1;
}
驗(yàn)證成功。
6、 update(position，ele):修改某個(gè)位置的元素
首先判斷要修改的位置是否越界，在不越界的情況下，定義一個(gè)臨時(shí)節(jié)點(diǎn)和索引，讓臨時(shí)節(jié)點(diǎn)指向頭結(jié)點(diǎn)，索引位置為0，遍歷臨時(shí)節(jié)點(diǎn)并判斷臨時(shí)節(jié)點(diǎn)此時(shí)的索引和要修改元素的位置是否相等，如果相等的話，此時(shí)臨時(shí)節(jié)點(diǎn)的位置就是要修改元素的位置，可以直接給臨時(shí)節(jié)點(diǎn)的數(shù)據(jù)域更改元素。
DoublyLinkedList.prototype.update = function(position,newData){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = curent.next;
}
current.data = newData;
return true;
}
}
驗(yàn)證：將0位置的數(shù)據(jù)換成rc
list.update(0,'rc')
console.log("list.update(0,'rc')為:");
console.log(list.toString());
驗(yàn)證成功。
7、removeAt(position):從列表的指定位置移除一項(xiàng)
這個(gè)方法和insert()方法的思想相似，首先判斷是否越界，在不越界的情況下，如果鏈表只有一個(gè)節(jié)點(diǎn)，則直接移除該項(xiàng)，讓鏈表的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)均指向空。如果鏈表有多個(gè)節(jié)點(diǎn)的情況下，也分為三種情況，操作如下：
DoublyLinkedList.prototype.removeAt = function(position){
if(position<0 || position>=this.length){
return null;
}else{
var current = this.head;
if(this.length ===1){
//鏈表長度為1
this.head = null;
this.tail = null
}else{//鏈表長度不為1
if(position === 0){
//刪除首位
this.head.next.prev = null;
this.head = this.head.next;
}else if(position === this.length-1){
this.tail.prev.next = null;
this.tail = this.tail.prev;
}else{
var index = 0;
while(index++ <position){
current = current.next;
}
current.prev.next = current.next;
current.next.pre = current.prev;
}
}
this.length -=1;
return current.data;
}
}
驗(yàn)證：刪除位置3的數(shù)據(jù)：
list.removeAt(3)
console.log("list.removeAt(3)為:");
console.log(list.toString());
結(jié)果為：
驗(yàn)證成功
8、remove(element):從列表中移除一項(xiàng)
可以直接根據(jù)indexOf(element)方法獲取元素在鏈表中的位置，在根據(jù)removeAt(position)方法將其刪除。
DoublyLinkedList.prototype.remove = function(data){
var index = this.indexOf(data);
return this.removeAt(index);
}
驗(yàn)證：刪除數(shù)據(jù)為rc的節(jié)點(diǎn)：
list.remove('rc');
console.log("list.remove('rc')為:");
console.log(list.toString());
9、isEmpty():判斷鏈表是否為空
直接判斷鏈表中元素的個(gè)數(shù)是否為零，如果為零則為空，返回true，否則不為空，返回false.
DoublyLinkedList.prototype.isEmpty = function(){
return this.length ==0;
}
驗(yàn)證：
console.log("鏈表是否為空："+list.isEmpty());
10、size():返回鏈表包含的元素個(gè)數(shù)
鏈表長度就是元素個(gè)數(shù)。
DoublyLinkedList.prototype.size = function(){
return this.length;
}
驗(yàn)證：
console.log("鏈表的元素個(gè)數(shù)為："+list.size());
以上就是JavaScript實(shí)現(xiàn)雙向鏈表過程解析的詳細(xì)內(nèi)容，更多關(guān)于JavaScript 雙向鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
jQuery及JS實(shí)現(xiàn)循環(huán)中暫停的方法
這篇文章主要介紹了jQuery及JS實(shí)現(xiàn)循環(huán)中暫停的方法,以實(shí)例形式分析了循環(huán)中暫停的原理及實(shí)現(xiàn)技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-02-02
之前的彈出層做的挺好，但是代碼結(jié)構(gòu)有問題，這次用到了，重構(gòu)了一下，改為jQuery的插件形式，感覺還不錯(cuò)，有興趣的朋友可以參考下，希望可以幫助到你2013-04-04
整理關(guān)于Bootstrap導(dǎo)航的慕課筆記
這篇文章主要為大家整理了關(guān)于Bootstrap導(dǎo)航的慕課筆記，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-03-03
在IE下獲取object（ActiveX）的Param的代碼
在IE下，獲取Param的時(shí)候有個(gè)詭異現(xiàn)象（不知道算不算bug）。2009-09-09
IE8的JavaScript點(diǎn)擊事件(onclick)不兼容的解決方法
這篇文章主要介紹了IE8的JavaScript點(diǎn)擊事件(onclick)不兼容的解決方法,大家參考使用吧2013-11-11
js 動(dòng)態(tài)創(chuàng)建 html元素
最近在學(xué)習(xí)js 寫了個(gè)簡單的效果,菜鳥可以學(xué)習(xí)學(xué)習(xí),基本原理：使用隨即數(shù)設(shè)置top 和left的值，2009-07-07
下面小編就為大家?guī)硪黄獪\談JS如何實(shí)現(xiàn)真正的對象常量。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
uniapp組件傳值的方法(父傳子,子傳父,對象傳值)實(shí)戰(zhàn)案例
現(xiàn)在的前端開發(fā)中基本上都是組件化開發(fā)的,下面這篇文章主要給大家介紹了關(guān)于uniapp組件傳值(父傳子,子傳父,對象傳值)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
這篇文章主要介紹了js回溯法計(jì)算最佳旅行線路代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09
這篇文章主要為大家詳細(xì)介紹了用純JS實(shí)現(xiàn)二級菜單效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04