我是一个c小白，我过去学习过cpp。这个寒假开始阅读一些纯c语言的开源项目，发现都重度使用链表。 例如，libhv里面的timer，是最小堆，是使用链表实现的。
在c++中，对于顺序容器，是鼓励使用vector的，因为大多数场景vector具有更好的性能。但是c的项目，很少去实现一个vector，更多是使用链表，不怕这样会影响性能吗？
这就是砖石与房屋的关系了.
便于实现, 内存空间紧凑, 不是很多数据的情况下 O(n) 访问没什么感觉
你想用 vector 的话可以用这个 https://troydhanson.github.io/uthash/ 里面的 utarray
1 个赞
主要原因是 C 的标准库东西比较少，里面没有 std::vector 这种东西，所以大家都自己实现了。
但是多数 C 项目里实现的链表并不是类似 std::vector 的容器（无泛型），而是 intrusive 的。通过 container_of 很容易由 next 指针转换得到对应结构体的指针，依托于这点，其实现的链表相关 API, 如 list_add_element 之类的也可以很通用。如果对 intrusive list 感兴趣，可以看一下 linux 里的实现。
4 个赞
例如，libhv 里面的 timer，是最小堆，是使用链表实现的。
首先这里需要纠正一下。libhv 用最小堆来管理 timer 不假，但它并不是使用“链表”实现的。
通过阅读相关源码，可以看到，这个最小堆也是一个基于二叉树的实现，只不过这个二叉树是用指针来记录节点之间的关系，而不是用数组。
为什么采用这种方式来实现呢？这里可以给出一个 educated guess：
- 无需为最小堆额外进行内存管理（包括初始化、扩容、释放），实现成本低。因为二叉树结点的内存空间是和 timer 对象的其他成员一同分配的，使用时赋值即可。
- 和最小堆的数组实现相比，时间复杂度是相同的，不存在显著的性能缺陷。虽然由于 spatial locality 等原因，实际性能会差一些，但相对于其他影响性能的昂贵操作（比如频繁的系统调用，拷贝 buffer 等），往往可以忽略不计。毕竟我们编写网络应用时，一般不会存在大量 timer 同时 pending 的场景。
那我们可不可以用数组实现的最小堆来管理 timer？当然可以。比如 swoole 的 heap 实现，就是用的数组。如果有兴趣，可以去看一下其他的网络 I/O 库，比如 libev、libuv、Boost.Asio 等，都是如何管理 timer 的。
另外，作为 libhv 的贡献者之一，这里不得不吐槽一句：libhv 的代码风格和组织形式不是很优雅。当初我尝试改它代码的时候，内心是崩溃的。。如果作为初学者，不建议阅读，容易对自己的代码风格起到负面影响。建议先从我上面提到的那几个库读起。
很少去实现一个 vector，更多是使用链表，不怕这样会影响性能吗？
上面也说过，当高性能不是首要目标时，出于一些其他的考虑，会选用一些性能不是那么好的实现。
再举几个例子吧。
众所周知，Bash 的数组[1]的底层实现是链表，而不是“内存连续的线性表”。这大概是因为 Bash 从语言层面，并不需要预先指定数组大小，也不要求数组元素是连续的。
所以如果有人这样写：
declare -a arr
arr[65535]='holy'
arr[2147483647]='shit'
如果 Bash 是采用传统的内存连续的数组实现，对于这种“稀疏”的数组，就不得不浪费大量内存，很容易就会 OOM。
所以，作为实现者，我们需要考虑下面几个问题：
- 要不要为这种“不负责任”的写法优化？
- 当然要！shell 就是要做到能“一把梭”，让不怎么懂编程的普通人也能轻松使用。随便定义了几个数组就 OOM 了怎么成？
- 采用其他数据结构，所导致的数组随机访问的性能下降，是否是可以接受的？
- 没问题！没人会在 shell 里面进行计算密集的操作，这些工作应该交给其他编程语言去做，然后提供 cli 供 Bash 调用。因此，时间复杂度为 O(n) 的数组随机访问也是可以接受的。
这下，该怎么实现就很明了了。
有的同学看到这里可能会反驳，如果用哈希表实现不是更好么？用下标做 key，就可以做到 average O(1) 了。
没错，而且很多语言的解释器就是这样实现数组的。
比如，PHP[2] 的 associative array 在元素下标均为不小于 0 的整数且连续时（用一个值为 HT_IS_PACKED 的 flag 标识），则会连续地储存。如果某次插入导致数组下标不连续，就会转化为哈希表实现。
还有 Tcl 的数组，底层完全是哈希表实现，不管 key 是不是整数。值得一提的是，这里用到的哈希函数是特别为 digit string 优化的，对于纯数字字符串的 key 占多数的场景下，分布比常用的 FNV 等哈希函数要好一些。当然，Tcl 中也有内存连续的数组：list[3]。
这些解释器选择了较低效的数组实现，究其原因，无非是要放宽数组在空间上存在的物理限制，从而使得它的使用更加灵活。
引申开来，我们在进行软件开发时的其他场景下，也经常要在性能和便利之间找到一个平衡点。这是需要具体问题具体分析的。
- [1] 这里指的是 Bash 的 indexed array。字符串下标的 associative array 的底层实现是哈希表。
- [2] 这里特指 PHP 7.x，因为其他版本的 PHP 源码我没读过，不知道有没有发生过改变。
- [3] 只在 8.x 版本的现代 Tcl 中，list 才是这样实现的。7.x 版本的 Tcl 的 list 实现非常朴素，每次使用需要现 parse，而且并不会将 parse 结果作为 internal rep 缓存起来。因此
lindexlset之类的函数是非常低效的。在 Guile 被提上日程的前夕，RMS 曾经锐评 Tcl，其中一点，就是 Tcl 没有内存连续的数组。
27 个赞
因为大部分情况下不会收到 O(n) 访问速度的限制。
不能这么说，举个例子：Emacs 内置有 vector，却还用 cons 来实现计时器。
swoole的heap数组竟然就是一个二级指针，然后实现std::vector的二倍扩容。我之前一直想着用c语言怎么去封装一个动态数组，原来可以这么暴力实现 
说实话，我不敢这样做。。
适用场景多，可扩展性好