---

hash table常用的實現方法之一就是數組+鏈表。

LRU其實就是hash_map + double linked list.

ASIO中的各種隊列，用的都是單鏈表.

redis的定時器管理，用的是鏈表.

在key-value資料庫裡面大行其道的數據結構skip list，用的就是幾個鏈表。redis/leveldb都用了它。

---

這個分兩種情況。

一種是標準庫中的鏈表。從我的使用體驗來看，除了c++標準庫中的鏈表提供了足夠豐富的介面，其他語言標準庫中的鏈表幾乎是毫無用處。點名批評java的鏈表（因為迭代器概念過於孱弱）和rust的鏈表（因為生命週期和可變性的要求讓操作過於受限）。

另一種是鏈表這個數據結構的概念，也就是俗稱的手寫鏈表。這個用處很大，例如可以用於其他複雜數據結構的底層實現，如斐波那契堆中用到了鏈表。如果要以庫的形式提供這樣的鏈表 ，我認為只有類似於linux內核中用到的侵入式鏈表是合適的。

不得不承認，雖然大家都很反感要求手寫各種標準庫中已經存在的數據結構，但是這樣的技能對於高等次的開發是不可缺少的。

---

vector

---

任何數據結構設計的目的，表面是為了存儲，實則為了快速遍歷。當演算法複雜度無法成指數級優化的時候，人們想出了能否從數據結構中進行優化。

---

linux內核源代碼

---

並發通信

---

面試(逃

基於升序鏈表的時間輪。。

以及其他數據結構的基礎(跳躍表，自組織鏈表)。。。

---

科研

---

存儲數據

---

這個問題要和動態數組比較。

動態數組是一些較為連續的內存空間，特點是隨機訪問速度較快，新增元素時可能需要擴容，增刪首項的時間複雜度難以忍受。

這恰恰和鏈表是反過來的，鏈表可以有效利用碎片內存，隨機訪問速度慢，增刪首項速度快，而且是遞歸定義的。

實際上鏈表只是遞歸定義類型的一個特例，二叉樹等數據結構和鏈表是類似的。

如果不是函數式語言，更建議使用動態數組，真正需要鏈表的地方極少，大多數語言的標準庫根本就不提供。要感受鏈表的作用，建議學習 Racket 或 Haskell 等函數式語言。

---

推薦閱讀：