链表快还是数组快？

[3dwelcome]

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

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



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

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

[xiaowei0823]

数组查询效率高，插入删除效率还是链表更优

[helone]

但是数据并非只查询啊，也要增加删除

[duke807]

方便用數組的時候當然首選用數組

用數組不方便的時候才用鏈表（譬如要釋放中間的某個元素，或者在中間插入一個新元素）

想進一步加快速度，則用 rb-tree 之類的

[haisayu]

conclusion
to conclude, we can get some facts about each data structure:

- std::vector is insanely faster than std::list to find an element
- std::vector always performs faster than std::list with very small data
- std::vector is always faster to push elements at the back than std::list
- std::list handles large elements very well, especially for sorting or inserting in the front
these are the simple conclusions on usage of each data structure:

- for number crunching : use std::vector
- for linear search : use std::vector
- for random insert/remove : use std::list (if data size very small (< 64b on my computer), use std::vector)
- for big data size : use std::list (not if intended for searching)

你给的链接说的挺清楚了。不同场景不一样。

[3dwelcome]

再发一张图，这是链表引以为傲的快速插入，理论上应该远快于数组。然而事实上，性能测试里还是被数组给灭掉了。

[senghoo]

主要看使用情景：
1. 数据量
2. 长度是否固定
3. 是否会有随机读写
4. 是否有随机位置插入，删除
等等。。

[BeautifulSoap]

不知道 lz 说的教程的场景和应用具体是怎样的

数组面对长度不确定、需要截断拼接、往中间插入 /删除 N 个元素等等操作的时候性能是很低的（你需要新建个数组然后把旧数据都搬过去，当然也有针对个别情况比如数组内插入或删除元素有高性能的优化算法）

[3dwelcome]

@helone
@xiaowei0823 你们没看完文章，随机插入测试环节，还是数组快。虽然这点很反直觉。。

[villivateur]

@3dwelcome 插入 1000 个数太少了，一级缓存都不止这么点，可以试试一百万这个数量级

[duke807]

@3dwelcome

數組插入快？你用的是假數組

真數組中間插入一個元素，插入點之後的所有元素都要經歷一次 copy 移动內存位置

[3dwelcome]

@haisayu “你给的链接说的挺清楚了。不同场景不一样。”

推荐 big data size 采用 std::list, 可是正常情况谁会直接存大对象。

一般大数据，不论是用数组还是链表，都是直接存对象指针的。

也是说，基本没有 big data size 的情况。。

[mainjzb]

？ 明显是楼主没看完文章
增加到 1kb 的时候链表赢了

[takato]

取决于最经常的操作是什么样的，许多数据结构在不同的方面表现都有所不同。

即使仅仅是查找操作，我们这里可能要考虑这样的问题：
高速缓存是否也是一种空间换时间的策略？
高速缓存是否是无限的？
假如数据量超过缓存以后性能会如何变化？

[duke807]

你發的連接是 vector vs list ，都不是數組好吧

c/c++ 的數組是類似 xxx_type xxx_variable[100]; 這樣的

[3dwelcome]

@duke807 “想進一步加快速度，則用 rb-tree 之類的”

rb-tree 底层应该也是链表之类实现的，毕竟是基于节点的算法。

我在想特定的条件下，红黑树实现改成数组，也许对性能影响也不大？

[iqoo]

iptables vs nftables 🐶

[duke807]

@3dwelcome
“一般大数据，不论是用数组还是链表，都是直接存对象指针的。”

這只是你個人喜好

我喜歡直接把大塊數據存到數組裡，而不是通過指針

在 MCU 環境（或者 rt preempt 實時 linux 用戶空間），我喜歡申請一個全局數組用來做內存分配，每個內存塊都是固定大小的一個數組元素，可以避免內存碎片，同時可以保證實時性。具體做法是上電初始化的時候，把數組每個元素轉換成鏈表，掛在一個叫 free 的表頭，其它業務從這個 free head 上取下內存塊使用，用完歸還到 free head 。

[xtreme1]

@3dwelcome
rbtree 当然可以用数组实现，但 rbtree 最大高度可以到 2*log2(n+1),
所以要存 1000 个 node ，你就要分配 1048576 个 node 的内存

[villivateur]

@duke807 真相了，list 和 vector 好像理论上都是链表

[vishun]

@3dwelcome 主要是链表要想插入前要先查找啊，查找也是 o(n)，如果通过索引等其它方式能直接找到位置的话那绝对是链表快，所以也不是很反直觉啊。

[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 。

[sdushn]

我理解是各有优点，实际使用中如果数据量小，在现代 CPU 的加成下，用什么都行，但是在复杂场景下就要想办法组合使用了吧

[3dwelcome]

@msaionyc "这时如果是在增删条件比较多的情况下难道也要用数组替换链表吗？"

不回复一些楼，又不是代表我持反对意见。

我只想讨论大概率使用场景。你如果写一个只有中间 insert 的对比场景，那肯定是链表比数组更占优势。

链表在数据结构里地位，和数组一样重要，我没怀疑这点。发帖的主要目的，只是想说明在现代 CPU 硬件设计上，对链表不友好，对数组更友好。相同场景下，优先考虑数组，仅此而已。

[3dwelcome]

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

以前是面向对象编程，现在时代变了，是面向硬件编程。

举个例子，有个叫 Odin 的新编程语言（ http://odin-lang.org/），这个就是为了优化硬件，而诞生的编程语言，所谓的 Data-Oriented Language 。

你可以照本宣科，表示大学书本数据结构里，链表 O(1)插入性能好。可真实高性能编程中，SoA （ array of structures ）的地位，要远高于 AoS 。你说为什么，就是因为 SoA 设计成面向 CPU 编程，有更好缓存亲和性，自然就有更好的性能。

[msaionyc]

“ 数组和链表在内存空间利用率方面的差别楼主不考虑吗？”
我觉得我第一句已经说出一些问题了。

我之所以发三条是我觉得你说话很不负责任，单纯凭借这篇性能测试就提出自己的观点，就认为链表过时。

另外我认为你评价我“照本宣科”也很不负责任，照本宣科是贬义词，你看完我上面提到的内存方面的问题了吗？

[3dwelcome]

@msaionyc 内存空间利用率具体指什么？没太搞懂，按理说数组比链表要节约内存。

链表你还要多一个 next 指针才行。

[haah]

还是哈希快！

[msaionyc]

数组必须要提前申请内存空间，没用满时等于空了的部分是浪费了的。

另外，插入操作可能会导致数组长度不够用，需要重新申请空间，原来的 delete 掉。

不论是平时大部分人都在做的业务场景，还是操作系统内部对于内存的管理，对于任务的调度，数组和链表都有各自的应用场景，你居然会根据一篇性能测试说出链表过时，太匪夷所思了

[3dwelcome]

@msaionyc

“需要重新申请空间，原来的 delete 掉。”， 旧空间也可以不删除的，多个子数组拼成一个大数组就可以不用删掉了。

“数组必须要提前申请内存空间，没用满时等于空了的部分是浪费了的。”
这句话也不对，操作系统对于应用程序申请了，但没有实际使用的内存，是不会真实分配的。只有第一次赋值或者初始化时，才会分配物理内存。

总的来说，还是链表占用内存更多。一个 next 指针需要 8 字节，对比一个 1M 大小的数组，链表比数组要整整多出 8M 额外内存。

[dqzcwxb]

数组查找效率高,链表增删效率高
这不是入门知识?

[llh880808]

@3dwelcome 只考虑绝对内存占用，链表是比数组多，但是

一方面要考虑链表结点的数据部分有多少，不能认为链表结点只存储一个整形数，如果数据部分足够大，指针部分浪费的空间就微不足道了，当然绝对来看内存占用还是比数组多

另一方面，数组占用的内存必须是地址连续的，在系统启动一定时间后，有可能没有足够大的连续内存，而链表可以有效利用零散的内存

所以，
链表是不是比数组占用内存多？是的
链表是不是比数组浪费内存？不一定，我倾向于否

[pursuer]

@3dwelcome 多个子数组拼成大数组不就是数组组成的 list 了吗。实际优化过程中也是可以采用数组组成的 list 来实现速度和存储的平衡的。
数组插入比链表快是利用了高速缓存的特性，但有些嵌入式设备高速缓存都没有，链表的优势就体现了。

[Huozy]

@llh880808 #50 老哥也是真的认真在回复。op 就是在杠啊“旧空间也可以不删除”，数组占用连续地址这个问题在 op 眼中是完全不考虑的。

[Mystery0]

多个小的数组拼成一个大的数组，那还是数据结构里面的数组吗，况且多个小数组怎么拼起来？用指针链起来？

[dcsuibian]

数组查询 O(1)，插入 O(n)。链表查询 O(n)，插入 O(1)。但你误解链表的这个 O(1)，这个 O(1)指的是你已经拿到了中间某个节点的指针，然后想往附近插入 /删除一个元素的情况。

你看的那两张随机插入和随机删除，是以下情况：
随机给一个位置 i ，然后让 list 和 vector 进行插入 /删除操作。那么这时候时间复杂度就不是 O(1)了。因为链表还要从头一直往后找，找到位置 i 的那个节点，即有 O(n)部分，但真正的插入 /删除还是 O(1)的。而 vector 找起来很快，耗时的是移动后面的元素（不考虑再分配的话）。

你应该看 random insert 最后一张图，那张才是链表的正确应用，文章也有提到：
if the iterator was already known (no need for linear search), it would be faster to insert into a list than into the vector.
所以并不反直觉。

如果你的应用场景并没有把查找的那个 O(n)去掉，那么数组更快也很正常。

[3dwelcome]

@Mystery0 "况且多个小数组怎么拼起来？用指针链起来？"

用二维指针就可以，比如 int** array 就能把数组缝合起来。或者更简单的形式，用 vector<int*>这种。

你面向硬件编程，把大数组切分成小数组是必然的。操作系统是有 4k 之类内存区块概念的，分配的数组不能太大，不能太小，性能才最好。

[hitmanx]

@3dwelcome 听上去有点类似 STL 的 dequeue ，https://jingyan.baidu.com/article/358570f67b4ebcce4724fcb3.html

这种 hybrid 的数据结构看上去很好，实际上经常是两头都不讨好。所以实际利用率很低

[3dwelcome]

@hitmanx 别人不知道，我代码里很多这种“缝合数组”。

原因就是在长度增加同时，能避免旧数组失效，这特性对我挺重要的。

[Caturra]

高速缓存在并发的条件下不一定是“高速”的，并发写操作可能对数组这种连续分配的内存造成频繁误伤，这可能是楼主提到的服务器中算法喜欢用链表的原因（虽然我不了解是否真的倾向于用链表，以及链表和数组的区别对于重 IO 服务来说是否有一丁点影响）

只考虑通常意义下的性能的话，一般数组实现的数据结构还是优于链表实现。以前打算法竞赛很喜欢把一堆链 /结点的平衡树改写成数组实现（因为数据大小都是已知的，数组的范围肯定能确认），跑分基本都是数组要快一截，数据量级大概是增删改查十万到百万每秒

[Caturra]

@hitmanx STL 实现常人很难理解，不看点资料都不知道为啥要搞这么诡异的事物。印象中 deque 的奇妙设计好像是为了避免迭代器失效才这么写的，性能可能就凑合水平（可是凑合归凑合，为啥 stack 默认是由 deque 来适配？还是难理解）

[Cola98]

帖子看下来了，如果只是回答数组和链表谁快，这没有说操作，怎么对比？如果是删除和添加一个元素，数组需要移动位置，所以它的时间复杂度高，而链表只需要修改一个节点。如果是查询，因为数组的元素都是挨着的，速度比链表快。关于 vector ，这是一个动态数组，底层还是数组。。

[lifanxi]

@3dwelcome
你似乎有个误解，认为 std::vector 可以通过拼接串联小数组的方式来进行优化，减少扩容时复制数据的开销，但这是不对的，C++标准上强要求 std::vector 的内存必须是连续的。如果不连续，它就不叫“数组”，也不叫“std::vector”。

为了保证这个连续性，所以数组或 std::vector 在插入数据或扩容时，势必需要进行数据复制，这在数据量大 /对象复杂的时候有不可忽略的性能开销。

所以其实你贴的文章中说得很清楚，在多插入场景下，std::vecotr 只有在非常小数据量的情况下，性能才比 std::list 要好。这一点无论从理论上还是实践中都可以得到证实。

在实际开发中，是不是因为自己的场景下数组比链表快那么一点点就一定要用数组呢？我觉得不对的。写代码时更多要考虑代码所要表达的思想，如果你代码的逻辑是一个典型的链表更优场景，就应该在代码中用链表。这样的代码长远来看才更好维护。如果确实为了极致性能想改成用数组，也需要加注释保证以后别人在数据集变大遇到性能问题时可以及时定位，甚至加 fallback 逻辑自动保证在大数据集情况下不会带来严重的性能回退。

[summerLast]

@3dwelcome 数组是连续的，计算机架构里面有用空间换时间的多级 cache ，整块的空间更容易被 cache 提高命中率，其中的关键是 cache 和 内存的访问速度不是一个数量级,数组更容易被 cache ， 如果没有 cache 或数组较大时链表插入更优秀

[summerLast]

@summerLast 内存空间连续的

[ExplorerLog]

std::array
std::vector
std::list

[3dwelcome]

@lifanxi “你似乎有个误解，认为 std::vector 可以通过拼接串联小数组的方式来进行优化”

不以长短论英雄。缝合小数组(deque)也是数组里的一个分支。

13cm 和 18cm 哪个更强？不好说的。

链表还有一个最大的问题，是不好维护。你数组还能设个越界报错，新手链表用不好，指针就在天上乱飞。

[xtinput]

内存读写速度成倍提升，CPU 运算速度增长缓慢
数组慢的地方是增删，增删主要是内存读写
高频增删用链表
高频读取用数组

[stuazt]

链表快还是数组快。。。这个学算法和数据结构的时候，不是 101 问题吗