链表快还是数组快？

[3dwelcome]

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

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



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

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

[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 ，这是一个动态数组，底层还是数组。。