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