Part 2.1：数组与链表：相爱相杀的线性双雄

引言：两种不同的“排队”方式

欢迎来到数据结构的世界！在正式学习各种高级结构之前，我们必须先掌握两种最基础、最重要、也是面试中最高频的线性数据结构：数组 (Array) 和 **链表 (Linked List)**。

想象一下两种不同的“排队”场景：

  1. 看电影买票（数组）：所有人都紧挨着排成一队，队伍整齐划一。如果你想知道排在第 5 位的是谁，你一眼就能看到。但如果有人想插队到中间，后面所有人都得往后挪一步，非常麻烦。
  2. 寻宝游戏（链表）：你拿到第一张纸条（头节点），上面写着宝藏的位置和下一张纸条的藏匿点。你必须顺着线索一步步找下去。如果你想在中间增加一个寻宝环节，只需要修改前后两张纸条的线索即可，非常灵活。

这两种“排队”方式，生动地揭示了数组和链表的本质区别。它们是构建更复杂数据结构（如栈、队列、哈希表）的基石，理解它们的优劣和权衡，是算法内功修炼的第一步。

为什么数组和链表如此重要？

  • 面试价值：几乎 100% 的技术面试都会直接或间接地考察数组和链表。链表反转、环检测、双指针等都是经典面试题，它们能极好地考察你的指针操作能力和逻辑严谨性。
  • 学术与工程价值：数组是计算机内存布局的直接体现，理解它有助于你写出缓存友好（Cache-friendly）的高性能代码。链表则在需要频繁动态增删的场景中大放异彩，例如操作系统的任务调度队列、内存管理等。

本文将带你深入这两种结构的底层，通过原理剖析、图示、动画式案例和代码实战，让你彻底理解这对“相爱相杀”的线性双雄。

背景知识：线性表

在开始之前，我们需要明确一个概念：**线性表 (Linear List)**。

线性表是具有 相同特性 的数据元素的一个 有限序列。通俗地说，就是把一堆数据“排成一队”。

关键特征：

  • 序列：元素之间有前后顺序。
  • 有限：元素数量是有限的。
  • 同质：所有元素的数据类型相同。

数组和链表都是线性表的两种最主要的物理实现方式。它们用不同的存储策略来实现线性表的逻辑结构。

Part A：数组 (Array) - 秩序井然的内存公寓

1. 详细算法原理

直觉：一排带编号的连续公寓

你可以把数组想象成一栋公寓楼里的一整排房间，这些房间地址连续，并且每个房间都有一个唯一的门牌号（索引）。如果你知道基地址（公寓楼的入口）和门牌号，你可以瞬间“传送”到任何一个房间，而不需要挨个敲门询问。

严谨原理：连续的内存空间

在计算机内存中，数组是一块连续的、大小固定的内存空间。当我们声明一个数组时，计算机会预留出足够存放所有元素的连续内存。

正是因为“连续”这一特性，数组实现了高效的**随机访问 (Random Access)**。计算机可以通过一个简单的数学公式，直接计算出任何一个元素的内存地址：

address(arr[i]) = base_address + i * element_size

  • base_address：数组的起始内存地址。
  • i：元素的索引（门牌号）。
  • element_size：单个元素占用的内存大小（例如，一个 32 位整数占 4 字节）。

这个计算过程是一个常数时间操作，所以数组的访问时间复杂度是 O(1)。

2. 关键图示

数组在内存中的存储
数组元素在内存中是连续存放的，可以通过公式直接计算出地址

3. 步骤分解：核心操作分析

  • **访问 (Access)**：O(1)。如上所述，通过公式直接计算地址。
  • **查找 (Search)**：O(n)。如果要查找某个特定值的元素，需要从头到尾遍历数组，最坏情况下需要 n 次比较。
  • **插入 (Insert)**：O(n)。在数组中间或开头插入元素，需要将被插入位置之后的所有元素向后移动一位。
  • **删除 (Delete)**：O(n)。删除数组中间或开头的元素，需要将删除位置之后的所有元素向前移动一位。

4. 动画式案例：在数组中插入元素

场景：在一个动态数组 [10, 20, 40, 50] 的索引 2 处插入元素 30。

步骤变化：

  1. 初始状态: [10, 20, 40, 50]
  2. 移动元素 50: 为了给新元素腾出空间，将索引 3 的 50 移动到索引 4。
    [10, 20, 40, 50, 50]
  3. 移动元素 40: 将索引 2 的 40 移动到索引 3。
    [10, 20, 40, 40, 50]
  4. 插入新元素: 在索引 2 处放入 30。
    [10, 20, 30, 40, 50]
  5. 最终状态: [10, 20, 30, 40, 50]

这个“牵一发而动全身”的移动过程，正是数组插入和删除操作耗时的根源。

Part B：链表 (Linked List) - 灵活串联的节点火车

1. 详细算法原理

直觉：一节节独立的火车车厢

你可以把链表想象成一列火车，每一节车厢（节点）都是独立的，可以停放在铁路网的任何地方。每节车厢除了装载货物（数据），还有一个连接器（指针），指向下一节车厢的位置。火车的起点由一个特殊的“火车头”（头指针 Head）来标记。

严谨原理：节点与指针

链表在内存中的存储是非连续的。它由一系列节点 (Node) 组成，这些节点可以散落在内存的各个角落。

每个节点包含两部分：

  1. **数据域 (Data)**：存储元素本身。
  2. **指针域 (Pointer/Next)**：存储指向下一个节点的内存地址。

通过一个指向第一个节点的**头指针 (Head Pointer)**，我们就可以像顺着铁链一样，遍历整个链表。

2. 关键图示

单向链表的逻辑结构
链表节点在内存中是分散的，通过指针串联在一起

3. 步骤分解：核心操作分析

  • **访问 (Access)**：O(n)。要访问第 i 个元素，必须从头指针 Head 开始，沿着指针一步步向后遍历 i 次。
  • **查找 (Search)**：O(n)。与访问类似，也需要从头遍历。
  • **插入 (Insert)**：O(1)（如果已知前驱节点）。只需要修改前后两个节点的指针即可，无需移动元素。
  • **删除 (Delete)**：O(1)（如果已知前驱节点）。同样是修改指针。

4. 动画式案例：在链表中插入节点

场景：在链表 10 -> 20 -> 40 中，节点 20 之后插入新节点 30。

步骤变化：

  1. 初始状态: Head -> [10, next] -> [20, next] -> [40, NULL]
  2. 创建新节点: 在内存中创建一个新节点 newNode，数据为 30。
    newNode = [30, NULL]
  3. 找到插入位置: 从 Head 开始遍历，找到节点 20（我们称之为 prevNode）。
  4. 修改指针 1: 将新节点的 next 指针指向 prevNode 原来的下一个节点（即节点 40）。
    newNode.next = prevNode.next
    现在 [30, next] 指向了 [40, NULL]。
  5. 修改指针 2: 将 prevNode 的 next 指针指向新节点。
    prevNode.next = newNode
    现在 [20, next] 指向了 [30, next]。
  6. 最终状态: Head -> [10] -> [20] -> [30] -> [40, NULL]

整个过程就像在火车车厢之间再挂上一节新的车厢，只需要断开和重连两个连接器，其他车厢完全不受影响。

伪代码与 Python 实现

伪代码：在链表指定节点后插入

// 在节点 prevNode 之后插入一个值为 data 的新节点
function insertAfter(prevNode, data):
  // 1. 检查前驱节点是否存在
  if prevNode is NULL:
    return
    
  // 2. 创建新节点
  newNode = new Node(data)
  
  // 3. 将新节点的 next 指向 prevNode 的下一个节点
  newNode.next = prevNode.next
  
  // 4. 将 prevNode 的 next 指向新节点
  prevNode.next = newNode

Python 实现：一个简单的单向链表

class Node:
    """链表节点类"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """单向链表类"""
    def __init__(self):
        self.head = None

    def append(self, data):
        """在链表末尾添加节点"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        """打印链表内容"""
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("NULL")

# Python 的 list 类型是动态数组，不是链表
# 这是一个链表的简单实现示例
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()  # 输出: 10 -> 20 -> 30 -> NULL

复杂度推导与对比

时间复杂度对比

操作数组 (动态)链表胜出者理由
访问第 i 个元素O(1)O(n)数组内存连续，可公式计算地址
在开头插入/删除O(n)O(1)链表只需修改头指针
在末尾插入/删除O(1) (均摊)O(1) (需尾指针)平手均可高效操作
在中间插入/删除O(n)O(n)平手链表虽插入快，但查找慢

注意：链表中间插入/删除操作本身是 O(1)，但找到那个位置需要 O(n)，所以总复杂度是 O(n)。

空间复杂度对比

  • 数组：O(n)。需要一块完整的、连续的内存。
  • 链表：O(n)。由 n 个节点组成，但每个节点除了数据外，还需要额外存储一个指针。因此，虽然都是 O(n)，但链表的空间常数因子更大。
    空间(链表) = n * (sizeof(data) + sizeof(pointer))
    空间(数组) = n * sizeof(data)

优势 / 劣势 / 易错点

数组

  • 优势：
    • 随机访问快：O(1) 的访问速度是其最大优势。
    • 缓存友好：内存连续，CPU 缓存命中率高，实际执行效率可能比理论分析更高。
  • 劣势：
    • 增删慢：中间元素的插入和删除需要移动大量元素。
    • 空间固定：静态数组大小固定，可能造成浪费或不足。动态数组在扩容时有性能开销。
  • 易错点：
    • 数组越界 (Index out of bounds)。
    • 动态数组扩容的时机和策略。

链表

  • 优势：
    • 增删快：真正的动态结构，插入和删除（在已知位置时）非常高效。
    • 空间灵活：按需分配内存，不会浪费空间。
  • 劣势：
    • 随机访问慢：O(n) 的访问速度是其最大短板。
    • 缓存不友好：内存不连续，缓存命中率低。
    • 额外空间开销：需要存储指针。
  • 易错点：
    • 指针丢失：在修改指针时，操作顺序错误可能导致链表断裂。
    • 空指针 (Null Pointer Exception)：对 NULL 节点的 next 属性进行操作。
    • 忘记处理头/尾节点：在链表头尾进行增删的边界情况。

适用场景

场景推荐结构理由
需要频繁随机访问元素数组O(1) 访问速度无与伦比
存储的数据量基本固定数组避免动态扩容开销
需要频繁在头部或中间插入/删除链表O(1) 的操作效率极高
数据量无法预估，动态变化大链表空间按需分配，灵活
对内存要求苛刻（每个字节都要省）数组无需存储额外指针
需要实现栈、队列等结构两者皆可数组实现的栈/队列更简单，链表实现的更灵活

扩展算法 & 进阶方向

  • 数组进阶：

    • **动态数组 (Dynamic Array)**：如 C++ 的 vector，Java 的 ArrayList，能自动扩容。
    • 二维数组/矩阵：用于图像处理、棋盘游戏等。
    • 稀疏数组：用于压缩存储大量默认值的数组。

  • 链表进阶：

    • **双向链表 (Doubly Linked List)**：每个节点有两个指针，分别指向前一个和后一个节点。支持双向遍历，但空间开销更大。
    • **循环链表 (Circular Linked List)**：尾节点的指针指向头节点，形成一个环。常用于需要循环处理的场景。
    • **跳表 (Skip List)**：一种“带索引”的链表，通过多层指针实现 O(log n) 级别的查找，是链表版的“二分查找”。

  • 经典面试题：

    • 双指针技巧：常用于数组和链表，如快慢指针判断链表是否有环。
    • 链表反转：原地反转一个单向链表。
    • 合并两个有序链表/数组。

总结

数组和链表，作为线性表的两大实现，各自占据了数据结构世界的半壁江山。它们没有绝对的优劣，只有是否适合特定场景。

**核心权衡 (Core Trade-off)**：

数组用“连续的内存空间”换来了“O(1) 的访问时间”，却牺牲了“O(n) 的增删效率”。
链表用“灵活的指针”换来了“O(1) 的增删效率”，却牺牲了“O(n) 的访问时间”。

深刻理解这一核心权衡，是你未来在面对复杂问题时，能否做出正确技术选型的关键。在后续的文章中，我们将看到，栈、队列、哈希表等更高级的数据结构，其底层实现都离不开数组和链表的身影。

大学算法全体系 > Part 2：基础数据结构
#数据结构 #数组 #链表 #线性表 #面试
Part 2.1：数组与链表：相爱相杀的线性双雄
https://hjjjkh.github.io/posts/a3b18b6d
作者
李国强
发布于
2025年11月15日
许可协议