数组和链表的博弈我是在一次网关过滤规则的性能优化里真正体会到的。当时我们维护的过滤规则列表是用标准库的链表组织起来的每个请求进来都要把几百条规则从头到尾过一遍压测时单核吞吐一直上不去。我的第一反应是把规则切换成数组结果同组的人反手做了一组对照当规则数压到几十条之后链表版本反而“看起来”更快。这个矛盾把我拉进了对数组和链表底层机制的深挖也让我想清楚了一个问题——速度与灵活的博弈从来不是单纯比谁的复杂度数字更小而是看你的访问模式到底在跟哪种内存布局打交道。1. 一次压测暴露的真相数组打败了链表但不是所有场景1.1 过滤链从链表换成数组后的实测变化先说那组让我印象极其深刻的数据。过滤规则本质上是一组条件表达式请求进来之后需要依次判断这些条件是否满足。最初的版本用链表存规则插入新规则很方便运行了一段时间也没人觉得不对。直到我带着压测工具去测峰值吞吐才发现单核 CPU 被顶满了但业务需求还差一大截。把规则从链表换到数组之后同样的机器、同样的压测脚本单核吞吐直接翻了接近一倍。刚开始大家都以为是自己眼花因为从理论复杂度上看链表和数组的遍历都是 O(n)换结构不应该有这么大差距。后来我们用性能分析工具去看 CPU 的周期分布才发现在链表版本里处理器大部分时间都停在了“等内存”上而不是真正在跑规则判断。原因说穿了很简单数组的几百条规则地址是连续排布的一次内存读取能把后面十几条甚至几十条规则都拖进 CPU 缓存链表的每个节点都是独立分配的一块内存指针从一条跳向下一条时CPU 往往要重新去内存里取数据预取器也帮不上忙。这个差距在大数据量下会被放大到非常明显。1.2 快速打脸案例数量小时链表没输但真正让我清醒的是规则数压到几十条之后的对照结果。这时候链表版本反而跟数组版本打成了平手甚至某些极端情况下还略快一点。原因也简单几十条规则的数据量太小了全部都能塞进 CPU 缓存内存布局的差距被缓存完全抹平。这个“打脸案例”非常重要因为它说明了一个被很多教程忽略的事实数据结构的优劣不是绝对的它跟数据规模、访问模式、硬件缓存都强相关。我见过太多人一听到“链表插入快”就无脑用链表一听到“数组随机访问快”就无脑用数组结果两头都吃亏。1.3 结论没有绝对好坏只有访问模式匹配那次压测之后我给团队定的选型口号就一句话先想清楚数据是读得多还是改得多读写发生在头部、尾部还是任意位置再决定用哪个结构。数组和链表没有谁更高级只有谁更匹配当前场景。这个道理听起来简单实际执行起来还是有不少门道。下面我就把两个结构的内存模型、操作复杂度、真实成本一项一项拆开说。2. 大O之外的第二条线内存布局才是性能分水岭2.1 数组的经济学连续内存、随机访问与均摊扩容数组的本质是一段连续的内存每个元素占用固定大小的空间所以只要知道起始地址和元素下标就能通过一个简单的乘法算出目标地址。这就是随机访问 O(1) 的来源也是数组在索引场景下无可替代的原因。动态数组比如各种语言里的 ArrayList、vector在容量不足时会申请一块更大的连续内存把旧元素整体拷贝过去。这个拷贝操作单次是 O(n) 的但因为容量是翻倍增长的多次插入平摊下来单次追加依然是 O(1)。这是理解动态数组性能的一个关键点很多人在“数组插入尾部不是要搬移吗”这个问题上想不通其实就是没理解均摊分析。数组的另一个容易被忽视的优点是遍历时的内存带宽利用率极高。因为元素连续排列CPU 加载一个缓存行的时候顺便就把相邻元素也装进来了走完整个数组其实很少触发真正的内存访问。这也就是压测里数组版本能赢的主要原因。2.2 链表的组织方式指针让结构自由也让数据散落链表把“每个元素”从“数组里的一个格子”变成了“一个独立的小对象”这个对象里既包含业务数据又包含指向下一个节点的指针。好处是节点在内存里不需要挨着想在哪插入一个新节点都可以只要把前后两个节点的指针重新连一下就行。结构上获得了自由代价是数据在物理内存里是散落的。散落意味着什么每次访问一个节点CPU 都要根据指针去内存里找它的位置。如果这些节点是在不同时间用 new 或 malloc 分配出来的它们大概率分布在内存地址空间的各个角落完全没有规律。CPU 的预取器擅长识别规律的访问模式碰到这种“完全随机”的跳转基本只能老老实实等内存。2.3 复杂度对照表越看越有讲究我把数组和链表最核心的操作复杂度放在一张表里接触过数据结构的人应该都能看懂但真正值得琢磨的是表里那些“有条件”的部分。操作场景动态数组单向链表双向链表按下标读取第 i 个元素O(1)O(n)O(n)从头遍历全部元素O(n)O(n)O(n)在尾部追加元素均摊 O(1)尾指针 O(1)否则 O(n)O(1)在头部插入元素O(n)O(1)O(1)在头部删除元素O(n)O(1)O(1)已知前驱节点后插入O(n)需要搬移后续所有元素O(1)O(1)已知某节点指针后删除O(n)需要前驱单链 O(n)O(1)空间额外开销几乎为 0每节点一个指针每节点两个指针缓存友好度高低低这张表里最值得画重点的一句是“已知前驱节点后插入”。链表的 O(1) 插入快前提是“你已经站在了那个位置上”。如果你只知道下标想在第 500 个位置插入仍然需要从头部一路找过去这一步就是 O(n)。而数组虽然插入时要把后面的元素全部搬移但如果插在尾部就是均摊 O(1)。所以很多人背下来的“链表插入快数组插入慢”其实是半个结论完整结论要看插入位置和是否已经持有节点指针。3. 链表“灵活”的代价从插入删除到内存分配的完整成本3.1 Cache line 是如何帮数组“作弊”的现代 CPU 读取内存的最小单位不是单个字节而是一个缓存行cache line常见大小是 64 字节。也就是说CPU 想读一个 4 字节的 int实际上会把附近 64 字节一起从内存搬到 L1 缓存。这 64 字节里可能有 16 个 int后续遍历这 16 个 int 时都不需要再访问内存。这就是数组遍历快的底层逻辑。它不是在偷懒而是内存访问模式天然符合 CPU 的工作方式。顺序访问数组时预取器还能提前把后续的缓存行拉进 L2/L1进一步降低等待时间。链表怎么跟这种机制对抗一个链表节点如果包含一个 int 数据和一个指针通常需要 16 字节左右再加上内存分配器的管理头可能就占掉一块 32 字节甚至更大的内存区域。问题是这些节点在地理位置上是分散的第 1 个节点在第 100 号缓存行第 2 个节点在第 98 号缓存行第 3 个节点跑到了第 999 号缓存行预取器完全无法预测下一个该读哪里。每次访问都是一次新的内存延迟。3.2 节点散落导致的预取失效算一笔账我给一个直观的算账示例。假设要遍历 100 个元素数组版本第一次访问大概会把 64 字节缓存行读进来里面含约 16 个元素后续 15 个元素的访问等于零成本。整体下来只触发 6 到 7 次真正的内存读取。链表版本每个节点分散在不同地址理想情况下每个节点都要触发一次缓存行加载。就算运气好每 2 个节点共享一个缓存行内存加载次数依然是数组的十倍以上。工程上这意味着一个简单的遍历链表可能消耗数十次内存访问延迟而数组只需要几次。一个内存访问延迟大约能到 100 纳秒级别一亿次遍历积累下来差距就很可观了。3.3 动态数组扩容与节点级分配两笔开销对比链表的另一个隐性成本在内存分配器上。每次 new 一个节点底层都要走一次分配器。分配器内部有各种空闲链表、内存池管理逻辑如果分配和释放频繁还可能产生大量内存碎片。节点的地址因此变得更加不可预测缓存命中率进一步下降。动态数组的扩容虽然也有拷贝成本但它有一个明显的优势扩容时机是明确的内存是成块申请和释放的翻倍策略保证了空间浪费不超过已用容量的一半。对现代内存分配器来说大块连续内存的管理开销远小于成千上万个小块节点的管理开销。当然这不是说链表一定会产生大量碎片如果你在设计阶段就规划好内存池或者使用预分配的节点数组碎片问题是可以规避的。问题是大多数项目没有这个规划和意识而是直接让链表节点随用随分。3.4 知道“前驱节点”这件事决定了链表的真实优势再回到选型最关键的细节链表真正的优势场景是“你已经拿到某个节点要在它后面插一个节点”或者“我已经定位到要删除的节点想 O(1) 删除它”。这就是为什么 LRU 缓存、双向链表配合哈希表是经典组合。哈希表负责快速定位 key 对应的链表节点双向链表负责在定位完成之后用 O(1) 完成插入和删除。如果没有哈希表辅助定位链表查找节点还是得从头遍历那么“删除一个 key”依然是 O(n)链表的优势就体现不出来。所以每次有人问我“链表到底快在哪”我都会反问一句你拿到那个操作的锚点了吗锚点就是前驱节点或者节点本身。拿不到锚点链表在性能上往往反而吃亏。4. 选型决策表拿访问模式反过来推结构4.1 访问密集场景数组的无条件优势如果你的核心场景是“按下标访问、按顺序遍历、对数据进行二分查找”那数组几乎没有对手。随机访问 O(1) 意味着索引查快顺序遍历意味着缓存友好二分查找意味着数据必须支持随机访问。举一个很典型的例子一个排行榜模块每天固定维护几千条积分记录需要频繁按名次查人也需要对积分做排序。这种场景用链表会非常痛苦因为“按名次取记录”是随机访问链表要做 O(n) 的跳转数据量一大立刻崩。用数组加排序配合二分查找性能始终稳定。另一个容易忽略的点是序列化与网络传输。数组可以整块内存直接写出链表的节点零星分布写出去之前还得一个个遍历组装。如果你需要把一个数据集合频繁写入网络或者落盘数组的内存连续性同样是巨大优势。4.2 增删频繁场景链表真正发光的条件链表发光的场景通常有三个特征数据总量动态变化很大、操作集中在头部或已定位的节点、对随机访问几乎没有要求。比如一个待处理任务队列任务经常从头部被取出新任务从尾部进入中间不需要按下标读取。此时用双向环形链表配合头尾指针能做到 O(1) 的头尾操作而且不会像环形数组那样出现“容量满了需要扩容”的问题。再比如一个撤销历史栈操作基本都是固定一端的压入和弹出链表和动态数组都可以但链表胜在长度无限伸缩时不需要偶尔的大拷贝。但要注意如果这个“增删频繁”的队列是并发场景链路就得换一套思路。多个线程同时动头尾必须在链表中加锁或使用无锁技术复杂度会显著提升。此时数组版本的环形队列反而更容易做无锁化尤其是单生产者、单消费者的模型用环形缓冲数组可以完全不用锁。4.3 并发与实时场景环形数组与无锁链表的取舍并发场景下的选型很多人会陷入两难。链表节点天然是独立的看起来更适合让不同线程操作不同区域数组共享同一块内存看起来需要更多同步。真实情况恰恰相反。单生产单消费者队列用数组实现的环形缓冲ring buffer非常漂亮生产者只写 tail 位置消费者只读 head 位置两边只要各自维护一个线程安全的读写指针配合内存屏障就能做到无锁并发。这样的队列在高性能日志收集、音频处理、网络收包里被广泛使用。多生产者多消费者下数组方案竞争会集中到少数几个计数器上链表也无非是把竞争分散到节点指针上但节点分配与释放的过程又变成了新的竞争点。真正要用好无锁链表得配合无锁内存池否则分配器本身的锁会成为瓶颈。所以并发场景我的建议很直接优先考虑环形数组只有在业务要求“任意位置稳定插入删除”时才走无锁链表。4.4 混合结构哈希表加双向链表解决 LRU 问题实际工程里最常用的往往不是纯数组或纯链表而是混合结构。我印象最深的是给一个缓存模块做过一次改造。那是一个标准的内存缓存要求满足“访问某个 key 后把它标记为最近使用容量满了淘汰最久未使用的 key”。如果只用哈希表淘汰逻辑没法按时间序做如果只用链表查找 key 要遍历链表。最终方案是哈希表加双向链表哈希表的值指向链表节点链表负责维护使用时间顺序。查询一个 key 时先用哈希表 O(1) 找到节点再把它移到链表头部淘汰时直接摘除链尾节点同时把对应的哈希表条目删掉。这个结构正是 LRU 缓存的标准解法也是“数组负责索引、链表负责任意插入删除”的典范。5. 绕开二选一数组模拟链表与链表的数组化改造5.1 静态链表用数组下标当指针很多情况下你需要的既不是纯数组也不是纯链表而是“数组底座上的链表逻辑”。静态链表就是这么一种结构它用数组来存节点节点之间的“指针”退化成整数下标。下面是一个很小的 Python 示意核心是用 next 数组记录下一个节点的下标用 free 记录空闲节点链表的头部class StaticList: def __init__(self, capacity): self.capacity capacity self.data [0] * capacity self.next [i 1 for i in range(capacity - 1)] self.next.append(-1) self.free 0 self.head -1 def insert_front(self, value): idx self.free self.free self.next[idx] self.data[idx] value self.next[idx] self.head self.head idx def traverse(self): cur self.head while cur ! -1: print(self.data[cur]) cur self.next[cur]这个做法的最大好处是节点内存全部预先分配、连续排布遍历时虽然逻辑上在跳指针物理地址却在一个连续数组里缓存命中率比真正的散落节点高得多。缺点是需要提前确定最大容量扩容时要整体搬移所以更适合容量上限明确的场景。5.2 内存池把散落的节点重新聚拢如果你的场景不允许提前设定容量但又希望链表节点缓存友好内存池是另一个答案。思路也很直接预先向操作系统申请一块大内存按固定大小切成若干块空闲节点需要新节点时从池里拿一块释归还时放回池里。这样所有节点都只出现在预分配的连续区域里地址范围变小缓存命中率显著提升分配和释放也避免了频繁调用系统级分配器。我在一个实时性要求比较高的消息转发模块里用过这个方案原来链表节点频繁 new/delete耗时抖动很厉害改成内存池后链表节点地址集中在一个 8MB 的内存块内遍历时的缓存表现明显变好抖动也小了很多。当然代价是内存池内部需要自己管理空闲列表且固定大小节点会造成一定程度空间浪费适合节点结构比较统一的场景。5.3 跳表给链表加高速索引兼顾查找和插入如果想在“有序插入”和“按范围查找”之间同时获得好性能跳表是一个值得了解的方案。它本质上是在链表上叠了多层索引底层是完整的有序链表上层每几个节点抽一个出来作为“快速通道”。查找时先从顶层索引开始大步跳逐层下降到最底层整体查询复杂度能降到 O(log n)。插入时先通过索引定位合适位置再决定要不要提层到更高索引。这种结构既保留了链表“节点插入删除局部性好”的优点又补上了链表“查找慢”的短板。Redis 的 sort set 场景之所以用跳表其中一个原因就是它需要频繁的范围查询和按分值排序跳表在这种混合负载下表现稳定实现也比平衡树直观。如果你在一个项目里既想保留链表的插入灵活性又忍受不了 O(n) 查找跳表就是比平衡二叉搜索树更容易理解和落地的替代品。5.4 改造案例把链路追查结构从指针链表改成数组游标最后分享一个具体的改造案例。当时某个内核态扩展模块需要维护一串“事件溯源记录”每个事件会指向前后事件形成一条链。最初用指针双向链表问题有两个一是每新增一条记录都要动态分配内存二是内核态里分配内存的实时性很不稳定。后来改成“数组游标”结构所有记录预先放在一大块连续内存里每个记录里只存前驱和后继的下标记录满了就把最早的下标回收。这个改造之后整个链条的遍历速度明显提升记录的新增删除也变成了简单的整数赋值。更关键的是因为所有记录都在这块连续内存里做整体快照和持久化变得极其方便一次性把整块内存写出去即可不再需要逐个节点序列化。这就是“链表的逻辑、数组的肉身”带来的双重收益。6. 实际项目里我反复踩的三个坑6.1 不要只看操作复杂度忘了遍历成本第一个坑就是开头讲过的很多人在对比数组和链表时只盯着“插入是 O(1) 还是 O(n)”却忽略了“遍历整个结构”这个最常见的操作。在我的经验里业务系统里 90% 的数据结构使用场景都是遍历和查找真正的任意位置高频插入其实没有那么多。即使是同样 O(n) 的完整遍历数组因为缓存局部性实际耗时可能只有链表的几分之一。如果遍历本身还附带过滤、聚合、序列化操作差距会被进一步放大。所以选型之前一定要先统计一下这个结构最频繁的操作到底是读、是查、还是改。6.2 数组复制与扩容的迭代器失效数组也不是没有坑其中最容易踩的就是扩容导致的迭代器失效。动态数组在容量不足时会把内部存储迁到一块更大的连续内存所有指向旧内存的指针、引用、迭代器都会失效。如果你一边遍历一边往里追加元素轻则逻辑错乱重则直接崩溃。解决方法通常有两个要么在扩容操作之前统一分配好最大容量要么在遍历时只记录下标并在扩容后重新获取引用。工程上我更推荐根据业务数据的量级预估容量尽量避免频繁扩容这不仅是为了避免迭代器失效更是为了减少拷贝带来的 CPU 开销。6.3 嵌套结构里如果“每一个元素都是链表”该怎么办最后一个坑来自“链表的数组”这种嵌套结构。比如你有一个数组每个数组元素又是一条链表这在实现哈希表链地址法时非常常见。表面上看既有随机访问又有灵活的冲突链性能应该不错但我做过性能分析后发现如果每条链都很短链表的指针跳转和缓存不友好会被无数条链叠加放大整体遍历速度反而远低于直接把冲突元素存进一个连续桶里的方案。所以嵌套结构必须放到两层上去考量。外层是数组没有错内层到底用链表还是连续缓冲要看每条链的平均长度。链长普遍在 3 以内时线性探测连续桶基本更好链长经常超过 10 再考虑链表或树化。这算是我踩过最多的一次教训也再次印证了前面那句话选型永远要回到数据和访问模式本身。数组和链表这场博弈让我学到的最实在的一条就是先把内存和分配这两笔账算明白再回头做选择。很多场景下真正的答案不是“数组还是链表”而是“如何让链表节点拥有数组的连续内存”或者“如何让数组像链表一样支持任意位置撕裂和重组”。等你能想到这一层基本就不会在结构选型上翻车了。
