言

不管是在前端還是后端開發(fā)面試過程中，關(guān)于數(shù)據(jù)結(jié)構(gòu)部分的問題是必不可少的，比如像鏈表，棧，隊列，圖等等。今天這篇文章，我們站在前端開發(fā)人員的角度，看看如何使用Javascript來實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)。

今天這篇文章中的代碼已經(jīng)放到Github上了，感興趣的可以自取，Github地址為：

https://github.com/zhouxiongking/article-pages/blob/master/articles/LinkedList/LinkedList.js

Javascript

鏈表

鏈表和數(shù)組是數(shù)據(jù)結(jié)構(gòu)中用于存儲多個元素，比較常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組中的元素在內(nèi)存中占用連續(xù)的內(nèi)存空間，而在鏈表中各個元素不是占有連續(xù)的內(nèi)存空間，元素之間通過引用關(guān)系連接。

通過下面這張圖可以很容易看清鏈表結(jié)構(gòu)。

鏈表結(jié)構(gòu)

相比于數(shù)組，鏈表在添加或移除元素時不會移動元素，只需要改變引用指向即可。但是如果想要訪問鏈表中的某個元素時，必須從表頭開始尋找，這是在使用上比數(shù)組劣勢的地方。

下面我們看看如何通過代碼來實現(xiàn)一個鏈表結(jié)構(gòu)，由于我們會采用類的結(jié)構(gòu)來組織代碼，因此采用ES6的語法來寫。

• 鏈表節(jié)點

首先我們需要如上圖所示的鏈表節(jié)點。

鏈表節(jié)點

• 追加元素

追加元素是在鏈表的末尾添加元素，動態(tài)的修改next引用的指向并修改鏈表的長度。

追加元素

• 任意位置插入元素

在任意位置插入元素時，我們需要建立一個臨時索引，從表頭開始往后迭代，直到臨時變量值等于插入位置，即改變插入點的next引用指向。

任意位置插入元素

• 移除指定位置元素

在移除指定位置元素時，首先需要檢查值是否越界，同樣需要建立一個臨時索引，從表頭向后迭代時，動態(tài)修改索引值，直到索引值與指定位置值相等，最后修改元素的next引用指向。

移除指定位置元素

• 尋找元素索引

在尋找元素索引時，建立一個臨時變量，從表頭開始向后遍歷，在遍歷過程中動態(tài)修改臨時變量值，直到找到需要的元素，返回這個臨時變量即可。

尋找元素索引

• 刪除指定元素

在刪除指定元素時，可以借助上述的尋找元素索引方法，先找到索引再通過移除指定位置元素的方法來刪除。

刪除指定元素

• 判空和鏈表長度

判斷鏈表是否為空以及獲取鏈表的長度，都只需要通過length屬性即可。

判空和鏈表長度

• 自定義輸出

打印鏈表時，我們可以自定義toString()方法，以我們想要的方式進(jìn)行輸出。

自定義輸出

測試

用Javascript編寫完鏈表結(jié)構(gòu)后，我們通過以下的代碼進(jìn)行測試。

測試代碼

我們可以得到以下結(jié)果。

測試結(jié)果

這也證明了我們實現(xiàn)鏈表結(jié)構(gòu)的正確性。

結(jié)束語

今天這篇文章主要利用Javascript實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的鏈表，大家學(xué)會了嗎？

言

不管是在前端還是后端開發(fā)面試過程中，關(guān)于數(shù)據(jù)結(jié)構(gòu)部分的問題是必不可少的，比如像鏈表，棧，隊列，圖等等。今天這篇文章，我們站在前端開發(fā)人員的角度，看看如何使用Javascript來實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)。

今天這篇文章中的代碼已經(jīng)放到Github上了，感興趣的可以自取，Github地址為：

https://github.com/zhouxiongking/article-pages/blob/master/articles/LinkedList/LinkedList.js

Javascript

鏈表

鏈表和數(shù)組是數(shù)據(jù)結(jié)構(gòu)中用于存儲多個元素，比較常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組中的元素在內(nèi)存中占用連續(xù)的內(nèi)存空間，而在鏈表中各個元素不是占有連續(xù)的內(nèi)存空間，元素之間通過引用關(guān)系連接。

通過下面這張圖可以很容易看清鏈表結(jié)構(gòu)。

鏈表結(jié)構(gòu)

相比于數(shù)組，鏈表在添加或移除元素時不會移動元素，只需要改變引用指向即可。但是如果想要訪問鏈表中的某個元素時，必須從表頭開始尋找，這是在使用上比數(shù)組劣勢的地方。

下面我們看看如何通過代碼來實現(xiàn)一個鏈表結(jié)構(gòu)，由于我們會采用類的結(jié)構(gòu)來組織代碼，因此采用ES6的語法來寫。

• 鏈表節(jié)點

首先我們需要如上圖所示的鏈表節(jié)點。

鏈表節(jié)點

• 追加元素

追加元素是在鏈表的末尾添加元素，動態(tài)的修改next引用的指向并修改鏈表的長度。

追加元素

• 任意位置插入元素

在任意位置插入元素時，我們需要建立一個臨時索引，從表頭開始往后迭代，直到臨時變量值等于插入位置，即改變插入點的next引用指向。

任意位置插入元素

• 移除指定位置元素

在移除指定位置元素時，首先需要檢查值是否越界，同樣需要建立一個臨時索引，從表頭向后迭代時，動態(tài)修改索引值，直到索引值與指定位置值相等，最后修改元素的next引用指向。

移除指定位置元素

• 尋找元素索引

在尋找元素索引時，建立一個臨時變量，從表頭開始向后遍歷，在遍歷過程中動態(tài)修改臨時變量值，直到找到需要的元素，返回這個臨時變量即可。

尋找元素索引

• 刪除指定元素

在刪除指定元素時，可以借助上述的尋找元素索引方法，先找到索引再通過移除指定位置元素的方法來刪除。

刪除指定元素

• 判空和鏈表長度

判斷鏈表是否為空以及獲取鏈表的長度，都只需要通過length屬性即可。

判空和鏈表長度

• 自定義輸出

打印鏈表時，我們可以自定義toString()方法，以我們想要的方式進(jìn)行輸出。

自定義輸出

測試

用Javascript編寫完鏈表結(jié)構(gòu)后，我們通過以下的代碼進(jìn)行測試。

測試代碼

我們可以得到以下結(jié)果。

測試結(jié)果

這也證明了我們實現(xiàn)鏈表結(jié)構(gòu)的正確性。

結(jié)束語

今天這篇文章主要利用Javascript實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的鏈表，大家學(xué)會了嗎？

篇文章給大家?guī)淼膬?nèi)容是關(guān)于JavaScript中鏈表的詳細(xì)介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

鏈表和數(shù)組

大家都用過js中的數(shù)組，數(shù)組其實是一種線性表的順序存儲結(jié)構(gòu)，它的特點是用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素。而它的缺點也正是其特點而造成，比如對數(shù)組做刪除或者插入的時候，可能需要移動大量的元素。

這里大致模擬一下數(shù)組的插入操作：

insert(arr, index, data){

for(let i=index + 1; i < arr.length; i++){

arr[i]=arr[i - 1];

}

arr[index]=data;

}

從上面的代碼可以看出數(shù)組的插入以及刪除都有可能會是一個O(n)的操作。從而就引出了鏈表這種數(shù)據(jù)結(jié)構(gòu)，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的缺點，當(dāng)然它也失去了數(shù)組在一塊連續(xù)空間內(nèi)隨機(jī)存取的優(yōu)點。

單向鏈表

單向鏈表的特點：

• 用一組任意的內(nèi)存空間去存儲數(shù)據(jù)元素（這里的內(nèi)存空間可以是連續(xù)的，也可以是不連續(xù)的）
• 每個節(jié)點(node)都由數(shù)據(jù)本身和一個指向后續(xù)節(jié)點的指針組成
• 整個鏈表的存取必須從頭指針開始，頭指針指向第一個節(jié)點
• 最后一個節(jié)點的指針指向空（NULL）

鏈表中的幾個主要操作

• 創(chuàng)建節(jié)點
• 插入節(jié)點
• 搜索/遍歷節(jié)點
• 刪除節(jié)點
• 合并

初始化節(jié)點

• 指針指向空
• 存儲數(shù)據(jù)

class Node {

constructor(key) {

this.next=null;

this.key=key;

}

}

初始化單向鏈表

• 每個鏈表都有一個頭指針，指向第一個節(jié)點，沒節(jié)點則指向NULL

class List {

constructor() {

this.head=null;

}

}

創(chuàng)建節(jié)點

static createNode(key) {

return new createNode(key);

}

這里說明一下，這一塊我是向外暴露了一個靜態(tài)方法來創(chuàng)建節(jié)點，而并非直接把它封裝進(jìn)插入操作里去，因為我感覺這樣的邏輯會更加正確一些。 從創(chuàng)建一個鏈表 -> 創(chuàng)建一個節(jié)點 -> 將節(jié)點插入進(jìn)鏈表中。可能你會遇到一些文章介紹的方式是直接將一個數(shù)據(jù)作為參數(shù)去調(diào)用insert操作，在insert內(nèi)部做了一個創(chuàng)建節(jié)點。

插入節(jié)點（插入到頭節(jié)點之后）

插入操作只需要去調(diào)整節(jié)點的指針即可,兩種情況：

• head沒有指向任何節(jié)點，說明當(dāng)前插入的節(jié)點是第一個
• head指向新節(jié)點
• 新節(jié)點的指針指向NULL
• head有指向的節(jié)點
• head指向新的節(jié)點
• 新節(jié)點的指針指向原本head所指向的節(jié)點

insert(node) {

// 如果head有指向的節(jié)點

if(this.head){

node.next=this.head;

}else {

node.next=null;

}

this.head=node;

}

搜索節(jié)點

• 從head開始查找
• 找到節(jié)點中的key等于想要查找的key的時候，返回該節(jié)點

find(key) {

let node=this.head;

while(node !==null && node.key !==key){

node=node.next;

}

return node;

}

刪除節(jié)點

這里分三種情況：

• 所要刪除的節(jié)點剛好是第一個，也就是head指向的節(jié)點
• 將head指向所要刪除節(jié)點的下一個節(jié)點(node.next)
• 要刪除的節(jié)點為最后一個節(jié)點
• 尋找到所要刪除節(jié)點的上一個節(jié)點(prevNode)
• 將prevNode中的指針指向NULL
• 在列表中間刪除某個節(jié)點
• 尋找到所要刪除節(jié)點的上一個節(jié)點(prevNode)
• 將prevNode中的指針指向當(dāng)前要刪除的這個節(jié)點的下一個節(jié)點

delete(node) {

// 第一種情況

if(node===this.head){

this.head=node.next;

return;

}

// 查找所要刪除節(jié)點的上一個節(jié)點

let prevNode=this.head;

while (prevNode.next !==node) {

prevNode=prevNode.next;

}

// 第二種情況

if(node.next===null) {

prevNode.next=null;

}

// 第三種情況

if(node.next) {

prevNode.next=node.next;

}

}

單向鏈表整體的代碼

class ListNode {

constructor(key) {

this.next=null;

this.key=key;

}

}

class List {

constructor() {

this.head=null;

this.length=0;

}

static createNode(key) {

return new ListNode(key);

}

// 往頭部插入數(shù)據(jù)

insert(node) {

// 如果head后面有指向的節(jié)點

if (this.head) {

node.next=this.head;

} else {

node.next=null;

}

this.head=node;

this.length++;

}

find(key) {

let node=this.head;

while (node !==null && node.key !==key) {

node=node.next;

}

return node;

}

delete(node) {

if (this.length===0) {

throw 'node is undefined';

}

if (node===this.head) {

this.head=node.next;

this.length--;

return;

}

let prevNode=this.head;

while (prevNode.next !==node) {

prevNode=prevNode.next;

}

if (node.next===null) {

prevNode.next=null;

}

if (node.next) {

prevNode.next=node.next;

}

this.length--;

}

}

雙向鏈表

如果你把上面介紹的單向列表都看明白了，那么這里介紹的雙向列表其實差不多。

從上面的圖可以很清楚的看到雙向鏈表和單向鏈表的區(qū)別。雙向鏈表多了一個指向上一個節(jié)點的指針。

初始化節(jié)點

• 指向前一個節(jié)點的指針
• 指向后一個節(jié)點的指針
• 節(jié)點數(shù)據(jù)

class ListNode {

this.prev=null;

this.next=null;

this.key=key;

}

初始化雙向鏈表

• 頭指針指向NULL

class List {

constructor(){

this.head=null;

}

}

創(chuàng)建節(jié)點

static createNode(key){

return new ListNode(key);

}

插入節(jié)點（（插入到頭節(jié)點之后）

• 看上圖中head后面的第一個節(jié)點可以知道，該節(jié)點的prev指向NULL
• 節(jié)點的next指針指向后一個節(jié)點, 也就是當(dāng)前頭指針?biāo)赶虻哪莻€節(jié)點
• 如果head后有節(jié)點，那么原本head后的節(jié)點的prev指向新插入的這個節(jié)點(因為是雙向的嘛)
• 最后將head指向新的節(jié)點

insert(node) {

node.prev=null;

node.next=this.head;

if(this.head){

this.head.prev=node;

}

this.head=node;

}

搜索節(jié)點

這里和單向節(jié)點一樣，就直接貼代碼了

search(key) {

let node=this.head;

while (node !==null && node.key !==key) {

node=node.next;

}

return node;

}

刪除節(jié)點

和之前單向鏈表一樣，分三種情況去看：

• 刪除的是第一個節(jié)點
• head指向所要刪除節(jié)點的下一個節(jié)點
• 下一個節(jié)點的prev指針指向所要刪除節(jié)點的上一個節(jié)點
• 刪除的是中間的某個節(jié)點
• 所要刪除的前一個節(jié)點的next指向所要刪除的下一個節(jié)點
• 所要刪除的下一個節(jié)點的prev指向所要刪除的前一個節(jié)點
• 刪除的是最后一個節(jié)點
• 要刪除的節(jié)點的上一個節(jié)點的next指向null（也就是指向刪除節(jié)點的next所指的地址）

delete(node) {

const {prev,next}=node;

delete node.prev;

delete node.next;

if(node===this.head){

this.head=next;

}

if(next){

next.prev=prev;

}

if(prev){

prev.next=next;

}

}

雙向鏈表整體代碼

class ListNode {

constructor(key) {

// 指向前一個節(jié)點

this.prev=null;

// 指向后一個節(jié)點

this.next=null;

// 節(jié)點的數(shù)據(jù)(或者用于查找的鍵)

this.key=key;

}

}

/**

* 雙向鏈表

*/

class List {

constructor() {

this.head=null;

}

static createNode(key) {

return new ListNode(key);

}

insert(node) {

node.prev=null;

node.next=this.head;

if (this.head) {

this.head.prev=node;

}

this.head=node;

}

search(key) {

let node=this.head;

while (node !==null && node.key !==key) {

node=node.next;

}

return node;

}

delete(node) {

const { prev, next }=node;

delete node.prev;

delete node.next;

if (node===this.head) {

this.head=next;

}

if (prev) {

prev.next=next;

}

if (next) {

next.prev=prev;

}

}

}

總結(jié)

這里做一個小總結(jié)吧，可能有一部分人讀到這里還不是特別的明白，我的建議是先好好看懂上面的單向鏈表。 其實只要你明白了鏈表的基礎(chǔ)概念，就是有一個head，然后在有好多的節(jié)點(Node)，然后用一個指針把他們串起來就好了，至于里面的插入操作也好，刪除也好，其實都是在調(diào)整節(jié)點中指針的指向。

以上就是JavaScript中鏈表的詳細(xì)介紹的詳細(xì)內(nèi)容，更多請關(guān)注其它相關(guān)文章！

更多技巧請《轉(zhuǎn)發(fā) + 關(guān)注》哦！