JavaScript中數據結構與算法(三)：鏈表_javascript技巧

線性表的順序存儲結構，最大的缺點就是改變其中一個元素的排列時都會引起整個合集的變化，其原因就是在內存中的存儲本來就是連貫沒有間隙的，刪除一個自然就要補上。針對這種結構的優化之后就出現了鏈式存儲結構，換個思路，我們完全不關心數據的排列，我們只需要在每一個元素的內部把下一個的數據的位置給記錄就可以了，所以用鏈接方式存儲的線性表簡稱為鏈表，在鏈式結構中，數據=（信息+地址）

鏈式結構中，我們把地址也可以稱為“鏈”，一個數據單元就是一個節點，那么可以說鏈表就是一組節點組成的合集。每一個節點都有一個數據塊引用指向它的下一個節點

數組元素是靠位置關系做邏輯引用，鏈表則是靠每一個數據元保存引用指針關系進行引用

這種結構上的優勢就非常明顯的，插入一個數據完全不需要關心其排列情況，只要把“鏈”的指向銜接上

這樣做鏈表的思路就不會局限在數組上了，我們可以用對象了，只要對象之間存在引用關系即可

鏈表一般有，單鏈表、靜態鏈表、循環鏈表、雙向鏈表

單鏈表：就是很單一的向下傳遞，每一個節點只記錄下一個節點的信息，就跟無間道中的梁朝偉一樣做臥底都是通過中間人上線與下線聯系，一旦中間人斷了，那么就無法證明自己的身份了，所以片尾有一句話："我是好人，誰知道呢？”

靜態鏈表：就是用數組描述的鏈表。也就是數組中每一個下表都是一個“節”包含了數據與指向

循環鏈表：由于單鏈表的只會往后方傳遞，所以到達尾部的時候，要回溯到首部會非常麻煩，所以把尾部節的鏈與頭連接起來形成循環

雙向鏈表：針對單鏈表的優化，讓每一個節都能知道前后是誰，所以除了后指針域還會存在一個前指針域，這樣提高了查找的效率，不過帶來了一些在設計上的復雜度，總體來說就是空間換時間了

綜合下，其實鏈表就是線性表中針對順序存儲結構的一種優化手段，但是在javascript語言中由于數組的特殊性（自動更新引用位置），所以我們可以采用對象的方式做鏈表存儲的結構

單鏈表

我們實現一個最簡單的鏈表關系

通過node對象的next去直引用下一個node對象，初步是實現了通過鏈表的引用，這種鏈式思路jQuery的異步deferred中的then方法，還有日本的cho45的jsderferre中都有用到。這個實現上還有一個最關鍵的問題，我們怎么動態插入數據到執行的節之后？

所以我們必須 要設計一個遍歷的方法，用來搜索這個node鏈上的數據，然后找出這個對應的數據把新的節插入到當前的鏈中，并改寫位置記錄

這就是一個查找當前節的一個方法，通過傳遞原始的頭部headNode節去一直往下查找next，直到找到對應的節信息

這里是用curry方法實現的

那么插入節的的時候，針對鏈表地址的換算關系這是這樣

a-b-c-d的鏈表中，如果要在c(c.next->d)后面插入一個f

a-b-c-f-d ,那么c,next->f , f.next-d

通過insert方法增加節

首先分離出createNode節的構建，在初始化的時候先創建一個頭部節對象用來做節開頭的初始化對象

在insert增加節方法中，通過對headNode鏈的一個查找，找到對應的節，把新的節給加后之后，最后就是修改一下鏈的關系

如何從鏈表中刪除一個節點？

由于鏈表的特殊性，我們a->b->c->d ，如果要刪除c那么就必須修改b.next->c為 b.next->d，所以找到前一個節修改其鏈表next地址，這個有點像dom操作中removeChild找到其父節點調用移除子節點

同樣的我們也在remove方法的設計中，需要設計一個遍歷往上回溯一個父節點即可

測試代碼：

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

JavaScript中數據結構與算法(三)：鏈表_javascript技巧

JavaScript中數據結構與算法(三)：鏈表_javascript技巧:我們可以看到在javascript概念中的隊列與棧都是一種特殊的線性表的結構，也是一種比較簡單的基于數組的順序存儲結構。由于javascript的解釋器針對數組都做了直接的優化，不會存在在很多編程語言中數組固定長度的問題(當數組填滿后再添加就比較困難了，包括添

推薦度：

點擊下載本文 文檔為doc格式

標簽： 技巧 js java

• 熱門焦點