JavaScript中怎么實(shí)現(xiàn)鏈表？

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的的鏈表和樹時(shí)，會(huì)遇到節(jié)點(diǎn)（node）這個(gè)詞，節(jié)點(diǎn)是處理數(shù)據(jù)結(jié)構(gòu)的鏈表和樹的基礎(chǔ)。節(jié)點(diǎn)是一種數(shù)據(jù)元素，包括兩個(gè)部分：一個(gè)是實(shí)際需要用到的數(shù)據(jù)；另一個(gè)存儲(chǔ)下一個(gè)節(jié)點(diǎn)位置。

鏈表是一系列節(jié)點(diǎn)串聯(lián)形成的數(shù)據(jù)結(jié)構(gòu)，鏈表存儲(chǔ)有序的元素集合，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本身的部分和一個(gè)指向下一個(gè)元素的鏈接部分組成。因此鏈表增刪非首尾元素時(shí)不需要移動(dòng)元素，只需要更改鏈接部分的值即可。

在此僅看單鏈表，單鏈表每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)如下：

單鏈表，在這種類型的數(shù)據(jù)結(jié)構(gòu)中，任何兩個(gè)數(shù)據(jù)元素之間只有一個(gè)鏈接，參見下圖：

鏈表的操作包括了創(chuàng)建、刪除、插入、輸出等。

創(chuàng)建就是空間的分配，將頭、尾指針及鏈表結(jié)點(diǎn)個(gè)數(shù)等初始化。刪除和插入根據(jù)被操作元素的位置可以細(xì)分為頭刪除（插入），尾刪除（插入），中間刪除（插入）。

插入操作

頭插入實(shí)際上是增加一個(gè)新節(jié)點(diǎn)，然后把新增加的結(jié)點(diǎn)指針指向原來頭指針指向的元素，再把頭指針指向新增的節(jié)點(diǎn)。

尾插入也是增加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)指針置為null，然后把原尾結(jié)點(diǎn)指針指向新增加的節(jié)點(diǎn)，最后把尾指針指向新增加的節(jié)點(diǎn)即可。

中間插入稍復(fù)雜，首先增加一個(gè)節(jié)點(diǎn)，然后新增節(jié)點(diǎn)的指針指向插入位置的后一個(gè)節(jié)點(diǎn)，把插入位置的前一個(gè)節(jié)點(diǎn)指針指向新插入節(jié)點(diǎn)即可。

刪除操作

刪除頭元素時(shí)，先將頭指針指向下一個(gè)節(jié)點(diǎn)，然后把原頭結(jié)點(diǎn)的指針置空即可。

刪除尾元素時(shí)，首先找到鏈表倒數(shù)第2個(gè)元素，然后把尾指針指向這個(gè)元素，接著把原倒數(shù)第2個(gè)元素的指針置空。

刪除中間元素相對(duì)復(fù)雜一些，首先將要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指針指向要?jiǎng)h除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后把要?jiǎng)h除節(jié)點(diǎn)的指針置空。

上面提到是單鏈表最基本的操作，除此之外還有其它操作不多說了。下面給出代碼示例。

在 JavaScript中，我們?cè)趺磳?shí)現(xiàn)鏈表呢？

現(xiàn)在以單鏈表的建立和遍歷為例介紹。項(xiàng)目結(jié)構(gòu)如下

SingleLinkedList.js文件內(nèi)容如下：

//定義單向鏈表的節(jié)點(diǎn)類
class Node{constructor(data){this.data = data    //節(jié)點(diǎn)的數(shù)據(jù)部分this.next = null    //節(jié)點(diǎn)的鏈接部分(指針部分)   }
}
//定義單向鏈表類
class SingleLinked{  constructor(){this.size = 0  //單鏈表的長度，用來記錄鏈表中的節(jié)點(diǎn)個(gè)數(shù)，為一個(gè)空鏈表this.head = new Node('head')  //是鏈表的頭指針：記錄鏈表的起始地址this.currentNode = ''  //用來記錄當(dāng)前節(jié)點(diǎn)}//獲取鏈表的長度getLength(){return this.size}//判斷鏈表是否為空isEmpty(){return this.size === 0   //如果this.size為0則說明鏈表為空，即返回true}//遍歷鏈表:不重復(fù)的訪問鏈表中的每一個(gè)節(jié)點(diǎn)displayList(){var list = ''var currentNode = this.head  //指向鏈表的頭指針while(currentNode){  //若當(dāng)前節(jié)點(diǎn)不為空，則執(zhí)行循環(huán)list+=currentNode.data    //連接節(jié)點(diǎn)的數(shù)據(jù)域currentNode = currentNode.next  //讓當(dāng)前指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)if(currentNode){   //如果currentNode不為空則加上連接符list += '->'  //鏈表節(jié)點(diǎn)的連接符}}console.log(list)}//獲取鏈表的最后一個(gè)節(jié)點(diǎn)findLast(){var currNode = this.headwhile(currNode.next){   //若當(dāng)前節(jié)點(diǎn)的next域?yàn)榭?#xff0c;則他是鏈表的最后一個(gè)節(jié)點(diǎn)，跳出循環(huán)currNode = currNode.next  //若當(dāng)前節(jié)點(diǎn)的next域不為空則讓指針指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)}return currNode}//采用尾插法給鏈表插入元素appendNode(element){var currNode = this.findLast()  //找到鏈表的最后一個(gè)節(jié)點(diǎn)var newNode = new Node(element)  //創(chuàng)建一個(gè)新的節(jié)點(diǎn)currNode.next = newNodenewNode.next = nullthis.size++   //鏈表的長度加1}//刪除鏈表中的一個(gè)節(jié)點(diǎn)delete(element){//this.displayList()var currentNode = this.headtry{while((currentNode.next!=null)&&(currentNode.next.element!=element)){  //判斷，如果節(jié)點(diǎn)靠后則節(jié)點(diǎn)的next的next為空，不為空時(shí)進(jìn)行刪除if(currentNode.next.data === element){currentNode.next = currentNode.next.next    this.size--}else{currentNode = currentNode.next}}}catch(e){   //測試函數(shù)，判斷函數(shù)的運(yùn)行錯(cuò)誤console.log(e)}}
}

測試代碼內(nèi)容如下，我這里保存文件名為 單鏈表測試.html，將此文件和SingleLinkedList.js放到同一目錄中：

<script src="./SingleLinkedList.js"></script><script>  //不能寫在有js代碼的JavaScript中var slist = new SingleLinked()console.log(slist.isEmpty())  //打印鏈表是否為空，若為空則輸出trueslist.appendNode(1001)   //創(chuàng)建鏈表節(jié)點(diǎn)slist.appendNode(1002)   //創(chuàng)建鏈表節(jié)點(diǎn)//創(chuàng)建鏈表更多節(jié)點(diǎn)var arr = [1020,1234,1006,788,5512]for(var i=0;i<arr.length;i++){slist.appendNode(arr[i])}//遍歷輸出鏈表slist.displayList()//刪除鏈表中的1006元素slist.delete(1006)slist.displayList()
</script>

用瀏覽器打開 單鏈表測試.html，按下F12鍵單開控制臺(tái)，查看結(jié)果：

更多情況可見https://segmentfault.com/a/1190000017970029