链表和数组到底如何选用？
一句话概括
要决定用数组还是用链表，核心在于分析你的应用场景，以及对内存的要求
- 数组：连续内存、快读、慢增删
- 链表：分散内存、慢读、快增删
在实际场景中，除了增删查改，还有缓存、并发、内存碎片和实际的运用场景
底层机制
- 数组：在内存中是一块连续的空间。你可以通过首地址+偏移量瞬间计算出任意元素的位置
- 链表：在内存中是分散的空间，靠指针将各个节点串在一起。要找到某个节点，必须从头部挨个顺着指针找
基础对比
根据实际场景选择
首选数组场景
- 经常按下标随机访问
如果你要频繁读取第 10 个、第 1000 个元素，数组的时间复杂度是 O(1)（瞬间完成），而链表是 O(n)（需要遍历） - 遍历操作极多
虽然两者遍历都是 O(n)，但数组利用 CPU 缓存局部性原理，遍历速度通常远快于链表（链表节点跳来跳去容易导致缓存缺失） - 数据规模已知，且不经常插入/删除
特别是只在尾部进行添加或删除操作时，数组效率很高，链表的malloc/free消耗大 - 需要占用更少的内存
数组只需要存储数据本身。链表每个节点都需要额外的空间存储指针（双向链表需要两个指针），内存开销较大 - 对CPU缓存友好
数组是连续内存，CPU预读命中率极高
链表到处跳，缓存不命中，速度差一个数量级，哪怕链表 O(1) 插入，实际跑起来可能还不如数组
首选链表
- 频繁在头部或中间插入/删除
这是链表的王牌应用场景。只要知道操作的位置（例如已经有迭代器指向那里），插入/删除节点只需 O(1) 时间，只需修改指针指向
而数组在中间插入/删除，需要移动后续所有元素的内存位置（O(n)） - 无法预估数据规模，且数据量变化剧烈
链表的大小是动态的，随用随分配，不会像数组那样频繁触发扩容和拷贝 - 实现特定的数据结构
例如实现LRU链表、无锁队列等数据结构，通常依赖链表结构 - 对内存连续性要求不高
避免因为大数组分配要求连续内存空间而导致分配失败 - 数据长度完全不确定，频繁删减
实战决简化总结
- 读多写少 → 数组
- 写多（插删多）读少 → 链表
- 追求极致速度 → 优先数组（缓存友好）
- 长度不稳定、怕扩容拷贝 → 链表
- 简单业务、上层逻辑 → 一律数组
- 底层框架、内核、队列 → 考虑链表
最后两点相当重要，应用层用数组，驱动内核用链表
总结建议
- 大多数情况下，默认选择数组
- 如果你遇到了在列表头部频繁增删，或者在中间频繁增删且数据量很大的场景，可以考虑使用链表
- 如果真的很难抉择，先用数组，真遇到瓶颈再换链表或跳表、树等结构