链表快还是数组快？

[3dwelcome]

最近在 B 站看一些 C++并发教学视频，我发现在服务器很多算法里，非常喜欢用链表。

然而由于现代 CPU 设计高速缓存的原因，我网上查性能对比环节，几乎 90%情况下，都是数组性能比链表好。



https://dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs

那么问题来了，是不是书本上链表算法已经过时，大部分情况下，用数组替代会更好一些呢？

[3dwelcome]

@xtreme1 rbtree 是自平衡的树吧，感觉正常来用，不会达到最大高度。

[BeautifulSoap]

@3dwelcome 我觉得老哥你可以学一下数据结构，了解下 Vector 这东西底层是怎么实现的。

随机性这东西是链表的弱项，链表每次访问指定节点都需要从表头 or 表尾重新遍历，所以复杂度是 O(n)，而数组随机访问的复杂度是 O(1)。但是相应的，数组（这里是 Vector ）插入数据最坏的情况下是需要将整个数组内容拷贝到新数组的。

链表适合极其大量数据，并且经常需要插入删除，但是又不是彻彻底底完全随机的那种。

[duke807]

直接用數組，增減元素時，除了現有數據要經歷拷貝

現有元素的引用者也會受到影響，因為引用可能會失效

對於 list （或 rbtree ），無論怎麼增減元素，現有元素的使用者也不會受到影響

[yehoshua]

链表适合数据多，经常插入排序等维护。从计算机体系来说，数组是直接访问，链表需要查询。所以一般情况下数组速度会快很多。但是数组维护起来很麻烦。如果是经常需要维护的数据，数组并不合适。

[BeautifulSoap]

@villivateur 咦，难道我数据结构学错了，我印象里 c++的 Vector 不是基于数组(array)的吗

[duke807]

@xtreme1 你對 rb tree 一定有什麼誤解，存 1000 個 node ，只需要 1000 個 node 的內存佔用，head 本身內存佔用忽略不計

[3dwelcome]

@duke807 “現有元素的引用者也會受到影響，因為引用可能會失效”

所以我数组一般都是存指针，指针不会失效。

而且数组还有一点好处，可以排序后二分法查找，查找元素速度比 rbtree 还要快。

[darknoll]

如果只是存取，那当然是数组快

[xuanbg]

增删链表优于数组，改查数组优于链表。

[villivateur]

@BeautifulSoap 噢噢，看来是我搞错了

[duke807]

@3dwelcome

總之，要刪增操作的話，用 數組 低效且不夠優雅，你用 vector 相當於把這份不優雅包裝隱藏了

另外，你數組只存指針本身也不優雅，多一次中轉就降低一份效率和降低代碼可讀性

關於這方面，你可以看一下 linux kernel 的鏈表實現方式，重點是使用 container_of 宏讓一切變得優雅和高效

簡單來説就是，傳統 c 語言鏈表的實現，是在 node 對象裡面放一個 void * 指針，指向用戶數據

而 linux 的實現，是反過來在用戶 struct 數據的任意位置，放一個 list node 成員，省掉了 void * 指針

嫌 linux 代碼多，可以看我這個 mcu 的 bootloader 代碼，和 linux 代碼類似，重點看 device_init 裡面，是怎麼把 數組 轉換成 鏈表，用做內存分配：

https://github.com/dukelec/stepper_motor_controller/blob/master/mdrv_bl/usr/app_main.c
鏈表本身的實現在這個目錄：
https://github.com/dukelec/cdnet/tree/master/utils

[Leviathann]

还是根据容量和操作的频率来决定
这类调优都应该以基准测试的结果为前提

[northernlights0]

比如要通过线性表实现一个队列，有大量的 push_back, pop_front 操作，就肯定是链表占优

另外排序二分是快，但是数组插入你就慢了

[GrayXu]

晕了，这贴里不少人没学过数据结构的样子。。

[3dwelcome]

@northernlights0 "比如要通过线性表实现一个队列，有大量的 push_back, pop_front 操作，就肯定是链表占优"

可以分而治之的，把一个超级大链表，转换成 N 个固定大小的数组集合。只对小数组进行局部操作，感觉也不会太慢。

理论上大家都知道链表插入快，而实际上 CPU 设计的高速缓存，天然就对数组有极强的亲和性。

而且在大部分情况下，查询的操作频率，要远远高于插入和删除。

[zhangchongjie]

要分情况说好坏吧，凡是没绝对

[msaionyc]

数组和链表在内存空间利用率方面的差别楼主不考虑吗？

另外我礼貌问下，楼主大学读的是计算机专业吗？没有其他的意思，感觉你看问题有点想当然，对数据结构的理解比较浅了。这些性能测试只能当作一种参考，真正什么场景用什么数据结构，开发人员心里要有数的，我看你上面回复的队列 /栈的问题，要分而治之用数组代替链表，我觉得这是为了不用链表而不用链表。

另外我再说一点，你看的是 cpp 这种偏低级一点的语言了，对一些高级语言来说，数组可能没法很好地利用 cache ，这时如果是在增删条件比较多的情况下难道也要用数组替换链表吗？

[msaionyc]

而且，帖子里有几位说到点子上了，你全都没有回复，我觉得有点奇怪

[msaionyc]

我一直认为，发表这种“xxx 过时”，“a 不如 b”这种话题应该非常慎重，尤其是技术方面

楼主不妨自己测试一下，就用 cpp ，写简单的代码测试做对比就能达到目的

[jedihy]

标题是链表快还是数组快。benchmark 放的是 vector 快还是 list 。