在計算機領(lǐng)域離不開算法和數(shù)據(jù)結(jié)構(gòu)，而在數(shù)據(jù)結(jié)構(gòu)中我們往往需要一些靈巧的結(jié)構(gòu)去處理一些繁雜的數(shù)據(jù)，鏈表 就是這樣一種能穿針引線般的幫助我們?nèi)ソ鉀Q這種問題的數(shù)據(jù)結(jié)構(gòu)。
它可以輔助組成其他數(shù)據(jù)結(jié)構(gòu)比如 隊列 。
后續(xù)的比如二分搜索樹，平衡二叉樹，紅黑樹等動態(tài)數(shù)據(jù)結(jié)構(gòu)都可以在理解鏈表的基礎(chǔ)上進(jìn)行深入的學(xué)習(xí)。
如果你是一個計算機初學(xué)者，那么對于鏈表的學(xué)習(xí)可以幫助你理解 遞歸 ，因為后續(xù)的二叉樹中需要深入理解 遞歸 。
鏈表的定義
在《算法（第4版）》中，對鏈表的定義如下：
鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者為空（null），或者是指向一個結(jié)點（node）的引用，該節(jié)點還有一個元素和一個指向另一條鏈表的引用。
鏈表的數(shù)據(jù)存儲在“節(jié)點”(Node)中：
在上節(jié)的 棧與隊列 一文中，都提到了 resize 這個操作，而通過觀察鏈表的數(shù)據(jù)結(jié)構(gòu)可以發(fā)現(xiàn)：
- 最后一個節(jié)點的 next 指向 NULL ，這個節(jié)點是最后一個節(jié)點
- 不像數(shù)組一下子必須new出來一片空間，無需考慮空間不夠用或浪費
- 需要多少個數(shù)據(jù)，就能生成多少個節(jié)點掛接起來
也就是說：鏈表具有動態(tài)的能力，不需要去處理固定容量的問題
正因為鏈表具備這種動態(tài)能力，那它也就缺失了高效的random access（隨機訪問）的能力。它無法與數(shù)組一樣，通過一個索引（index）直接獲取對應(yīng)的元素。
因為在底層機制中數(shù)組開辟的空間在內(nèi)存中是連續(xù)分布的，我們可以直接尋找索引對應(yīng)的偏移，直接計算出數(shù)據(jù)所存儲的內(nèi)存地址，直接用O(1)復(fù)雜度拿出。
鏈表靠next連接，每個節(jié)點存儲地址不同，我們只能通過next順藤摸瓜找到我們要找的元素。
鏈表的實現(xiàn)
這些就是鏈表的成員變量以及常用方法。
鏈表的添加元素操作
對于鏈表這種數(shù)據(jù)結(jié)構(gòu)而言，在鏈表頭或者鏈尾添加元素都非常方便。
將元素插入鏈表的中間位置也十分簡單，不過得注意插入的順序
Node insertNode = new Node(e);
insertNode.next = prevNode.next;
prevNode.next = insertNode;
對比兩組動畫后，聰明的你很快就會想：能否用同樣的代碼來處理鏈表的插入頭部和插入中間的操作呢？
答案是肯定的！只需要引入虛擬的頭結(jié)點的概念就行了。
那么就可以得到鏈表的添加元素的代碼：
鏈表的刪除元素操作
對于鏈表的刪除元素操作，需要找到目標(biāo)節(jié)點的前驅(qū)節(jié)點。
prev.next = delNode.next
delNode.next = null
鏈表的查找元素操作
虛擬節(jié)點所在的位置索引可以視為 -1
鏈表的修改元素操作
基于上面 鏈表的查找元素操作 很容易寫出 鏈表的修改元素操作
鏈表的時間復(fù)雜度
| 接口 | 說明 | 復(fù)雜度 |
|---|---|---|
| add(index, e) | 插入操作 | O(n) |
| remove(index, e) | 刪除操作 | O(n) |
| set(index, e) | 修改操作 | O(n) |
| get(index, e) | 查找操作 | O(n) |
| contains(index, e) | 也是查找操作 | O(n) |
正因為鏈表沒有索引，因此鏈表喪失了像數(shù)組那樣快速訪問的能力，這也就讓鏈表的增刪改查全都是O(n)級別的。
這看上去鏈表像是一個性能很差的數(shù)據(jù)結(jié)構(gòu)，那鏈表是如何能在數(shù)據(jù)結(jié)構(gòu)中穿針引線呢？
請繼續(xù)閱讀后續(xù)的內(nèi)容：如何用鏈表實現(xiàn)棧和隊列
