JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之鏈表_基礎(chǔ)知識(shí)

鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，也屬于線性表，但不會(huì)按線性的順序來(lái)儲(chǔ)存數(shù)據(jù)。而是在每一個(gè)節(jié)點(diǎn)中，儲(chǔ)存了下一個(gè)節(jié)點(diǎn)的指針。可以看圖理解。(有C語(yǔ)言基礎(chǔ)的可能比較好理解)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)(C語(yǔ)言的數(shù)組需要預(yù)先定義長(zhǎng)度)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
接下來(lái)就是介紹兩種常見(jiàn)的鏈表: 單向鏈表，雙向鏈表在JavaScript中的實(shí)現(xiàn)。

單向鏈表

鏈表中最簡(jiǎn)單的形式就是單向鏈表，鏈表中的節(jié)點(diǎn)都包含兩個(gè)部分，第一部分儲(chǔ)存著自身信息，第二部分則儲(chǔ)存有指向下一節(jié)點(diǎn)的指針。最后一個(gè)節(jié)點(diǎn)則指向NULL:

JavaScipt中單向鏈表的實(shí)現(xiàn)

首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

不難看出，單向鏈表構(gòu)造函數(shù)比棧與隊(duì)列要復(fù)雜許多。
單向鏈表需要有如下的方法:

1. append(element): 添加元素到鏈表尾部
2. insert(position,element): 向單向鏈表中某個(gè)位置插入元素
3. indexOf(element): 尋找某個(gè)元素在單向鏈表中的位置
4. remove(element): 移除給定的元素
5. removeAt(position): 移除單向鏈表中某個(gè)位置的元素
6. getHead(): 獲取單向鏈表的頭部
7. isAmpty(): 檢查單向鏈表是否為空，為空則返回true
8. toString(): 將鏈表所有內(nèi)容以字符串輸出
9. size(): 返回單向鏈表長(zhǎng)度
   

append方法:

說(shuō)明: 向單向鏈表尾部添加元素。
實(shí)現(xiàn):

insert方法:

說(shuō)明: 向單向鏈表中某個(gè)位置插入元素。
實(shí)現(xiàn):

indexOf方法:

說(shuō)明：尋找某個(gè)元素在單向鏈表中的位置。
實(shí)現(xiàn):

remove方法:

說(shuō)明: 移除給定的元素。
實(shí)現(xiàn):

removeAt方法:

說(shuō)明:移除單向鏈表中某個(gè)位置的元素。
實(shí)現(xiàn):

getHead方法:

說(shuō)明:獲取單向鏈表的頭部。
實(shí)現(xiàn):

isAmpty、toString、size方法

實(shí)現(xiàn):

雙向鏈表

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個(gè)節(jié)點(diǎn)的鏈接。但在雙向鏈表中，還有指向上一個(gè)節(jié)點(diǎn)的鏈接，是雙向的。

JavaScipt中雙向鏈表的實(shí)現(xiàn)

首先，依然是構(gòu)造函數(shù):

雙向鏈表需要有如下的方法:

1. append(element): 添加元素到雙向鏈表尾部
2. insert(position,element): 向雙向鏈表中某個(gè)位置插入元素
3. removeAt(position): 移除雙向鏈表中某個(gè)位置的元素
4. showHead(): 獲取雙向鏈表的頭部
5. showLength(): 獲取雙向鏈表長(zhǎng)度
6. showTail(): 獲取雙向鏈表尾部
   

append方法:

說(shuō)明: 添加元素到雙向鏈表尾部
實(shí)現(xiàn):

insert方法:

說(shuō)明: 向雙向鏈表中某個(gè)位置插入元素。
實(shí)現(xiàn):

removeAt方法:

說(shuō)明:移除雙向鏈表中某個(gè)位置的元素。
實(shí)現(xiàn):

showHead、showLength、showTail方法

實(shí)現(xiàn):

感想

鏈表這一節(jié)，基本全部都是先按需求寫(xiě)代碼，寫(xiě)完后再和書(shū)上對(duì)比。發(fā)現(xiàn)簡(jiǎn)直被瞬間秒成渣。自己寫(xiě)的很多暗坑，邏輯也很混亂。看來(lái)還是太年輕了。

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com