上海高端網(wǎng)站建設(shè)制作seo軟件安卓版
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