數據結構淺析：鏈表

你有修建過戈德堡機械嗎？如果沒有，也許應該修建過精心構建的多米諾骨牌線？

好的，也許你的童年應該不像我一樣書獃子。就這樣吧，對於玩過上述兩者中任意一樣的人，你已經掌握了今天數據結構的本質：鏈表！

鏈表是怎麼工作的

鏈表的最簡單實現形式-單鏈表-是一系列的節點，每一個單獨的節點都包含一個值和一個指向鏈表中下一個節點的指針。

添加（Add）通過在表的尾部添加一個項目增加列表的大小。

移除（Remove）通常移除鏈表中指定位置的元素。

搜索（Contains）將在列表中搜索一個指定的值。

使用例子：

哈希表中為了防止出現衝突，將values存儲在一個列表中。

重拍極速前進（The Amazing Race）

為了讓這篇文章保持輕鬆友好一些，我們一起來創建一個CBS可用於計劃其下一季「極速前進」真人秀拍攝的工具。

在閱讀本文時，我希望你能夠一直問自己：「鏈表和數組有什麼區別？它們有什麼相似之處？」

我們開始吧。

首先，你需要創建一個鏈表：

為了跟蹤比賽的起點和終點，需要創建head和tail屬性。

然後，為了保證賽程不要太長或者太短，需要創建length屬性和size方法。這樣你就總是可以精確的掌握賽程的長度。

現在你有了一種存儲數據的方法，你應該創建一個往列表添加數據的方法。問題是，你要添加什麼數據呢？

記住，鏈表是一系列的節點，每一個節點都有一個值和指向列表中下一個節點的指針。了解了這一點，你會意識到節點就是一個存儲有value和next兩個屬性的對象。

由於每一次往列表添加數據都需要創建一個新的節點，你決定創建一個構造函數，這樣每次往列表添加數據時創建節點會更簡單一些。

有了構造函數，就可以創建add方法。

現在你已經添加了這個方法，你可以往「AmazingRace」列表中添加一堆比賽地點。看起來像這樣。注意為了更容易理解我添加了一些額外的空格。

好啦，現在已經創建了列表以及添加內容的方法，你意識到往列表中添加地點還需要一些方法。

你決定將這個鏈表共享給合作者，Kent，要求他往裡面添加更多的比賽地點。唯一的問題是，當你將列表給他時，沒有告訴他你已經添加了哪些地點。不幸的是你也忘記了。

當然他可以通過運行console.log(AmazingRace)然後逐一檢查其輸出。但是Kent是一個懶人，他需要一種方式來確認某些值是否已經存在列表中，從而避免重複添加。考慮到這一點，你創建了contains方法來檢查是否包含某些值。

很棒，現在Kent為了避免重複，他可以在添加之前檢查一下是否已經存在。

另一方面，你可能會想為什麼不在添加之前進行檢查從而避免重複呢？當你在實現一個鏈表—或者任意的數據結構時—理論上你可以添加任何額外你想要的功能。

你甚至可以改變已有數據結構中原來的方法。在REPL中試一下以下代碼：

我們沒有做這些事情的原因是因為約定的標準。基本上，開發者對特定的方法應該如何工作是有預期的。

約定的標準：http://www.ecma-international.org/ecma-262/7.0/index.html#sec-array.prototype.push

儘管我們的鏈表不是JavaScript的原生庫，我們在實現它時擁有更多的自由，但是這些數據結構如何運作我們仍有基本的期望。鏈表本身並不保證存儲的值唯一。但是它們確實可以提供contains這樣的方法允許我們進行預檢，從而維護我們列表中的值不重複。

Kent將他修改後的列表再發給你，但是其中一些可能有問題。比如北極可能不是「極速前進」最好的終點。

所以你決定創建一個可以移除某些節點的方法。一定要記住的是，一旦你刪除了某一個節點，你就打斷了列表，你需要將被刪除節點的前後兩個節點重新連接起來。

remove方法的代碼比較長。本質上它按照如下步驟運行：

1、檢查待刪除的值是否存在

2、遍歷列表，並且需要跟蹤當前節點和上一個節點

3、然後，如果當前節點就是要刪除的點—>

4A、當前節點是鏈表的頭

將鏈表的頭重置為列表中的下一個節點

更新鏈表長度

跳出循環

4B、當前節點是鏈表的尾

將鏈表的尾設置為鏈表中的上一個節點

按照下圖的方式重新連接節點

4C、如果不是要刪除的節點—>繼續迭代

將下一個節點設置為當前節點

將當前節點設置為上一個節點

最後要說明的一件事：你可能已經注意到你並沒有真正的刪除那個節點。你只是移除了對它的引用。對，這樣就可以了，因為一旦對一個對象的所有引用都被移除以後，垃圾回收器會幫助我們將它從內存中移除的。更多關於垃圾回收的信息參考這裡。

https://docstore.mik.ua/orelly/webprog/jscript/ch11_03.htm

有了你剛才實現的remove方法，你只需下面這一行就可以保證參賽者不會凍死、或者打擾到正在準備新年慶典的聖誕老人。

好了，你已經完成了一個單鏈表的簡單實現。你可通過添加元素來擴充列表，也可以通過移除元素來壓縮列表。

如果你想在鏈表的首部、尾部或者任意節點後插入元素。你需要自己實現這些方法。這些方法的名稱和參數應該類似這樣：

時間複雜度分析

再來看一下完整的代碼

Add的複雜度是O(1)：因為有tail屬性跟蹤隊列的尾部，所以你不必遍歷整個列表。

Remove的複雜度是O(n)：最壞的情況下，你需要遍歷完整個列表才能找到你需要移除的節點。儘管真正的移除節點的操作是O(1)（因為你只需要重置一下指針就可以）。

Contains的複雜度是O(n)：為了確認列表中是否包含指定的值，你必須遍歷整個列表。

addHead的複雜度是O(1)：和我們的add方法相似，我們總是知道列表的頭部，所以不需要遍歷。

insertAfter的複雜度是O(n)：和上面討論的Remove方法一樣，你需要遍歷整個列表找到你需要插入的位置。同樣的，實際的插入操作複雜度為O(1)。

鏈表VS數組

為什麼要使用鏈表而不是數組？技術上數組可以運行所有鏈表操作，如添加、插入、刪除。此外，JavaScript中數組已經具備這些方法。

最大的差別來自插入和刪除。因為數組是基於索引，當你在數組的中間插入或者刪除元素時，你需要將其後面所有的元素重置到新的索引位置。

想像一下，在一個有100,000個元素的頭部或者中間插入一個元素！像這樣的插入和刪除操作是非常耗費資源的。因為這一點，鏈表通常用於常常被移動的大型數據集。

另一方面，數組在查找方面非常出色，因為它是基於索引的。如果你知道元素的位置，你可以通過array[position]在O(1)時間內查找到該元素。

鏈表通常需要順序遍歷列表。基於這一原因，數組常常用於小一些的數據集或者不常移動的數據集。

小節

鏈表

1、有tail和head屬性用於跟蹤鏈表的兩端

2、有add，addHead，insertAfter和remove方法用於管理列表內容

3、有length屬性用於跟蹤列表長度

每日推薦

如您有任何問題，請聯繫優才小編：

15201480058

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！