---

hash table常用的实现方法之一就是数组+链表。

LRU其实就是hash_map + double linked list.

ASIO中的各种队列，用的都是单链表.

redis的定时器管理，用的是链表.

在key-value资料库里面大行其道的数据结构skip list，用的就是几个链表。redis/leveldb都用了它。

---

这个分两种情况。

一种是标准库中的链表。从我的使用体验来看，除了c++标准库中的链表提供了足够丰富的介面，其他语言标准库中的链表几乎是毫无用处。点名批评java的链表（因为迭代器概念过于孱弱）和rust的链表（因为生命周期和可变性的要求让操作过于受限）。

另一种是链表这个数据结构的概念，也就是俗称的手写链表。这个用处很大，例如可以用于其他复杂数据结构的底层实现，如斐波那契堆中用到了链表。如果要以库的形式提供这样的链表 ，我认为只有类似于linux内核中用到的侵入式链表是合适的。

不得不承认，虽然大家都很反感要求手写各种标准库中已经存在的数据结构，但是这样的技能对于高等次的开发是不可缺少的。

---

vector

---

任何数据结构设计的目的，表面是为了存储，实则为了快速遍历。当演算法复杂度无法成指数级优化的时候，人们想出了能否从数据结构中进行优化。

---

linux内核源代码

---

并发通信

---

面试(逃

基于升序链表的时间轮。。

以及其他数据结构的基础(跳跃表，自组织链表)。。。

---

科研

---

存储数据

---

这个问题要和动态数组比较。

动态数组是一些较为连续的内存空间，特点是随机访问速度较快，新增元素时可能需要扩容，增删首项的时间复杂度难以忍受。

这恰恰和链表是反过来的，链表可以有效利用碎片内存，随机访问速度慢，增删首项速度快，而且是递归定义的。

实际上链表只是递归定义类型的一个特例，二叉树等数据结构和链表是类似的。

如果不是函数式语言，更建议使用动态数组，真正需要链表的地方极少，大多数语言的标准库根本就不提供。要感受链表的作用，建议学习 Racket 或 Haskell 等函数式语言。

---

推荐阅读：