数组与链表：存储结构与增删改查

数组与链表：存储结构与增删改查

在计算机科学中，数组和链表是最基础的两种线性数据结构。理解它们在内存中的存储方式以及基本操作的时间复杂度，是算法学习的基石。本教程将从存储结构出发，逐一拆解两者的增、删、改、查操作。

内存中的存储结构

数组：连续内存块

数组在内存中占据一块连续的地址空间。这意味着所有元素依次紧邻存放，可以通过首地址加上偏移量直接计算出任意元素的位置。

• 优点：支持随机访问，给定索引 i 可在 O(1) 时间内找到元素。
• 缺点：大小固定（静态数组）或扩容代价高（动态数组需拷贝整个块）；插入和删除可能需要移动大量元素。

地址:  100  104  108  112  116
       [10] [20] [30] [40] [50]
索引:    0    1    2    3    4

链表：离散节点+指针

链表由一系列节点组成，每个节点存放数据以及指向下一个（和/或上一个）节点的指针。节点在内存中不必连续。

• 优点：动态大小，插入和删除节点时无需移动其他元素，只需修改指针。
• 缺点：不支持随机访问，查找某个元素必须从头遍历，时间复杂度 O(n)。

单向链表结构:
[head] -> [10|next] -> [20|next] -> [30|next] -> null

双向链表结构:
[head] <-> [10|prev|next] <-> [20|prev|next] <-> [30|prev|next] <-> [tail]

增：插入元素

数组的插入

• 末尾插入 (如 push)：若数组有剩余容量，直接在尾部写入，时间复杂度 O(1)；若需扩容，则 O(n)。
• 中间/头部插入：需要将插入点之后的所有元素向后移动一位，平均移动 n/2 个元素，时间复杂度 O(n)。

  # 在索引 i 处插入 val
  arr.insert(i, val)  # 需移动元素，O(n)
  

链表的插入

• 头部/尾部插入：只需创建新节点，调整头尾指针，时间复杂度 O(1)（如果能直接访问尾节点）。
• 指定节点后插入：找到目标节点（需 O(n) 查找），然后修改指针，插入动作本身 O(1)。

  # 在节点 node 之后插入 val
  new_node = Node(val)
  new_node.next = node.next
  node.next = new_node
  

• 如果在指定位置前插入，单向链表需从头遍历找到前驱节点，O(n)；双向链表则可直接通过前驱指针定位，插入操作 O(1)。

删：移除元素

数组的删除

删除指定位置的元素后，需要将该位置之后的所有元素向前移动一位填补空缺，时间复杂度 O(n)。删除末尾元素则为 O(1)。

arr.pop(i)  # 删除索引 i 的元素，后续元素前移

链表的删除

删除已知节点的下一个节点（或当前节点，若知道前驱）只需修改指针，并释放节点（或由垃圾回收处理），操作 O(1)。但要找到待删节点本身，通常需要 O(n) 的查找时间。

# 删除 node 的下一个节点
if node.next:
    node.next = node.next.next

• 双向链表删除：可以通过 node.prev.next = node.next 等方式在 O(1) 内完成删除（已知节点引用时）。

改：修改元素

数组的修改

直接通过索引访问并赋值，时间复杂度 O(1)。

arr[i] = new_value  # O(1)

链表的修改

需先遍历找到目标节点，然后修改其数据域。查找 O(n)，修改 O(1)。整体 O(n)。

cur = head
for _ in range(i):
    cur = cur.next
cur.val = new_value

查：查找元素

按索引查找（随机访问）

• 数组：通过 base_address + index * element_size 直接计算地址，O(1)。
• 链表：必须从头部开始逐个遍历，直到第 i 个节点，O(n)。

按值查找（搜索特定元素）

• 数组：线性扫描或二分查找（需有序），无序时为 O(n)。
• 链表：同样需要线性扫描，O(n)，无法进行二分查找。

对比总结

实际应用场景选择

• 需要频繁随机访问（如实现栈、数值计算、二分查找等）→ 选用数组。
• 需要频繁在头部或中间插入/删除，且无法预先确定大小 → 选用链表。
• 双向链表常用于实现 LRU 缓存、浏览器历史记录等。
• 现代编程语言中，动态数组（如 Python 的 list、Java 的 ArrayList）结合了数组随机访问和自动扩容的优点；而标准库中的链表（如 LinkedList）则直接提供节点操作接口。

掌握数组与链表的底层差异，能帮助你在实际开发中做出正确的数据结构选择，也为后续学习栈、队列、哈希表等复杂结构奠定基础。