第一部分：基本原理：两种数据结构的故事

在计算机科学领域，数组和链表是两种最基础的线性数据结构。它们在逻辑上都用于存储元素序列，但在物理实现和性能特征上存在根本性的差异。要理解它们在现代计算环境中的地位，首先必须掌握其经典定义和理论上的权衡。

1.1 数组：连续性与索引访问的力量

数组（Array）是由相同类型的元素组成的数据结构，每个元素都由一个或多个索引来标识。其最核心的特征是所有元素都存储在连续的内存地址中 ¹。

• 内存分配：无论是编译时在栈（Stack）上分配的局部数组，还是运行时在堆（Heap）上分配的动态数组，其内存块始终是连续的 ⁴。这种分配方式意味着一旦数组被创建，其占用的内存空间就像一条完整的、未中断的街道。

• 索引访问：连续性布局赋予了数组最显著的优势：常数时间复杂度的随机访问，即 O(1)。任何元素的内存地址都可以通过一个简单的数学公式直接计算得出：Address(A[i]) = BaseAddress + i * ElementSize ²。这使得访问数组中的任何元素（无论是第一个、最后一个还是中间的任意一个）都具有极高的效率和可预测性 ⁷。

• 大小调整：传统数组的大小在创建时是固定的。现代编程语言中广泛使用的动态数组（如 C++ 的 std::vector 或 Java 的 ArrayList）通过一种巧妙的机制解决了这个问题。当容量不足时，它们会重新分配一个更大的连续内存块，并将所有旧元素复制到新位置。这个过程在最坏情况下是 O(n) 操作，但由于容量通常是成倍增加，因此在尾部添加元素的平均（摊销）时间复杂度为 O(1) ⁹。

1.2 链表：动态节点与指针的灵活性

链表（Linked List）是另一种线性数据结构，但其元素的逻辑顺序并非由它们在内存中的物理位置决定。相反，链表由一系列节点（Node）组成，每个节点包含数据以及一个指向序列中下一个节点的指针（Pointer）或引用 ¹。

• 内存分配：链表的节点存储在非连续的内存位置，通常在需要时从堆中动态分配 ⁴。这种“随用随取”的模式提供了极大的灵活性，使得链表可以逐个元素地增长或收缩，而无需寻找一大块连续的可用内存 ¹。

• 内存开销：这种灵活性是有代价的，即内存开销。每个节点除了存储实际数据外，还必须为指针分配额外的空间（对于单向链表是一个指针，对于双向链表是两个）。这种开销对于存储较小数据类型的元素时尤其显著 ¹。

• 遍历访问：由于其非连续和指针链接的特性，无法通过索引直接计算出元素的地址。访问第 n 个元素必须从链表的头部开始，沿着指针逐个节点地遍历，直到到达目标位置。这导致其访问时间复杂度为 O(n) ¹。

1.3 经典比较：渐进复杂度和理论权衡

从纯粹的算法理论（大O表示法）来看，数组和链表的选择似乎是一个简单的权衡。

• 插入与删除：这是链表经典的理论优势所在。

• 数组：在数组的开头或中间插入/删除元素，需要移动后续所有元素来填补或腾出空间，这是一个 O(n) 的操作 ¹。

• 链表：如果已经持有一个指向目标位置前一个节点的指针，那么插入和删除操作的时间复杂度为 O(1)。这仅仅需要修改几个指针的指向，而无需移动大量数据 ¹。然而，这个
  O(1) 的前提至关重要。如果首先需要通过索引或值找到该位置，那么整个操作的复杂度将由 O(n) 的搜索/遍历过程主导。因此，一个完整的“在索引k处插入”操作的真实成本是 O(k)+O(1)，在一般情况下简化为 O(n) ¹¹。

• 搜索：对于一个未排序的集合，两者都需要进行线性扫描，时间复杂度均为 O(n) 。但如果数组是排序的，它可以利用二分搜索实现 O(logn) 的性能，而链表由于缺乏随机访问能力，无法进行二分搜索 ¹。

• 空间复杂度：两者存储 n 个元素的空间复杂度都是 O(n)。但链表的常数因子更高，因为它需要为每个节点的指针支付额外的内存开销 。

下表总结了基于经典计算机科学理论的性能对比。

这个经典的视角描绘了一个清晰的画面：数组为快速访问而优化，链表为灵活修改而优化。然而，这个画面在现代计算机硬件的强光下，开始变得模糊甚至失真。

第二部分：架构的命令：为何现代硬件重写规则

经典的大O分析发生在一个抽象的计算模型中，该模型假设所有内存访问的成本是均等的。然而，在现代计算机中，这个假设早已被打破。CPU与主存之间巨大的性能鸿沟，以及为弥补这一鸿沟而设计的复杂缓存系统，已经成为决定数据结构实际性能的主导因素。

2.1 CPU-内存性能鸿沟与存储器层次结构

现代CPU的运行速度比主存（DRAM）快几个数量级 ²⁰。如果CPU每次都需要等待数据从主存中获取，它将浪费成百上千个时钟周期，这构成了现代计算的核心瓶颈 ²⁰。为了解决这个问题，计算机体系结构引入了

存储器层次结构（Memory Hierarchy）。其核心思想是在高速的CPU和低速的主存之间，放置一系列容量更小但速度极快的存储器，即CPU缓存（CPU Cache）²²。

2.2 CPU缓存入门：L1、L2、L3与缓存行

• 缓存级别：CPU缓存通常分为多个级别（L1, L2, L3）。L1缓存最小、最快，紧邻CPU核心；L2缓存次之；L3缓存最大、最慢，通常由多个核心共享 ²²。

• 延迟：访问L1缓存可能只需约1-4个时钟周期，而访问主存则可能需要100-300个周期 ²⁴。当CPU需要的数据在缓存中时，称为
  缓存命中（Cache Hit），这是一个极快的操作。反之，如果数据不在缓存中，必须从更慢的存储层（如下一级缓存或主存）获取，则称为缓存未命中（Cache Miss），这是一个代价极高的操作 ²²。

• 缓存行：数据在主存和缓存之间的传输单位不是字节，而是固定大小的块，称为缓存行（Cache Line），在现代CPU中通常为64字节 ²³。当程序请求内存中的一个字节时，包含该字节的整个64字节缓存行都会被加载到缓存中 ²⁹。

2.3 局部性原理：缓存性能的关键

CPU缓存之所以高效，是因为程序通常表现出局部性原理（Principle of Locality），它有两种形式 ²⁹：

• 时间局部性 (Temporal Locality)：如果一个内存位置被访问，那么它在不久的将来很可能被再次访问。缓存通过保留最近访问过的数据来利用这一点 ³²。循环是时间局部性的典型例子 ²⁹。

• 空间局部性 (Spatial Locality)：如果一个内存位置被访问，那么它附近的内存位置也很可能在不久的将来被访问。缓存通过加载整个缓存行来利用这一点：获取一个字节的同时，也预取了其相邻的数据 ²⁹。遍历数组是空间局部性的典范 ²⁶。

2.4 性能再评估：数组作为天生的缓存友好结构

数组的连续内存布局与空间局部性原理完美契合 ¹。当程序访问

array 时，一个包含 array, array, array,... 等多个元素的缓存行被一次性加载到缓存中 ⁵。因此，对

array, array 的后续访问将成为极速的缓存命中。更重要的是，CPU的硬件预取器（Prefetcher）能够轻松识别这种线性的、可预测的访问模式，并提前将后续的缓存行加载到缓存中，从而有效地隐藏了访问主存的延迟 ²⁰。这使得对数组的顺序遍历成为现代硬件上最高效的操作之一 ¹⁶。

2.5 链表的真实成本：缓存未命中与指针追逐瓶颈

与数组相反，链表节点的非连续性彻底破坏了空间局部性 ⁴。节点

i 和节点 i+1 可能位于内存中相隔甚远的两个随机位置 ³⁵。为了从当前节点移动到下一个节点，CPU必须首先加载当前节点的数据，以读取其中存储的下一个节点的地址。这个过程被称为

指针追逐（Pointer Chasing）²¹。

这种操作模式对性能是毁灭性的，其深层原因在于它引入了固有的串行依赖 ³⁷。

1. 要获取节点 i+1 的地址，CPU 必须 等待对节点 i 的内存访问完成。

2. 在现代CPU能够并行执行多条指令的背景下，这种依赖性形成了一个无法并行的瓶颈：对 load(node_i+1) 的请求必须等待 load(node_i) 的结果。

3. 这导致CPU的指令流水线频繁停顿，硬件预取器也因无法预测下一个随机的内存地址而失效 ²¹。

4. 结果是，遍历链表的每一步都有极高的概率导致缓存未命中，迫使CPU进行一次缓慢的主存访问，其巨大的延迟无法被隐藏 ¹¹。

一个理论上 O(n) 的数组插入操作，虽然需要移动大量元素，但这个移动过程是线性的、可预测的，可以充分利用缓存和硬件预取。而一个理论上 O(1) 的链表插入操作，如果需要先遍历 n 个节点来定位，那么这 n 次“指针追逐”所带来的缓存未命中惩罚，其总成本可能远远超过数组移动元素的成本 ²⁰。

结论是明确的：在现代硬件上，对于涉及数据遍历的通用场景，数据结构的缓存友好度远比其渐进复杂度更能决定实际性能。数组的内存局部性使其天然地与现代CPU架构协同工作，而链表的内存分散性则使其与硬件的优化机制背道而驰。

第三部分：链表的持久生命力：在特定领域的至高地位

尽管在通用遍历性能上存在巨大劣势，但这并不意味着链表已经过时。恰恰相反，在某些特定且关键的领域，链表的独特属性——例如稳定的指针、在持有引用时真正的 O(1) 修改能力、以及内存分配与插入操作的解耦——不仅是有益的，甚至是不可或替代的。链表的价值从追求原始速度转向了提供更高级的结构性保障。

3.1 系统编程深潜：Linux内核中的侵入式链表

在操作系统内核这样的底层环境中，数据结构（如代表进程的 task_struct）非常复杂，并且会被系统的多个不同部分引用。在这种情况下，使用动态数组是不可行的，因为任何大小调整操作都会移动内存中的所有元素，这将导致内核中无数指向这些元素的指针失效，从而引发系统崩溃 ⁹。

为了解决这个问题，Linux内核采用了一种名为侵入式链表（Intrusive Linked List）的精妙实现 ⁴⁰。

• 核心思想：与常规链表（节点包含一个指向数据的指针）不同，侵入式链表将链表节点（即 next 和 prev 指针，在Linux中为 struct list_head）直接嵌入到数据结构本身 ⁴⁰。

• 关键优势：

1. 稳定的地址：一个对象（如一个 task_struct）的内存地址在其整个生命周期内都是固定的。它可以被添加到链表或从链表中移除，而其自身的内存位置绝不会改变。这对于维护系统各处指针的有效性至关重要。

2. 无额外内存分配：向链表中添加或移除一个已存在的对象，仅需修改指针，完全不需要在操作期间进行任何内存分配 ³⁹。这在内核的某些关键路径（如中断处理或持有自旋锁时）是强制性要求，因为在这些上下文中进行可能休眠的内存分配是被禁止的 ⁴⁴。

3. 多重隶属关系：通过在数据结构中嵌入多个 list_head 成员，同一个对象可以同时属于多个不同的链表，极大地增强了数据组织的灵活性 ⁴²。

应用实例：Linux内核广泛使用侵入式链表来管理任务列表（所有 task_struct 构成的链表）、内存管理中的空闲页块列表（伙伴系统和SLAB分配器）、以及各种设备驱动列表等 ⁴¹。在这些场景中，指针的稳定性和可预测的、无分配的修改操作，其重要性远远超过了快速遍历整个列表的需求。

3.2 并发与并行：无锁链表的作用

在多线程编程中，保护共享数据结构通常依赖于锁（Lock）。然而，锁会带来性能开销、死锁风险以及可组合性差等问题 ⁵⁰。如果一个线程持有锁并被意外延迟，所有其他需要该锁的线程都将被阻塞 ⁵¹。

无锁（Lock-Free）数据结构提供了一种替代方案。无锁链表利用硬件提供的原子指令，如比较并交换（Compare-and-Swap, CAS），来实现并发的插入和删除，而无需使用互斥锁 ⁵²。

• CAS操作原理：以插入为例，一个线程想要在节点 p 之后插入新节点 n。它首先读取 p->next 的当前值（设为 old_next），然后让 n->next 指向 old_next。最后，它执行一个CAS操作，原子地尝试将 p->next 的值从 old_next 更新为 n。这个CAS操作只有在 p->next 的值仍然是 old_next 时才会成功。如果在此期间有其他线程修改了 p->next，CAS操作就会失败，当前线程则需要重试整个过程 ⁵²。

• 为何选择链表：链表操作的局部化特性——即修改通常只涉及一两个指针——使其非常适合像CAS这样的原子操作。相比之下，在数组中无锁地插入一个元素要复杂得多，因为它需要原子地移动大块内存。

3.3 函数式与不可变范式：持久化链表与结构共享

在函数式编程中，数据结构通常是不可变的（Immutable）。当你“修改”一个数据结构时，实际上是创建了一个新的版本，同时保留了旧版本。这种特性被称为持久化（Persistence）⁵⁴。

链表是实现持久化数据结构的理想选择，其关键在于结构共享（Structural Sharing）⁵⁵。

• 工作方式：要在一个链表 L 的头部添加一个新元素，你只需创建一个新的头节点，让它的 next 指针指向 L 的原始头节点。整个原始链表 L 保持原封不动。

• 效率：现在，新旧两个链表共享了除新头节点外的所有节点。这种方式在内存上极为高效，避免了为每次修改都复制整个数据结构 ⁵⁶。

• 与数组对比：如果用数组实现同样的功能，每次修改都必须完整复制整个数组，成本极高 ⁵⁵。链表的节点化结构是实现高效结构共享的基础，这也是它在Haskell、ML等函数式语言中成为核心数据结构的原因 ⁵⁵。

3.4 作为基础构件：哈希表中的链式法

哈希表（Hash Table）通过哈希函数将键（Key）映射到数组的索引上。然而，不同的键可能会被映射到同一个索引，这便产生了哈希冲突（Collision）⁵⁹。

解决冲突的一种常见且简单的方法是链式法（Separate Chaining）。在这种方法中，哈希表的每个数组槽位并不直接存储元素，而是存储一个指向链表的指针。所有哈希到同一个索引的键值对都被存储在这个链表中 ⁵⁹。链表是此处的自然选择，因为每个桶（bucket）中的冲突数量是不可预知且动态变化的，链表可以根据需要灵活地增长 ⁶¹。

3.5 分布式系统中的概念相似性：区块链

区块链（Blockchain）在概念上可以被视为一个链表。每个区块（Block）包含数据（如交易记录）和前一个区块的加密哈希值 ⁶³。这个“前块哈希”扮演了指针的角色，将所有区块按时间顺序链接在一起，形成一个可验证的链条 ⁶⁶。

尽管结构上相似，但区块链与简单链表有本质区别。区块链是不可变的、去中心化的，并通过密码学和共识算法保证安全，而不仅仅是简单的内存指针 ⁶³。链表为区块链提供了基础的“链接”概念，但整个系统在此之上增加了复杂的安全和分布式特性。

总而言之，链表的“缺点”——其节点在内存中是独立、解耦的实体——在特定的高级应用场景中，反而成为了它最大的“优点”。其价值体现在它所支持的结构特性上，这些特性使得更健壮、灵活和安全的编程范式（如系统管理、并发编程、函数式编程）成为可能。

第四部分：前行之路：链接结构的演进与未来

面对现代硬件带来的性能挑战，链表并没有停滞不前。它的核心思想正在通过各种方式进行调整和演进，以克服其固有的性能瓶颈。未来不属于单一的“更好的链表”，而是一个由混合结构和高级替代方案组成的“工具箱”。

4.1 混合动力：融合数组与链表的优势

既然数组缓存友好而链表修改灵活，一个自然的发展方向就是将两者结合，取长补短。

4.1.1 展开链表：一种缓存友好的折衷方案

展开链表（Unrolled Linked List）是一种变体，其每个节点不再只包含单个元素，而是包含一个小型的元素数组 ⁶⁸。这个内部数组的大小通常被精心选择，以使其恰好能装入一个或少数几个CPU缓存行 ⁶⁸。

• 工作原理：遍历这种链表时，大部分时间是在节点内部的连续数组中进行迭代，这是一个非常缓存友好的操作。只有当一个节点的内部数组遍历完后，才需要进行一次指针追逐，跳转到下一个节点 ⁶⁹。

• 优势：这种设计极大地减少了指针追逐的次数和缓存未命中的频率。同时，由于每个指针的开销被分摊到了节点内的所有元素上，内存开销也显著降低 ⁶⁸。它在保留了大部分插入/删除灵活性的同时，为遍历操作带来了巨大的性能提升 ⁷¹。

4.1.2 其他混合模型：数组列表与数组实现的链表

• 数组列表：与展开链表类似，可以实现一个由多个数组（或 std::vector）组成的链表。这对于管理动态增长的数据非常有效，其中每个数据块内部可以进行高效的顺序处理 ⁷²。

• 数组实现的链表：一个更有趣的逆向思维是在一个大的连续数组内部实现链表的逻辑。在这种结构中，节点的“next”字段不再是内存地址指针，而是下一个元素在该数组中的索引 ³⁷。这种方法保证了所有节点都位于同一个连续内存块中，从而获得了完美的缓存局部性。同时，它仍然允许通过修改索引来进行逻辑上的
  O(1) 重新链接（通过维护一个数组内未使用的索引的“空闲列表”来实现）。这种技术在内存分配受限的环境（如某些嵌入式系统）中尤为有用。

4.2 概率的力量：跳表作为高性能的平衡树替代品

排序数组虽然支持 O(logn) 的二分搜索，但其插入操作是 O(n)。平衡二叉搜索树（如红黑树）为搜索、插入和删除提供了 O(logn) 的性能，但其平衡逻辑复杂，且在并发场景下需要复杂的锁机制。

跳表（Skip List）提供了一个优雅的替代方案。它是一种基于有序链表的概率性数据结构，通过在基础链表之上构建多个“快车道”（包含较少元素的更高层级链表）来实现高效搜索 ⁷⁴。

• 工作原理：搜索从最高、最稀疏的层级开始。指针向前移动，直到将要越过目标元素时，便下降到下一层更详细的链表，重复此过程。这使得搜索可以快速“跳跃”到列表的正确区域 ⁷⁷。

• 性能：通过随机化的方式决定一个节点应该存在于哪些层级，跳表在期望上可以达到 O(logn) 的搜索、插入和删除性能，与平衡树相当，但通常实现更简单，且具有更好的并发特性 ⁷⁸。

4.3 迈向架构无关性：缓存无关设计的愿景

缓存无关算法（Cache-Oblivious Algorithms）旨在设计出在任何存储器层次结构上都能表现良好，而无需知道具体的硬件参数（如缓存大小或缓存行大小）的算法 ²⁴。

在链表领域的应用，这通常涉及以特殊方式组织节点的内存布局（例如，使用递归的van Emde Boas布局），使得对任意大小为 k 的子列表的遍历都能接触到最少数量的缓存块，无论缓存块的实际大小 B 是多少。这是一个前沿的研究领域，其目标是创造可移植的高性能数据结构 ⁸⁰。

链表的演进揭示了高性能计算的一个基本趋势：通过增加算法和实现的复杂性，来换取对硬件资源的更优利用。简单的链表在算法上是微不足道的，但展开链表、跳表和缓存无关链表则要求程序员承担更多关于数据布局的责任。这种从追求算法简洁到追求硬件协同的转变，标志着数据结构设计的成熟。

第五部分：结论与现代程序员的战略建议

对数组和链表的深入研究表明，经典的“访问快用数组，增删快用链表”的二元对立观点在现代计算机体系结构下已经过于简化。实际性能更多地取决于数据访问模式与CPU缓存机制的交互。链表并未被淘汰，而是其适用场景变得更加专业化和高层次化。它的未来在于与数组思想的融合以及在特定编程范式（如并发、函数式、系统级）中发挥其独特的结构优势。

5.1 决策框架：何时选择数组、链表或其替代方案

对于现代开发者而言，选择正确的数据结构需要一个超越大O复杂度的、更具情境意识的决策框架。以下启发式指南旨在提供一个实用的决策流程。

5.2 未来是混合的：数据结构设计的展望

对于性能敏感的应用，在简单的数组和链表之间进行选择的时代正在结束。未来属于体系结构感知的数据结构：结合了二者优点的混合结构（如展开链表）、利用概率提升性能的结构（如跳表），以及为特定领域高度优化的实现（如侵入式链表、无锁链表）。

现代程序员的责任已从仅仅理解抽象的算法复杂度，扩展到理解代码如何与存储器层次结构互动。最有效的数据结构将不再是那些在理论真空中设计的，而是那些与其运行的硬件形成共生关系的结构。

Works cited

1. www.wscubetech.com, accessed June 21, 2025, https://www.wscubetech.com/resources/dsa/array-vs-linked-list

2. Linked List vs Array - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/linked-list-vs-array/

3. What is the Difference Between Array and Linked List? - Great Learning, accessed June 21, 2025, https://www.mygreatlearning.com/blog/what-is-the-difference-between-array-and-linked-list/

4. A Programmer's approach of looking at Array vs. Linked List - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/programmers-approach-looking-array-vs-linked-list/

5. Differences Between Array and Linked List - ScholarHat, accessed June 21, 2025, https://www.scholarhat.com/tutorial/datastructures/differences-between-arrays-and-linked-lists

6. Difference Between Array & Linked List in Data Structure - Simplilearn.com, accessed June 21, 2025, https://www.simplilearn.com/tutorials/data-structure-tutorial/difference-between-array-and-linked-list-in-data-structure

7. Array vs. Linked List - HappyCoders.eu, accessed June 21, 2025, https://www.happycoders.eu/algorithms/array-vs-linked-list/

8. Linked Lists vs. Arrays: When and Why to Use Each Data Structure - AlgoCademy, accessed June 21, 2025, https://algocademy.com/blog/linked-lists-vs-arrays-when-and-why-to-use-each-data-structure/

9. Array Vs Linked list : r/C_Programming - Reddit, accessed June 21, 2025, https://www.reddit.com/r/C_Programming/comments/146npoq/array_vs_linked_list/

10. Fundamental Data Structures: Linked Lists - Vega IT, accessed June 21, 2025, https://www.vegaitglobal.com/media-center/knowledge-base/fundamental-data-structures-linked-lists

11. Arrays vs. Linked Lists: Key Differences & Use Cases - The Coder Cafe, accessed June 21, 2025, https://www.thecoder.cafe/p/arrays-vs-linked-lists

12. Difference Between Array and Linked List - Tutorialspoint, accessed June 21, 2025, https://www.tutorialspoint.com/difference-between-array-and-linked-list

13. Understanding Memory Allocation in Linked Lists: How Nodes and Addresses Connect, accessed June 21, 2025, https://youcademy.org/memory-allocation-in-linked-lists/

14. Linked Lists vs Arrays - Advantages and Disadvantages - Youcademy, accessed June 21, 2025, https://youcademy.org/linked-list-vs-array/

15. How much memory is used when allocating an array vs allocating an linked list in Java?, accessed June 21, 2025, https://stackoverflow.com/questions/19322173/how-much-memory-is-used-when-allocating-an-array-vs-allocating-an-linked-list-in

16. Time complexity of sequentially scanning an array vs a linked list? - Stack Overflow, accessed June 21, 2025, https://stackoverflow.com/questions/64720646/time-complexity-of-sequentially-scanning-an-array-vs-a-linked-list

17. When to use Array over Linked List and vice versa? - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/when-to-use-array-over-linked-list-and-vice-versa/

18. Time and Space Complexity of Linked List - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/time-and-space-complexity-of-linked-list/

19. What is the advantage of linked list over an array and vice versa? - Stack Overflow, accessed June 21, 2025, https://stackoverflow.com/questions/7496251/what-is-the-advantage-of-linked-list-over-an-array-and-vice-versa

20. Performance of Array vs. Linked-List on Modern Computers - DZone, accessed June 21, 2025, https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp

21. Memory Latency - Algorithmica, accessed June 21, 2025, https://en.algorithmica.org/hpc/cpu-cache/latency/

22. How Does CPU Cache Work and What Are L1, L2, and L3 Cache? - MakeUseOf, accessed June 21, 2025, https://www.makeuseof.com/tag/what-is-cpu-cache/

23. CPU cache - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/CPU_cache

24. Cache-Friendly Algorithms and Data Structures: Optimizing Performance Through Efficient Memory Access - AlgoCademy, accessed June 21, 2025, https://algocademy.com/blog/cache-friendly-algorithms-and-data-structures-optimizing-performance-through-efficient-memory-access/

25. CPU Cache Basics - DEV Community, accessed June 21, 2025, https://dev.to/larapulse/cpu-cache-basics-57ej

26. Memory Layout And Cache Optimization For Arrays - HeyCoach | Blogs, accessed June 21, 2025, https://blog.heycoach.in/memory-layout-and-cache-optimization-for-arrays/

27. CPU performance - CuriousCoding, accessed June 21, 2025, https://curiouscoding.nl/posts/cpu-benchmarks/

28. Cache-Friendly Code | Baeldung on Computer Science, accessed June 21, 2025, https://www.baeldung.com/cs/cache-friendly-code

29. Cache introduction - Washington, accessed June 21, 2025, https://courses.cs.washington.edu/courses/cse378/10sp/lectures/lec16.pdf

30. Locality of reference - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Locality_of_reference

31. Locality of Reference and Cache Operation in Cache Memory - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/locality-of-reference-and-cache-operation-in-cache-memory/

32. 2: Principle of Locality, accessed June 21, 2025, https://www.cs.fsu.edu/~hawkes/cda3101lects/chap7/locality.htm

33. Difference Between Spatial Locality and Temporal Locality - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/difference-between-spatial-locality-and-temporal-locality/

34. Why does cache locality matter for array performance? - Stack Overflow, accessed June 21, 2025, https://stackoverflow.com/questions/12065774/why-does-cache-locality-matter-for-array-performance

35. Yeah, linked lists are bad for the data cache since each element is in some tota, accessed June 21, 2025, https://news.ycombinator.com/item?id=25271996

36. A Study of Pointer-Chasing Performance on Shared-Memory Processor-FPGA Systems - Electrical and Computer Engineering, accessed June 21, 2025, https://users.ece.cmu.edu/~jhoe/distribution/2016/fpga16.pdf

37. CPU Cache disadvantages of using linked lists in C - Stack Overflow, accessed June 21, 2025, https://stackoverflow.com/questions/40071635/cpu-cache-disadvantages-of-using-linked-lists-in-c

38. Accelerating Pointer Chasing in 3D-Stacked Memory: Challenges, Mechanisms, Evaluation - Ethz, accessed June 21, 2025, https://people.inf.ethz.ch/omutlu/pub/in-memory-pointer-chasing-accelerator_iccd16.pdf

39. Why would one ever prefer a linked list over a dynamic array? I know about the a... | Hacker News, accessed June 21, 2025, https://news.ycombinator.com/item?id=14182922

40. Doubly linked list · Linux Inside - 0xax, accessed June 21, 2025, https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-1.html

41. Intrusive linked lists - Data structures in practice, accessed June 21, 2025, https://www.data-structures-in-practice.com/intrusive-linked-lists/

42. The Linux kernel uses intrusive linked lists extensively. Container based linked... | Hacker News, accessed June 21, 2025, https://news.ycombinator.com/item?id=13263640

43. The Linux Kernel's Implementation - The Linked-List Structure - Litux, accessed June 21, 2025, https://litux.nl/mirror/kerneldevelopment/0672327201/app01lev1sec2.html

44. Arc in the Linux kernel, accessed June 21, 2025, https://rust-for-linux.com/arc-in-the-linux-kernel

45. Advantages of linked lists over arrays? - Computer Science Stack Exchange, accessed June 21, 2025, https://cs.stackexchange.com/questions/151505/advantages-of-linked-lists-over-arrays

46. Kernel task_struct | Alex XU, accessed June 21, 2025, https://alex-xjk.github.io/post/taskstruct/

47. Linux kernel threads and processes management : task_struct - cylab.be, accessed June 21, 2025, https://cylab.be/blog/347/linux-kernel-threads-and-processes-management-task-struct

48. Memory Management — The Linux Kernel documentation, accessed June 21, 2025, https://linux-kernel-labs.github.io/refs/heads/master/lectures/memory-management.html

49. Demystifying Linked Lists in the Linux Kernel - irenge blog, accessed June 21, 2025, https://julesbashizi.wordpress.com/2024/03/08/demystifying-linked-lists-in-the-linux-kernel/

50. Parallel linked lists - Page has been moved, accessed June 21, 2025, https://www.cse.chalmers.se/edu/course/TDA384_LP3/files/lectures/Lecture10-parallel_lists.pdf

51. Fine-grained synchronization & lock-free programming, accessed June 21, 2025, https://www.cs.cmu.edu/afs/cs/academic/class/15418-f18/www/lectures/17_lockfree.pdf

52. Non-blocking linked list - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Non-blocking_linked_list

53. Lock-Free Linked Lists Using Compare-and-Swap - liblfds.org, accessed June 21, 2025, https://www.liblfds.org/downloads/white%20papers/%5BLinked%20List%5D%20-%20%5BValois%5D%20-%20Lock-Free%20Linked%20Lists%20Using%20Compare-and-Swap.pdf

54. Persistent data structures - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/persistent-data-structures/

55. Persistent data structure - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Persistent_data_structure

56. Persistent data structures in functional programming - SoftwareMill, accessed June 21, 2025, https://softwaremill.com/persistent-data-structures-in-functional-programming/

57. How does a persistent data structure in functional programming work? - Quora, accessed June 21, 2025, https://www.quora.com/How-does-a-persistent-data-structure-in-functional-programming-work

58. How do data structures work in functional programming? : r/functionalprogramming - Reddit, accessed June 21, 2025, https://www.reddit.com/r/functionalprogramming/comments/zrpu6e/how_do_data_structures_work_in_functional/

59. Hash table - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Hash_table

60. Collision Resolution Techniques - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/collision-resolution-techniques/

61. 8.1. Description of Chained Hash Tables - Mastering Algorithms with C [Book], accessed June 21, 2025, https://www.oreilly.com/library/view/mastering-algorithms-with/1565924533/ch08s01.html

62. Separate Chaining Collision Handling Technique in Hashing - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/separate-chaining-collision-handling-technique-in-hashing/

63. Applications of linked lists in blockchain data structures - Educative.io, accessed June 21, 2025, https://www.educative.io/answers/applications-of-linked-lists-in-blockchain-data-structures

64. Understanding Blockchain Data Structure: A Comprehensive Guide - Metaschool, accessed June 21, 2025, https://metaschool.so/articles/blockchain-data-structure

65. Blockchain Facts: What Is It, How It Works, and How It Can Be Used - Investopedia, accessed June 21, 2025, https://www.investopedia.com/terms/b/blockchain.asp

66. Blockchain Technology and Distributed Systems | GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/blockchain-technology-and-distributed-systems/

67. How is Blockchain Different From a Linked List? - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/how-is-blockchain-different-from-a-linked-list/

68. Unrolled linked list - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Unrolled_linked_list

69. Unrolled Linked List | Brilliant Math & Science Wiki, accessed June 21, 2025, https://brilliant.org/wiki/unrolled-linked-list/

70. Insertion in Unrolled Linked List - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/insertion-unrolled-linked-list/

71. The quest for the fastest linked list - Johnny's Software Lab, accessed June 21, 2025, https://johnnysswlab.com/the-quest-for-the-fastest-linked-list/

72. Why Linked Lists vs Arrays isn't a real choice - YouTube, accessed June 21, 2025, https://www.youtube.com/watch?v=34ky600VTN0

73. Can linked list be implemented using arrays? As you can see in this resource said Yes and if you scroll down someone commented on this post said No. So any ideas on this question, pls? : r/computerscience - Reddit, accessed June 21, 2025, https://www.reddit.com/r/computerscience/comments/w6o6lk/can_linked_list_be_implemented_using_arrays_as/

74. www.geeksforgeeks.org, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/skip-list/#:~:text=In%20a%20skip%20list%2C%20elements,apart%20in%20the%20bottom%20layer.

75. Skip List | Brilliant Math & Science Wiki, accessed June 21, 2025, https://brilliant.org/wiki/skip-lists/

76. Skip List - Efficient Search, Insert and Delete in Linked List - GeeksforGeeks, accessed June 21, 2025, https://www.geeksforgeeks.org/dsa/skip-list/

77. Skip list - Wikipedia, accessed June 21, 2025, https://en.wikipedia.org/wiki/Skip_list

78. Skip Lists, accessed June 21, 2025, https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/skiplists.pdf

79. Skip Lists: A Probabilistic Alternative to Balanced Trees, accessed June 21, 2025, https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf

80. The Ultimate Guide to Linked Lists in Cache-Oblivious Computing - Number Analytics, accessed June 21, 2025, https://www.numberanalytics.com/blog/ultimate-guide-to-linked-lists-in-cache-oblivious-computing