常用数据结构 ​

数组、链表、栈、队列、哈希表、堆是刷题与面试的"地基"。本文按「底层原理 → 复杂度表 → 适用场景 → 语言 API → 典型坑」组织，代码示意统一用 Python。

一、总览与复杂度速查 ​

1.1 为什么必须懂底层原理 ​

• 复杂度结论依赖底层实现：数组为什么按下标 O(1)？链表为什么插入快、查找慢？
• 面试常问「ArrayList 和 LinkedList 区别」「HashMap 底层」，本质就是本文各节的浓缩。

1.2 各结构常用操作复杂度总表 ​

*数组尾部追加均摊 O(1)，头部插入 O(n)；**已知前驱节点的前提下。

1.3 选型口诀 ​

• 要按下标随机访问 → 数组；要频繁在头部/中间增删 → 链表。
• 先进后出 → 栈；先进先出 → 队列；查找快 → 哈希表；动态取最值 → 堆。

二、数组（Array） ​

2.1 底层实现原理 ​

• 内存中一段连续空间，元素等宽排布；a[i] 的地址 = 首地址 + i × 元素大小，因此 O(1) 随机访问。

连续内存示意：
地址： base+0    base+4    base+8    base+12
      ┌────────┬────────┬────────┬────────┐
      │  a[0]  │  a[1]  │  a[2]  │  a[3]  │
      └────────┴────────┴────────┴────────┘

连续内存示意：
地址： base+0    base+4    base+8    base+12
      ┌────────┬────────┬────────┬────────┐
      │  a[0]  │  a[1]  │  a[2]  │  a[3]  │
      └────────┴────────┴────────┴────────┘

2.2 操作时间复杂度 ​

2.3 适用场景 ​

• 需要随机访问、数据量稳定、缓存友好的场景；几乎所有算法题的"底子"。
• 排序、二分、双指针、滑动窗口都在数组上进行。

2.4 语言 API 提示 ​

• Java：int[] 定长；动态数组用 ArrayList（自动扩容）。
• Python：list 即动态数组，尾部 append/pop 均摊 O(1)。
• 刷题注意：Python list.pop(0) 与 insert(0, x) 是 O(n)。

2.5 典型坑 ​

• 扩容：ArrayList 扩容到 1.5 倍并拷贝，批量插入前可先 ensureCapacity。
• 中间删除：循环里删元素会下标错位，应倒序遍历或收集后统一删。
• 越界：二分/滑动窗口极易下标越界，用「左闭右开」统一风格可减少 bug。

三、链表（Linked List） ​

3.1 底层实现原理 ​

• 由节点串联，每个节点存数据 + 指向下一个节点的指针；内存不必连续。
• 单链表只能向后走；双链表有 prev/next；循环链表尾节点指向头。

单链表示意：
head → [1 | ●] → [2 | ●] → [3 | null]
       data next   data next   data next

双向链表示意：
null ← [1] ⇄ [2] ⇄ [3] → null

单链表示意：
head → [1 | ●] → [2 | ●] → [3 | null]
       data next   data next   data next

双向链表示意：
null ← [1] ⇄ [2] ⇄ [3] → null

3.2 单链表 / 双链表 / 循环链表对比 ​

3.3 操作时间复杂度 ​

3.4 适用场景 ​

• 高频头尾增删且不常按下标查：LRU、任务队列、邻接表。
• 面试题：反转链表、环检测、找中点、合并有序链表、K 个一组反转。

3.5 语言 API 提示 ​

• Java：LinkedList 同时实现 List 与 Deque（双链表）。
• Python：无内建链表，刷题常自定义 class ListNode；队列用 collections.deque（双链表实现）。

3.6 典型坑 ​

• 环：不判空/不判环会死循环；环检测用快慢指针（快走 2 步慢走 1 步）。
• 虚拟头结点：头结点可能被删/被换，统一用 dummy 节点简化边界。
• 断链顺序：链表操作必须先保存后继再改指针，顺序写错会丢节点。

# 反转链表（迭代）模板
def reverse(head):
    prev = None
    while head:
        nxt = head.next   # 先保存后继
        head.next = prev  # 再改指向
        prev, head = head, nxt
    return prev

# 反转链表（迭代）模板
def reverse(head):
    prev = None
    while head:
        nxt = head.next   # 先保存后继
        head.next = prev  # 再改指向
        prev, head = head, nxt
    return prev

四、栈（Stack） ​

4.1 原理：后进先出 LIFO ​

• 只在一端（栈顶）插入与删除，像叠盘子。

push 1 → push 2 → push 3 → pop
        ┌───┐
        │ 3 │ ← 栈顶 top
        ├───┤
        │ 2 │
        ├───┤
        │ 1 │ ← 栈底
        └───┘

push 1 → push 2 → push 3 → pop
        ┌───┐
        │ 3 │ ← 栈顶 top
        ├───┤
        │ 2 │
        ├───┤
        │ 1 │ ← 栈底
        └───┘

4.2 操作时间复杂度 ​

4.3 适用场景 ​

• 函数调用栈（递归的底层就是栈）；括号/表达式匹配；撤销操作。
• 单调栈（见高频算法题套路）：下一个更大元素、接雨水、柱状图最大矩形。
• 二叉树前/中/后序的迭代遍历都用栈模拟递归。

4.4 语言 API 提示 ​

• Java：ArrayDeque（推荐，比 Stack 快）或 LinkedList，用 push/pop/peek。
• Python：list 即可，append/pop 就是栈；也可用 collections.deque。

4.5 典型坑 ​

• Java Stack 继承 Vector、带锁，性能差且遗留 API，面试建议说用 ArrayDeque。
• pop 前必须先判空，否则抛异常；处理「出栈后还要比较栈顶」时注意栈空。
• 递归转迭代 = 显式用栈保存状态，别忘压入顺序与执行顺序相反。

五、队列（Queue） ​

5.1 原理：先进先出 FIFO ​

• 队尾入队、队头出队，像排队。数组实现的队列会"假溢出"，常用循环队列复用空间。

入队 a → b → c（队尾 tail 追加）
出队顺序：a → b → c
      head                  tail
       ↓                     ↓
      [a] [b] [c] [ ] [ ]

入队 a → b → c（队尾 tail 追加）
出队顺序：a → b → c
      head                  tail
       ↓                     ↓
      [a] [b] [c] [ ] [ ]

5.2 操作时间复杂度 ​

5.3 适用场景 ​

• BFS（二叉树层序、图最短步数、迷宫最短路）必用队列，见树与图。
• 生产者-消费者缓冲、任务调度、滑动窗口的单调队列优化。

5.4 语言 API 提示 ​

• Java：接口 Queue + LinkedList/ArrayDeque 实现；双端用 Deque。
• Python：collections.deque 的 append/popleft 均 O(1)；纯 list 做队首出队是 O(n)。

5.5 典型坑 ​

• Java 队列是接口不能 new；add/remove 失败抛异常，offer/poll 失败返回特殊值。
• Python 用 list.pop(0) 当队列 → O(n)，数据量大必超时，务必用 deque。
• 循环队列判空/判满的公式容易写错：(tail+1) % cap == head 判满（牺牲一格）。

六、哈希表（Hash Table） ​

6.1 底层实现原理 ​

• 通过哈希函数把 key 映射到桶下标，理想情况直接定位 → O(1)。
• 哈希冲突（不同 key 同桶）两种主流解法：拉链法（桶里挂链表/红黑树）与开放寻址法（线性探测）。

拉链法示意（Java HashMap 结构）：
bucket:  0    1    2    3
         │    │    │    │
        null [k1|v1]─►[k5|v5]   ← 冲突 key 挂成链/树
              │
             [k2|v2]

拉链法示意（Java HashMap 结构）：
bucket:  0    1    2    3
         │    │    │    │
        null [k1|v1]─►[k5|v5]   ← 冲突 key 挂成链/树
              │
             [k2|v2]

6.2 操作时间复杂度 ​

6.3 适用场景 ​

• 空间换时间的头号工具：判重、计数、两数之和、缓存、索引映射。
• 需要「把 O(n²) 变 O(n)」时优先想到哈希表（对每个元素问"之前出现过互补值吗"）。

6.4 语言 API 提示 ​

• Java：HashMap（拉链+树化）、HashSet、LinkedHashMap（可做 LRU）。
• Python：dict/set 基于开放寻址；defaultdict 省去判存在分支；Counter 直接计数。

6.5 典型坑 ​

• 哈希冲突与扩容：装填因子超阈值扩容并全部 rehash，批量预知大小可指定初始容量。
• Java 自定义对象做 key 必须重写 hashCode 与 equals，且 key 应不可变（改字段后查不到）。
• Python dict 的 key 必须可哈希（hashable），list 不能做 key，tuple 可以。
• 迭代时不要直接删元素：Java 用 Iterator.remove()，Python 可收集后统一删或倒序遍历。

七、堆（Heap / 优先队列） ​

7.1 底层实现原理 ​

• 逻辑上是完全二叉树，物理上用数组存储（下标 i 的孩子是 2i+1、2i+2）。
• 大顶堆：父 ≥ 子，堆顶最大；小顶堆：父 ≤ 子，堆顶最小。

小顶堆（数组下标从 0）：
        1
       / \
      3   2          → 数组 [1, 3, 2, 6, 5]
     / \
    6   5

小顶堆（数组下标从 0）：
        1
       / \
      3   2          → 数组 [1, 3, 2, 6, 5]
     / \
    6   5

7.2 上浮与下沉 ​

• 上浮（sift up）：新元素放末尾，不断和父比较上移 → 插入用。
• 下沉（sift down）：堆顶被换走/删除后，新堆顶与较小(较大)孩子交换下移 → 删除用。
• 建堆：从最后一个非叶子节点向前逐个下沉，总代价 O(n)。

7.3 操作时间复杂度 ​

7.4 适用场景 ​

• TopK 问题（前 K 大用小顶堆维护 K 个元素），见排序与查找。
• 动态数据流中位数（大顶堆+小顶堆）、合并 K 个有序链表、定时任务、Dijkstra 的堆优化。

7.5 语言 API 提示 ​

• Java：PriorityQueue<E>（默认小顶堆），大顶堆传 (a,b) -> b - a 或 Comparator.reverseOrder()。
• Python：heapq（默认小顶堆），大顶堆技巧是存 -x；无自定义类时用元组 (优先级, 值)。

7.6 典型坑 ​

• Java PriorityQueue 的迭代遍历不是有序的，只有逐个 poll 才有序。
• 自定义对象入堆要提供 Comparator，否则 ClassCastException；比较器写反堆的顶就反了。
• Python 想从堆里"修改优先级"没有现成 API，常用标记删除（懒惰删除）或重建。
• 两个元素比较相等时堆序不定，需要"先按 x 再按 y"的稳定次序时，Java 比较器写全字段。

八、结构组合与题感速查 ​

8.1 常见组合套路 ​

• 哈希表 + 双向链表：O(1) 查与 O(1) 增删 → LRU 缓存。
• 两个栈：实现队列 / 最小栈。
• 栈 + 数组下标：单调栈记录"左侧/右侧第一个更小/更大"。
• 哈希表 + 小顶堆：前 K 个高频元素（先计数再堆）。
• 队列 + 单调性：单调队列求滑动窗口最值。

8.2 常见题用哪个结构（速查表） ​