两种截然不同的存储艺术。 数组如同规整划一的连续街区，地址相连，寻址便捷； 而链表则像散落各处却彼此相牵的珠串，灵活生长，处处皆可安家。

数组常用操作

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。下图展示了数组的主要概念和存储方式。

初始化数组

可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为0：

var arr [5]int

/*
在Go中，指定长度时（[5]int）为数组，不指定长度（[]int）为切片
犹豫Go的数组被设计成编译器期确定长度，因此只能使用常量来指定长度
为了方便实现扩容 extend()方法，以下将切片(Slice)看做数组(Array)
*/
nums := []int{1,3,2,5,4}

访问元素

数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引，我们可以使用图中所示的公式计算得到该元素的内存地址，从而直接访问该元素。

首个元素的索引为0，这似乎有些反直觉，因为从1开始计数会更自然。但从地址计算公式的角度看，索引本质上是内存地址的偏移量。首个元素的地址偏移量是0，因此它的索引为0是合理的。

在数组中访问元素非常高效，我们可以在$O(1)$时间内随机访问数组中的任意一个元素。

// 随机访问元素
func randomAccess(nums []int) (randomNum int){
  // 在区间[0, nums.length) 前开后闭，包含头不包含尾。中随机取一个数字
  randomIndex := rand.Intn(len(nums))
  // 获取并返回随机元素
  randomNum = nums[randomIndex]
  return
}

插入元素

数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。

值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个问题的解决方案留在“列表”章节中讨论。

// 在数组的索引index处插入元素num
func insert(nums []int, num int, index int){
  // 把索引index以及之后的所有元素向后移动一位
  for i:=len(nums)-1; i>index; i--{
    nums[i]=nums[i-1]
  }
  // 将num赋给index处的元素
  nums[index]=num
}

删除元素

同理，若想删除索引 $i$ 处的元素，则需要把索引 $i$ 之后的元素都向前移动一位。

请注意，删除元素完成后，原先末尾的元素变得“无意义”了，所以我们无须特意去修改它。

// 删除索引index处的元素
func remove(nums []int, index int){
  // 把索引index之后的所有元素向前移动一位
  for i:=index; i<len(nums)-1 ;i++{
    nums[i] = nums[i+1]
  }
}

总的来看，数组的插入与删除操作有以下缺点。

时间复杂度高：数组的插入和删除的平均时间复杂度均为$O(n)$，其中$n$为数组长度。 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。

遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素：

// 遍历数组
func traverse(nums []int){
  count := 0
  // 通过索引遍历数组
  for i:=0; i<len(nums); i++{
    count += nums[i]
  }
  count = 0
  // 直接遍历数组元素
  for _, num := range nums{
    count += num
  }
  // 同时遍历索引和元素
  for i, num := range nums{
    count += nums[i]
    count += num
  }
}

查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。

因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

// 在数组中查找指定元素
func find(nums []int, target int) (index int){
  index := -1
  for i:=0; i<len(nums); i++{
    if nums[i] == target{
      index = i
      break
    }
  }
  return
}

扩容数组

在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。

如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个 $O(n)$的操作，在数组很大的情况下非常耗时。代码如下所示：

// 扩展数组长度
func extend(nums []int, enlarge int) []int {
  // 初始化一个扩展长度后的数组
  res := make([]int, len(nums)+enlarge)
  // 将原数组中的所有元素复制到新数组
  for i, num := range nums{
    res[i] = num
  }
  // 返回扩展后的新数组
  return res
}

数组的优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

• 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
• 支持随机访问：数组允许在$O(1)$时间内访问任何元素。
• 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下局限性。

• 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
• 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
• 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

数组典型应用

数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。

• 随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
• 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
• 查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。
• 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
• 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

链表常用操作

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。

• 链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。
• 尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为 null、nullptr 和 None 。
• 在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。

如以下代码所示，链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

// 链表节点结构体
type ListNode struct{
  Val int // 节点值
  Next *ListNode // 指向下一个节点的指针
}

// NewListNode构造函数，创建一个新的链表
func NewListNode(val int) *ListNode {
  return &ListNode{
    Val: val,
    Next: nil,
  }
}

初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建节点之间的引用关系。初始化完成后，就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

// 初始化链表 1->3->2->5->4
// 初始化每个节点
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// 构建节点之间的引用
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4

数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可记作链表 $n0$ 。

插入节点

在链表中插入节点非常容易。如图所示，假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为$O(1)$。

相比之下，在数组中插入元素的时间复杂度为$O(n)$，在大数据量下的效率较低。

// 在链表的节点 n0 之后插入节点 P
func insertNode(n0 *ListNode, P *ListNode){
  // 先找到n0原临近节点n1
  n1 := n0.Next
  // 再把P指向n1
  P.next = n1
  // 再把n0指向P
  n0.Next = P
}

P.next = n1 和 n0.Next = P 顺序不能调换，应该先右后左。

删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

// 删除链表的节点 n0 之后的首个节点
func removeItem(n0 *ListNode){
  if n0.Next == nil {
    return 
  }
  // n0 -> P -> n1
  P := n0.Next
  n1 := P.Next
  n0.Next := n1
}

访问节点

在链表中访问节点的效率较低。我们可以在$O(1)$时间下访问数组中的任意元素。 链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 $i$ 个节点需要循环 $i-1$ 轮，时间复杂度为 $O(n)$。

// 访问链表中索引为index的节点
func access(head *ListNode, index int) *ListNode {
  for i := 0; i<index; i++{
    if head == nil {
      return nil
    }
    head = head.Next
  }
  return head
}

查找节点

遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。此过程也属于线性查找。

func findNode(head *ListNode, target int) int {
  index := 0
  for head != nil {
    if head.Val == target{
      return index
    }
    head = head.Next
    index++
  }
  return -1
}

数组 vs. 链表

总结了数组和链表的各项特点并对比了操作效率。由于它们采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。

常见链表类型

常见的链表类型包括三种。

• 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。

• 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

• 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

// 双向链表结构体
type DoublyListNode struct{
  Val int 
  Next *DoublyListNode
  Prev *DoublyListNode
}

// NewDoublyListNode初始化
func NewDoublyListNode(val int) *DoublyListNode{
  return &DoublyListNode{
    Val: val,
    Next: nil,
    Prev: nil,
  }
}

链表典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

• 栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
• 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
• 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

• 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
• 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
• LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

• 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
• 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

内存与缓存

• 探讨了数组和链表这两种基础且重要的数据结构，它们分别代表了“连续存储”和“分散存储”两种物理结构。
• 实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。

计算机存储设备

计算机中包括三种类型的存储设备：硬盘（hard disk）、内存（random-access memory, RAM）、缓存（cache memory）。表 4-2 展示了它们在计算机系统中的不同角色和性能特点。

计算机的存储层次结构体现了速度、容量和成本三者之间的精妙平衡。实际上，这种权衡普遍存在于所有工业领域，它要求我们在不同的优势和限制之间找到最佳平衡点。

如图 4-10 所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢的内存的依赖。

数据结构的内存效率

在内存空间利用方面，数组和链表各自具有优势和局限性。

一方面，内存是有限的，且同一块内存不能被多个程序共享，因此我们希望数据结构能够尽可能高效地利用空间。数组的元素紧密排列，不需要额外的空间来存储链表节点间的引用（指针），因此空间效率更高。然而，数组需要一次性分配足够的连续内存空间，这可能导致内存浪费，数组扩容也需要额外的时间和空间成本。相比之下，链表以“节点”为单位进行动态内存分配和回收，提供了更大的灵活性。

另一方面，在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。数组由于其连续的存储方式，相对不容易导致内存碎片化。相反，链表的元素是分散存储的，在频繁的插入与删除操作中，更容易导致内存碎片化。

数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。

显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。我们将 CPU 从缓存中成功获取数据的比例称为缓存命中率（cache hit rate），这个指标通常用来衡量缓存效率。

为了尽可能达到更高的效率，缓存会采取以下数据加载机制。

• 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
• 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
• 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
• 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。

实际上，数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面。

• 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。
• 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
• 预取机制：数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
• 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。

总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。这使得在解决算法问题时，基于数组实现的数据结构往往更受欢迎。

需要注意的是，高缓存效率并不意味着数组在所有情况下都优于链表。实际应用中选择哪种数据结构，应根据具体需求来决定。例如，数组和链表都可以实现“栈”数据结构（下一章会详细介绍），但它们适用于不同场景。

• 在做算法题时，我们会倾向于选择基于数组实现的栈，因为它提供了更高的操作效率和随机访问的能力，代价仅是需要预先为数组分配一定的内存空间。
• 如果数据量非常大、动态性很高、栈的预期大小难以估计，那么基于链表实现的栈更加合适。链表能够将大量数据分散存储于内存的不同部分，并且避免了数组扩容产生的额外开销。

版权所有

版权归属：Mars Chin

许可证：署名-非商业性 4.0 国际 (CC-BY-NC-4.0)