链表快还是数组快？

[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)，如果通过索引等其它方式能直接找到位置的话那绝对是链表快，所以也不是很反直觉啊。