数组与链表：内存布局、操作特性与双指针技巧
数组和链表是面试中最基础、最高频的数据结构。理解它们的底层差异，掌握常见算法技巧，是攻克算法面试的第一步。
一、核心差异对比
| 特性 | 数组（Array） | 链表（Linked List） |
|---|---|---|
| 内存分配 | 连续空间 | 离散节点，指针连接 |
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n)（需搬移） | O(1) |
| 尾部插入 | 均摊 O(1)（动态数组） | O(n)（需遍历） / O(1)（带尾指针） |
| 中间删除 | O(n) | O(1)（已知前驱） |
| 缓存友好性 | 高（空间局部性） | 低（指针跳转） |
| 额外空间 | 无 | O(n) 指针开销 |
内存布局示意
数组 — Elements 在内存中连续排列：
[0] [1] [2] [3] [4] ← 地址连续
^base_addr
arr[i] 地址 = base + i × sizeof(element)
链表 — 节点分散，通过 next 指针连接：
[数据|next] → [数据|next] → [数据|next] → null
0x1000 0x2000 0x1500 ← 地址不连续
二、数组高频技巧
1. 双指针（Two Pointers）
双指针是数组类问题的核心技巧，分为三种模式：
（1）对撞指针
左右指针从两端向中间移动，适用于「两数之和」「回文判断」。
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left, right]
elif s < target:
left += 1
else:
right -= 1
return []
（2）快慢指针
快指针探路，慢指针记录有效位置，适用于「原地修改」「删除重复项」。
def remove_duplicates(nums):
if not nums:
return 0
slow = 1
for fast in range(1, len(nums)):
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
return slow
（3）滑动窗口
动态维护子数组边界，适用于「子串问题」「满足条件的连续区间」。
def min_sub_array_len(target, nums):
left = total = 0
result = float('inf')
for right in range(len(nums)):
total += nums[right]
while total >= target:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return result if result != float('inf') else 0
2. 前缀和（Prefix Sum）
将「区间求和」转化为「两点差值」，实现 O(1) 查询。
class PrefixSum:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def query(self, left, right):
return self.prefix[right + 1] - self.prefix[left]
适用题型：子数组求和、和为 K 的子数组、区间统计。
三、链表高频技巧
1. 链表反转
面试必考基础题，迭代和递归两种写法都要掌握。
# 迭代法（推荐面试书写）
def reverse_list(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
# 递归法
def reverse_list_recursive(head):
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
2. 快慢指针：环检测与中点查找
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
3. 双链表合并与分隔
# 合并两个有序链表
def merge_two_lists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next, l1 = l1, l1.next
else:
tail.next, l2 = l2, l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
四、经典例题索引
| 题号 | 题目 | 技巧 | 难度 |
|---|---|---|---|
| LeetCode 1 | 两数之和 | 哈希表 / 双指针 | Easy |
| LeetCode 15 | 三数之和 | 排序 + 双指针 | Medium |
| LeetCode 76 | 最小覆盖子串 | 滑动窗口 | Hard |
| LeetCode 206 | 反转链表 | 迭代 / 递归 | Easy |
| LeetCode 141 | 环形链表 | 快慢指针 | Easy |
| LeetCode 21 | 合并两个有序链表 | 双指针 | Easy |
| LeetCode 560 | 和为 K 的子数组 | 前缀和 + 哈希 | Medium |
| LeetCode 3 | 无重复字符的最长子串 | 滑动窗口 | Medium |
五、面试常见问题
Q: 为什么数组比链表缓存友好？
因为数组元素连续存储，CPU 缓存线（Cache Line）一次可加载多个相邻元素，减少内存访问次数。链表节点分散，每次访问都可能触发缓存未命中（Cache Miss）。
Q: 什么场景必须用链表而不是数组？
- 频繁在头部/中间插入删除（O(1) vs O(n)）
- 不确定数据总量（避免数组扩容拷贝）
- 实现 LRU、LFU 等缓存淘汰策略
Q: 二维数组的内存布局？
行优先（Row-major）：a[i][j] 地址 = base + (i × cols + j) × sizeof(T)。理解这一点对矩阵类题目（旋转、搜索）的优化很关键。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。