正在切换页面...

数据结构基础

medium数据结构基础架构必备最近更新

数据结构是程序的骨架。选择正确的数据结构，算法效率可以从 O(n²) 降到 O(n log n) 甚至 O(1)；选错了，再精妙的算法也救不回来。本文系统梳理 8 种最常用的数据结构，每种都从内存模型、操作复杂度和在 Java 集合框架中的映射三个角度讲透。

本文聚焦数据结构本身的原理。各数据结构在 Java 集合框架中的具体实现（如 HashMap、ArrayList 等），在本目录的其他文章中有专门的源码级深入分析。

线性结构 vs 非线性结构

在展开讲解之前，先建立一个宏观的分类框架：

数据结构
├── 线性结构（元素之间是一对一的前后关系）
│   ├── 数组（Array）        ← 连续内存，随机访问
│   ├── 链表（Linked List）  ← 离散内存，指针串联
│   ├── 栈（Stack）          ← 受限的线性表，后进先出
│   └── 队列（Queue）        ← 受限的线性表，先进先出
│
└── 非线性结构（元素之间是一对多或多对多关系）
    ├── 哈希表（Hash Table）  ← 键值映射，近似 O(1) 查找
    ├── 树（Tree）           ← 一对多的层级关系
    ├── 堆（Heap）           ← 特殊的树，快速取极值
    └── 图（Graph）          ← 多对多的网状关系

这个分类的核心区别在于：线性结构中每个元素最多有一个前驱和一个后继，而非线性结构打破了这个约束。理解这一点，就能理解为什么不同的数据结构适合不同的问题。

数组（Array）

是什么

数组是最基本的数据结构——一段连续的内存空间，存储相同类型的元素，通过整数下标直接访问。

可以把数组想象成一排编了号的储物柜：每个柜子大小相同，知道编号就能直接打开对应的柜子，不需要从头找起。

内存模型

数组 int[] arr = {10, 20, 30, 40, 50};

内存布局（假设起始地址 0x100，int 占 4 字节）：

地址:    0x100   0x104   0x108   0x10C   0x110
         ┌───────┬───────┬───────┬───────┬───────┐
值:      │  10   │  20   │  30   │  40   │  50   │
         └───────┴───────┴───────┴───────┴───────┘
下标:     [0]     [1]     [2]     [3]     [4]

随机访问的秘密：要访问 arr[i]，CPU 只需计算 起始地址 + i × 元素大小 就能直接定位，这是一次简单的算术运算，耗时 O(1)。这就是数组最核心的优势。

关键操作与复杂度

操作	时间复杂度	原因
随机访问 `arr[i]`	O(1)	地址计算：`base + i × size`
尾部追加	O(1) 均摊	空间够就直接放；不够则扩容后复制
中间插入 / 删除	O(n)	必须移动后续所有元素来填补空隙
按值查找（无序）	O(n)	只能逐个比较
按值查找（有序）	O(log n)	可以用二分查找

插入的代价

为什么数组中间插入慢？因为必须保持元素的连续性：

在下标 2 处插入 25：

插入前：[10, 20, 30, 40, 50]
                ↓
步骤1 - 后移:  [10, 20, __, 30, 40, 50]   ← 30/40/50 各后移一位
步骤2 - 填入:  [10, 20, 25, 30, 40, 50]   ← 写入新值

n 个元素的数组，在位置 i 插入需要移动 n - i 个元素，平均下来是 O(n)。

扩容机制

Java 的原生数组长度不可变。ArrayList 在容量不足时会创建一个更大的新数组（通常是原来的 1.5 倍），然后把所有元素复制过去。这就是为什么 ArrayList 的 add() 操作是"O(1) 均摊"——大多数时候是 O(1)，偶尔一次扩容是 O(n)，摊下来还是 O(1)。

Java 映射

数据结构	Java 实现	说明
静态数组	`int[]`, `String[]`	长度固定，不可扩容
动态数组	`ArrayList`	底层是 `Object[]`，自动扩容

链表（Linked List）

是什么

链表是另一种线性结构，但和数组截然不同：元素在内存中不需要连续存放，每个元素（节点）通过指针指向下一个节点，像一条链子一样串起来。

如果说数组像一排储物柜，链表就像一条寻宝线索链：每个线索上写着当前宝藏的位置和下一条线索的位置。你必须从第一条线索开始，一条一条跟着走。

链表的种类

单链表：
  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ data: 10 │    │ data: 20 │    │ data: 30 │
  │ next: ───┼───►│ next: ───┼───►│ next: null│
  └──────────┘    └──────────┘    └──────────┘
  head                                 tail

双向链表：
       ┌──────────────┐    ┌──────────────┐    ┌──────────────┐
       │ prev: null    │◄───┤ prev: ───    │◄───┤ prev: ───    │
       │ data: 10      │    │ data: 20      │    │ data: 30      │
       │ next: ────────┼───►│ next: ────────┼───►│ next: null    │
       └──────────────┘    └──────────────┘    └──────────────┘
       head                                       tail

循环链表：
  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ data: 10 │    │ data: 20 │    │ data: 30 │
  │ next: ───┼───►│ next: ───┼───►│ next: ───┼──┐
  └──────────┘    └──────────┘    └──────────┘  │
  ▲                                              │
  └──────────────────────────────────────────────┘

关键操作与复杂度

操作	时间复杂度	原因
头部插入 / 删除	O(1)	改两个指针就行
已知节点的插入 / 删除	O(1)	只需修改前后节点的指针
按下标访问	O(n)	必须从头遍历到目标位置
按值查找	O(n)	必须逐个比较

链表插入 vs 数组插入

链表最大的优势就是插入和删除不需要移动元素：

在节点 B 后面插入新节点 X：

插入前：A ──► B ──► C

步骤1：X.next = C           ← 新节点指向后继
步骤2：B.next = X           ← 前驱指向新节点

插入后：A ──► B ──► X ──► C

只修改了两个指针，O(1) 搞定。但前提是你已经知道要在哪个节点后面插入——如果需要先按下标找到那个节点，光"找"这一步就是 O(n)。所以常说链表"插入 O(1)"时，隐含的前提是已经持有目标节点的引用。

数组 vs 链表：核心权衡

维度	数组	链表
内存布局	连续	离散
随机访问	O(1) ✅	O(n) ❌
头部插入/删除	O(n) ❌	O(1) ✅
内存利用	可能浪费（预分配）	精确分配（但指针有额外开销）
缓存友好	高（局部性好）	低（节点分散在内存各处）

最后一行值得注意：现代 CPU 有缓存预取机制（Prefetch），连续内存的数组能被整块加载到 CPU 缓存中，而链表节点散落在内存各处，每次访问下一个节点都可能触发 cache miss。这就是为什么在实践中，即使理论复杂度相同，数组的性能往往优于链表。

Java 映射

数据结构	Java 实现	说明
双向链表	`LinkedList`	同时实现了 `List` 和 `Deque` 接口

栈（Stack）

是什么

栈是一种受限的线性结构，只允许在一端（栈顶） 进行插入和删除操作，遵循后进先出（LIFO: Last In First Out）原则。

把栈想象成一摞盘子：你只能从最上面放盘子（入栈 push）和取盘子（出栈 pop），不能从中间抽。

操作示例

操作序列：push(1), push(2), push(3), pop(), push(4), pop()

         ┌───┐     ┌───┐     ┌───┐              ┌───┐
         │   │     │   │     │ 3 │ ← top         │   │
         ├───┤     ├───┤     ├───┤     ┌───┐     ├───┤     ┌───┐
         │   │     │ 2 │     │ 2 │     │ 2 │     │ 4 │     │ 2 │
         ├───┤     ├───┤     ├───┤     ├───┤     ├───┤     ├───┤
         │ 1 │     │ 1 │     │ 1 │     │ 1 │     │ 1 │     │ 1 │
         └───┘     └───┘     └───┘     └───┘     └───┘     └───┘
        push(1)   push(2)   push(3)    pop()    push(4)    pop()
                                      返回 3              返回 4

关键操作与复杂度

操作	时间复杂度	说明
`push(e)` — 入栈	O(1)	在栈顶添加元素
`pop()` — 出栈	O(1)	移除并返回栈顶元素
`peek()` — 查看栈顶	O(1)	返回栈顶元素但不移除

底层实现：数组 vs 链表

栈可以用数组或链表实现：

数组实现：用一个变量 top 记录栈顶位置，push 时 top++，pop 时 top--。优点是缓存友好。
链表实现：栈顶就是链表的头节点，push 时在头部插入，pop 时删除头节点。优点是不需要处理扩容。

Java 中推荐用 ArrayDeque 做栈（数组实现），而不是老旧的 Stack 类。Stack 继承自 Vector，每个方法都加了 synchronized 锁，在单线程场景下白白付出同步开销。

常见应用场景

场景	说明
方法调用栈	JVM 用栈帧管理方法调用，每调用一个方法就压入一个栈帧
表达式求值	中缀转后缀、括号匹配
深度优先搜索（DFS）	递归本质上就是用方法调用栈实现的 DFS
浏览器前进/后退	两个栈分别记录历史和前进页面
撤销操作（Undo）	每次操作入栈，撤销时出栈

Java 映射

数据结构	Java 实现	说明
栈	`ArrayDeque`（推荐）	用 `push()` / `pop()` / `peek()`
栈	`Stack`（已过时）	线程安全但性能差

队列（Queue）

是什么

队列也是受限的线性结构，遵循先进先出（FIFO: First In First Out）原则——从队尾入队，从队头出队。

就像排队买奶茶：先到的人先点单，后到的人排在后面。不允许插队，也不允许从队尾出去（那就是"逃跑"了）。

队列的变体

普通队列（FIFO）：
  入队 → [A, B, C, D] → 出队
         队尾          队头

双端队列（Deque）：
  入队 ←→ [A, B, C, D] ←→ 出队
         两端都可以操作

优先队列（Priority Queue）：
  入队 → [按优先级排列] → 出队（总是优先级最高的先出）

关键操作与复杂度

操作	普通队列	优先队列
入队 `offer(e)`	O(1)	O(log n)（堆插入）
出队 `poll()`	O(1)	O(log n)（堆删除）
查看队头 `peek()`	O(1)	O(1)

循环数组实现

用普通数组实现队列有个问题：出队时如果把数组头部的元素删了，后面的元素要不要前移？如果前移就是 O(n)，不移就会浪费前面的空间。

循环数组（Circular Array）解决了这个问题：把数组的首尾"接起来"，用两个指针 head 和 tail 分别追踪队头和队尾的位置：

普通数组的浪费：
  出队几次后        [_, _, _, D, E, F]      ← 前面三格浪费了
                     ▲              ▲
                   浪费了          tail

循环数组的复用：
  容量为 6 的循环数组：

     ┌───┬───┬───┬───┬───┬───┐
     │ G │   │   │ D │ E │ F │
     └───┴───┴───┴───┴───┴───┘
       ▲   ▲       ▲
      tail         head
      (1)         (3)

  tail 绕回到了数组前面，充分利用了空间
  下标计算：next = (current + 1) % capacity

Java 的 ArrayDeque 就是用循环数组实现的，这也是它比 LinkedList 做队列更快的原因——连续内存，缓存友好。

常见应用场景

场景	队列类型	说明
BFS 广度优先搜索	普通队列	层序遍历树/图
任务调度	普通/优先队列	线程池的任务排队
消息队列	阻塞队列	生产者-消费者模式
缓存淘汰（LRU）	双端队列	最近使用的放队头，淘汰队尾
定时任务	延迟队列	到期时间最早的先出队

Java 映射

数据结构	Java 实现	说明
普通队列	`ArrayDeque`（推荐）	循环数组实现
普通队列	`LinkedList`	双向链表实现
优先队列	`PriorityQueue`	小顶堆实现
阻塞队列	`ArrayBlockingQueue`	有界阻塞，线程安全
延迟队列	`DelayQueue`	元素到期后才能出队

哈希表（Hash Table）

是什么

哈希表是一种通过键（Key）直接定位值（Value） 的数据结构。核心思想：用一个哈希函数把键转换成数组下标，从而实现近似 O(1) 的查找。

把哈希表想象成一个超大型停车场：每辆车（键）根据车牌号经过一个公式计算出分配的车位号（数组下标），停车和找车都不需要遍历整个停车场。

工作原理

put("apple", 100) 的过程：

1. 计算哈希值：  hash("apple") = 2036578       ← hashCode()
2. 映射到下标：  2036578 % 16 = 2              ← 假设数组长度 16
3. 存入桶：      table[2] = Entry("apple", 100)

get("apple") 的过程：

1. 计算哈希值：  hash("apple") = 2036578       ← 同样的计算
2. 映射到下标：  2036578 % 16 = 2              ← 直达目标位置
3. 取出值：      table[2].value → 100

哈希表内部结构：

下标:  0      1      2              3      ...    15
     ┌──────┬──────┬──────────────┬──────┬──────┬──────┐
     │ null │ null │ apple:100    │ null │ ...  │ null │
     └──────┴──────┴──────────────┴──────┴──────┴──────┘

哈希冲突

哈希函数把无限的输入映射到有限的数组空间，冲突不可避免——不同的键可能算出相同的下标。

解决冲突的两种主流方案：

拉链法（Separate Chaining）——Java HashMap 的选择：

下标 2 处发生冲突（apple 和 grape 算出同一个下标）：

table[2]:  [apple:100] ──► [grape:200] ──► null
           链表或红黑树

查找 grape 时：先到 table[2]，再在链表中逐个比较 key

链表长了查找就退化成 O(n)，所以 Java 8 的 HashMap 在链表长度超过 8 且数组长度 ≥ 64 时，会将链表转为红黑树，把最坏情况从 O(n) 降到 O(log n)。

开放寻址法（Open Addressing）——如 Python dict、Java ThreadLocalMap：

发生冲突时，按照某种探测规则找下一个空位：

线性探测：h, h+1, h+2, h+3, ...
二次探测：h, h+1, h+4, h+9, ...

table:  [_, apple:100, grape:200, _, ...]
              ▲            ▲
           下标 1        下标 2 冲突了，放到下标 3（线性探测改为下标 2 放 grape）

关键操作与复杂度

操作	平均	最坏	说明
插入	O(1)	O(n)	最坏：所有键都冲突到同一个桶
查找	O(1)	O(n)	实际中几乎总是 O(1)
删除	O(1)	O(n)	同上

好的哈希函数的特征

均匀分布：不同的键尽可能映射到不同的下标，减少冲突
计算高效：哈希函数本身要快，不能成为瓶颈
确定性：相同的键必须产生相同的哈希值

Java HashMap 在 hashCode() 的基础上做了一次扰动（将高 16 位异或到低 16 位），让键的分布更均匀：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 高位参与运算，减少只有低位不同的键之间的冲突

Java 映射

数据结构	Java 实现	说明
哈希表	`HashMap`	数组 + 链表 + 红黑树（JDK 8+）
有序哈希表	`LinkedHashMap`	HashMap + 双向链表，保持插入/访问顺序
线程安全哈希表	`ConcurrentHashMap`	分段锁 / CAS，高并发性能优秀
哈希集合	`HashSet`	底层就是 HashMap（value 用一个固定对象占位）

树（Tree）

是什么

树是一种层级结构——一个根节点向下分出多个子节点，每个子节点又可以有自己的子节点，形成"一对多"的关系。

树就像一个家族族谱：一个祖先（根节点）有若干子女（子节点），每个子女又有自己的子女，逐层展开。

基本术语

        A          ← 根节点（root），深度 0
       / \
      B   C        ← A 的子节点，深度 1
     / \   \
    D   E   F      ← 叶子节点（leaf），深度 2
   /
  G                ← 深度 3

节点 B 的：
  - 父节点：A
  - 子节点：D, E
  - 兄弟节点：C
  - 子树：以 B 为根的 {B, D, E, G}

树的高度 = 最大深度 + 1 = 4

二叉树

每个节点最多有两个子节点（左子节点和右子节点）。大多数实际底层场景中涉及的树都是二叉树。

满二叉树：每层都填满       完全二叉树：最后一层靠左填充
       1                        1
      / \                      / \
     2   3                    2   3
    / \ / \                  / \ /
   4  5 6  7                4  5 6

                        （最后一层可以不满，但必须从左到右连续）

二叉搜索树（BST）

在二叉树的基础上加一个约束：左子节点 < 父节点 < 右子节点。这使得查找操作可以像二分查找一样，每次排除一半的节点。

         8
        / \
       3   10
      / \    \
     1   6    14
        / \   /
       4   7 13

查找 7 的过程：
  8 → 7 < 8，往左
  3 → 7 > 3，往右
  6 → 7 > 6，往右
  7 → 找到了！

操作	平均	最坏（退化成链表）
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

最坏情况出现在数据有序插入时——BST 退化成一条链：

顺序插入 1, 2, 3, 4, 5：

  1
   \
    2
     \
      3
       \
        4
         \
          5       ← 变成链表了，查找退化为 O(n)

自平衡二叉树

为了避免退化，我们需要自动保持平衡的树：

类型	平衡策略	应用
AVL 树	左右子树高度差不超过 1，通过旋转调整	查找密集型场景
红黑树	用颜色标记保持近似平衡（最长路径不超过最短路径的 2 倍）	Java `TreeMap`、`TreeSet`
B/B+ 树	多路搜索树，降低树的高度	数据库索引（MySQL InnoDB）

红黑树是 Java 集合框架中使用最广泛的平衡树。它放松了 AVL 的严格平衡要求（不要求高度差 ≤ 1），换来更少的旋转次数——查找略慢，但插入和删除更快，适合频繁增删的场景。

四种遍历方式

        1
       / \
      2   3
     / \
    4   5

前序遍历（根-左-右）：1, 2, 4, 5, 3    ← 用于复制树
中序遍历（左-根-右）：4, 2, 5, 1, 3    ← BST 中得到有序序列
后序遍历（左-右-根）：4, 5, 2, 3, 1    ← 用于删除树、计算目录大小
层序遍历（逐层从左到右）：1, 2, 3, 4, 5  ← 用 BFS + 队列实现

Java 映射

数据结构	Java 实现	说明
红黑树	`TreeMap`	按 key 排序的 Map
红黑树	`TreeSet`	按元素排序的 Set
红黑树	`HashMap` 桶内	链表过长时转为红黑树

堆（Heap）

是什么

堆是一种特殊的完全二叉树，满足堆序性：

最大堆（Max Heap）：父节点 ≥ 子节点，根节点是最大值
最小堆（Min Heap）：父节点 ≤ 子节点，根节点是最小值

堆就像一个金字塔形的排名系统：老板（根节点）的工资最高（或最低），每个经理的工资都高于（或低于）自己的下属，但同级之间不需要排序。

用数组存储的巧妙设计

完全二叉树可以完美地映射到数组，不浪费任何空间：

最小堆示例：

树形表示：                   数组表示：
         1                   [1, 3, 5, 7, 8, 9, 6]
        / \                   0  1  2  3  4  5  6
       3   5
      / \ / \
     7  8 9  6

父子关系公式（下标从 0 开始）：
  父节点下标：(i - 1) / 2
  左子节点下标：2 * i + 1
  右子节点下标：2 * i + 2

这就是为什么堆用数组实现而不用链表——完全二叉树的结构特征让数组能完美表达父子关系，无需指针，省内存又缓存友好。

核心操作

上浮（Sift Up）——插入新元素时：

插入 2 到最小堆 [1, 3, 5, 7, 8, 9, 6]：

步骤1：放到末尾       [1, 3, 5, 7, 8, 9, 6, 2]
步骤2：与父节点比较   2 < 7（父），交换
                      [1, 3, 5, 2, 8, 9, 6, 7]
步骤3：继续上浮       2 < 3（父），交换
                      [1, 2, 5, 3, 8, 9, 6, 7]
步骤4：2 > 1（根），停止

下沉（Sift Down）——删除堆顶时：

删除堆顶（最小值 1）：

步骤1：用末尾元素替换堆顶  [7, 2, 5, 3, 8, 9, 6]
步骤2：7 与较小的子节点比较 7 > 2，交换
                            [2, 7, 5, 3, 8, 9, 6]
步骤3：7 与较小的子节点比较 7 > 3，交换
                            [2, 3, 5, 7, 8, 9, 6]
步骤4：7 没有子节点了，停止

关键操作与复杂度

操作	时间复杂度	说明
获取最大/最小值	O(1)	就是数组的第一个元素
插入	O(log n)	放到末尾 + 上浮
删除堆顶	O(log n)	替换堆顶 + 下沉
建堆（从无序数组）	O(n)	从最后一个非叶子节点开始逐个下沉

常见应用场景

场景	说明
优先队列	总是取优先级最高的元素
Top-K 问题	用大小为 K 的堆维护 K 个最大/最小元素
堆排序	O(n log n) 排序，且原地操作
合并 K 个有序链表	用最小堆维护 K 个链表的当前头节点
任务调度	操作系统用优先队列选择下一个执行的进程

Java 映射

数据结构	Java 实现	说明
最小堆	`PriorityQueue`	默认最小堆，传入 `Comparator.reverseOrder()` 可变为最大堆

图（Graph）

是什么

图是最通用的数据结构——由顶点（Vertex） 和边（Edge） 组成，可以表示任意的多对多关系。树是图的特例（无环连通图），链表也是图的特例（每个节点只有一条出边）。

把图想象成一张城市交通网：城市是顶点，公路是边，有的公路是单行道（有向图），有的是双向的（无向图），有的路比其他路远（带权图）。

图的分类

无向图：          有向图：          带权图：
  A ── B          A ──► B          A ──3── B
  |    |          ▲     |          |       |
  C ── D          C ◄── D          5       2
                                   |       |
 AB 之间可以       A→B 但不能       C ──4── D
 双向通行          B→A             边上有权重（距离/费用等）

存储方式

邻接矩阵——用二维数组表示：

无向图 A-B, A-C, B-D, C-D：

     A  B  C  D
A [  0  1  1  0 ]     1 表示有边，0 表示没边
B [  1  0  0  1 ]
C [  1  0  0  1 ]     对称矩阵（无向图）
D [  0  1  1  0 ]

优点：O(1) 判断两点是否相连
缺点：空间 O(V²)，稀疏图浪费严重

邻接表——每个顶点维护一个邻居列表：

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

优点：空间 O(V + E)，稀疏图很省空间
缺点：判断两点是否相连需要遍历邻居列表

存储方式	空间	查询边	遍历邻居	适用场景
邻接矩阵	O(V²)	O(1)	O(V)	稠密图（边数接近 V²）
邻接表	O(V+E)	O(度)	O(度)	稀疏图（边数远小于 V²）

实际工程中绝大多数图都是稀疏的（社交网络、地图、网页链接），所以邻接表用得更多。

两种遍历方式

BFS（广度优先搜索）——用队列，逐层扩展：

从 A 出发做 BFS：

      A ── B         访问顺序：A → B, C → D, E
      |    |
      C    D ── E

第 0 层：A
第 1 层：B, C（A 的邻居）
第 2 层：D, E（B、C 的未访问邻居）

BFS 适合：最短路径、层序遍历

DFS（深度优先搜索）——用栈（或递归），一条路走到底：

从 A 出发做 DFS（假设先访问编号小的邻居）：

      A ── B         访问顺序：A → B → D → E → C
      |    |
      C    D ── E

先沿 A→B→D→E 走到底，再回溯到 A，再访问 C

DFS 适合：连通性判断、拓扑排序、环检测

常见应用场景

场景	图类型	算法
社交网络好友推荐	无向图	BFS 找共同好友
地图导航最短路	带权有向图	Dijkstra / A*
课程先修关系	有向无环图（DAG）	拓扑排序
网络流量优化	带权有向图	最大流算法
垃圾回收（GC）	有向图	可达性分析（从 GC Roots 做 DFS/BFS）

Java 映射

Java 标准库没有提供通用的图实现，需要自己构建或使用第三方库（如 JGraphT）。常见的自建方式：

// 邻接表表示
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
// ...

全景对比

数据结构	查找	插入	删除	空间	核心优势
数组	O(1) 按下标	O(n)	O(n)	O(n)	随机访问极快
链表	O(n)	O(1) 已知位置	O(1) 已知位置	O(n)	动态增删不移动元素
栈	O(n)	O(1) 栈顶	O(1) 栈顶	O(n)	LIFO 语义
队列	O(n)	O(1) 队尾	O(1) 队头	O(n)	FIFO 语义
哈希表	O(1) 平均	O(1) 平均	O(1) 平均	O(n)	键值查找最快
BST	O(log n) 平均	O(log n) 平均	O(log n) 平均	O(n)	有序 + 高效增删查
堆	O(1) 极值	O(log n)	O(log n)	O(n)	快速取最大/最小值
图	O(V+E)	O(1)	O(V)	O(V+E)	表达复杂关系

怎么选择数据结构

面对一个具体问题时，问自己三个问题：

需要什么操作？ 频繁查找 → 哈希表；频繁取极值 → 堆；需要有序 → 树
数据有什么特征？ 键值对 → 哈希表/树；线性序列 → 数组/链表；层级关系 → 树；网状关系 → 图
需要什么保证？ 排序 → 树；FIFO → 队列；LIFO → 栈；唯一性 → 集合（Set）

没有"最好的"数据结构，只有最适合当前问题的数据结构。

数据结构基础

medium数据结构基础架构必备最近更新

本文聚焦数据结构本身的原理。各数据结构在 Java 集合框架中的具体实现（如 HashMap、ArrayList 等），在本目录的其他文章中有专门的源码级深入分析。

线性结构 vs 非线性结构

在展开讲解之前，先建立一个宏观的分类框架：

数据结构
├── 线性结构（元素之间是一对一的前后关系）
│   ├── 数组（Array）        ← 连续内存，随机访问
│   ├── 链表（Linked List）  ← 离散内存，指针串联
│   ├── 栈（Stack）          ← 受限的线性表，后进先出
│   └── 队列（Queue）        ← 受限的线性表，先进先出
│
└── 非线性结构（元素之间是一对多或多对多关系）
    ├── 哈希表（Hash Table）  ← 键值映射，近似 O(1) 查找
    ├── 树（Tree）           ← 一对多的层级关系
    ├── 堆（Heap）           ← 特殊的树，快速取极值
    └── 图（Graph）          ← 多对多的网状关系

数组（Array）

是什么

数组是最基本的数据结构——一段连续的内存空间，存储相同类型的元素，通过整数下标直接访问。

可以把数组想象成一排编了号的储物柜：每个柜子大小相同，知道编号就能直接打开对应的柜子，不需要从头找起。

内存模型

数组 int[] arr = {10, 20, 30, 40, 50};

内存布局（假设起始地址 0x100，int 占 4 字节）：

地址:    0x100   0x104   0x108   0x10C   0x110
         ┌───────┬───────┬───────┬───────┬───────┐
值:      │  10   │  20   │  30   │  40   │  50   │
         └───────┴───────┴───────┴───────┴───────┘
下标:     [0]     [1]     [2]     [3]     [4]

关键操作与复杂度

操作	时间复杂度	原因
随机访问 `arr[i]`	O(1)	地址计算：`base + i × size`
尾部追加	O(1) 均摊	空间够就直接放；不够则扩容后复制
中间插入 / 删除	O(n)	必须移动后续所有元素来填补空隙
按值查找（无序）	O(n)	只能逐个比较
按值查找（有序）	O(log n)	可以用二分查找

插入的代价

为什么数组中间插入慢？因为必须保持元素的连续性：

在下标 2 处插入 25：

插入前：[10, 20, 30, 40, 50]
                ↓
步骤1 - 后移:  [10, 20, __, 30, 40, 50]   ← 30/40/50 各后移一位
步骤2 - 填入:  [10, 20, 25, 30, 40, 50]   ← 写入新值

n 个元素的数组，在位置 i 插入需要移动 n - i 个元素，平均下来是 O(n)。

扩容机制

Java 映射

数据结构	Java 实现	说明
静态数组	`int[]`, `String[]`	长度固定，不可扩容
动态数组	`ArrayList`	底层是 `Object[]`，自动扩容

链表（Linked List）

是什么

链表是另一种线性结构，但和数组截然不同：元素在内存中不需要连续存放，每个元素（节点）通过指针指向下一个节点，像一条链子一样串起来。

链表的种类

单链表：
  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ data: 10 │    │ data: 20 │    │ data: 30 │
  │ next: ───┼───►│ next: ───┼───►│ next: null│
  └──────────┘    └──────────┘    └──────────┘
  head                                 tail

双向链表：
       ┌──────────────┐    ┌──────────────┐    ┌──────────────┐
       │ prev: null    │◄───┤ prev: ───    │◄───┤ prev: ───    │
       │ data: 10      │    │ data: 20      │    │ data: 30      │
       │ next: ────────┼───►│ next: ────────┼───►│ next: null    │
       └──────────────┘    └──────────────┘    └──────────────┘
       head                                       tail

循环链表：
  ┌──────────┐    ┌──────────┐    ┌──────────┐
  │ data: 10 │    │ data: 20 │    │ data: 30 │
  │ next: ───┼───►│ next: ───┼───►│ next: ───┼──┐
  └──────────┘    └──────────┘    └──────────┘  │
  ▲                                              │
  └──────────────────────────────────────────────┘

关键操作与复杂度

操作	时间复杂度	原因
头部插入 / 删除	O(1)	改两个指针就行
已知节点的插入 / 删除	O(1)	只需修改前后节点的指针
按下标访问	O(n)	必须从头遍历到目标位置
按值查找	O(n)	必须逐个比较

链表插入 vs 数组插入

链表最大的优势就是插入和删除不需要移动元素：

在节点 B 后面插入新节点 X：

插入前：A ──► B ──► C

步骤1：X.next = C           ← 新节点指向后继
步骤2：B.next = X           ← 前驱指向新节点

插入后：A ──► B ──► X ──► C

数组 vs 链表：核心权衡

维度	数组	链表
内存布局	连续	离散
随机访问	O(1) ✅	O(n) ❌
头部插入/删除	O(n) ❌	O(1) ✅
内存利用	可能浪费（预分配）	精确分配（但指针有额外开销）
缓存友好	高（局部性好）	低（节点分散在内存各处）

Java 映射

数据结构	Java 实现	说明
双向链表	`LinkedList`	同时实现了 `List` 和 `Deque` 接口

栈（Stack）

是什么

栈是一种受限的线性结构，只允许在一端（栈顶） 进行插入和删除操作，遵循后进先出（LIFO: Last In First Out）原则。

把栈想象成一摞盘子：你只能从最上面放盘子（入栈 push）和取盘子（出栈 pop），不能从中间抽。

操作示例

操作序列：push(1), push(2), push(3), pop(), push(4), pop()

         ┌───┐     ┌───┐     ┌───┐              ┌───┐
         │   │     │   │     │ 3 │ ← top         │   │
         ├───┤     ├───┤     ├───┤     ┌───┐     ├───┤     ┌───┐
         │   │     │ 2 │     │ 2 │     │ 2 │     │ 4 │     │ 2 │
         ├───┤     ├───┤     ├───┤     ├───┤     ├───┤     ├───┤
         │ 1 │     │ 1 │     │ 1 │     │ 1 │     │ 1 │     │ 1 │
         └───┘     └───┘     └───┘     └───┘     └───┘     └───┘
        push(1)   push(2)   push(3)    pop()    push(4)    pop()
                                      返回 3              返回 4

关键操作与复杂度

操作	时间复杂度	说明
`push(e)` — 入栈	O(1)	在栈顶添加元素
`pop()` — 出栈	O(1)	移除并返回栈顶元素
`peek()` — 查看栈顶	O(1)	返回栈顶元素但不移除

底层实现：数组 vs 链表

栈可以用数组或链表实现：

数组实现：用一个变量 top 记录栈顶位置，push 时 top++，pop 时 top--。优点是缓存友好。
链表实现：栈顶就是链表的头节点，push 时在头部插入，pop 时删除头节点。优点是不需要处理扩容。

常见应用场景

场景	说明
方法调用栈	JVM 用栈帧管理方法调用，每调用一个方法就压入一个栈帧
表达式求值	中缀转后缀、括号匹配
深度优先搜索（DFS）	递归本质上就是用方法调用栈实现的 DFS
浏览器前进/后退	两个栈分别记录历史和前进页面
撤销操作（Undo）	每次操作入栈，撤销时出栈

Java 映射

数据结构	Java 实现	说明
栈	`ArrayDeque`（推荐）	用 `push()` / `pop()` / `peek()`
栈	`Stack`（已过时）	线程安全但性能差

队列（Queue）

是什么

队列也是受限的线性结构，遵循先进先出（FIFO: First In First Out）原则——从队尾入队，从队头出队。

就像排队买奶茶：先到的人先点单，后到的人排在后面。不允许插队，也不允许从队尾出去（那就是"逃跑"了）。

队列的变体

普通队列（FIFO）：
  入队 → [A, B, C, D] → 出队
         队尾          队头

双端队列（Deque）：
  入队 ←→ [A, B, C, D] ←→ 出队
         两端都可以操作

优先队列（Priority Queue）：
  入队 → [按优先级排列] → 出队（总是优先级最高的先出）

关键操作与复杂度

操作	普通队列	优先队列
入队 `offer(e)`	O(1)	O(log n)（堆插入）
出队 `poll()`	O(1)	O(log n)（堆删除）
查看队头 `peek()`	O(1)	O(1)

循环数组实现

用普通数组实现队列有个问题：出队时如果把数组头部的元素删了，后面的元素要不要前移？如果前移就是 O(n)，不移就会浪费前面的空间。

循环数组（Circular Array）解决了这个问题：把数组的首尾"接起来"，用两个指针 head 和 tail 分别追踪队头和队尾的位置：

普通数组的浪费：
  出队几次后        [_, _, _, D, E, F]      ← 前面三格浪费了
                     ▲              ▲
                   浪费了          tail

循环数组的复用：
  容量为 6 的循环数组：

     ┌───┬───┬───┬───┬───┬───┐
     │ G │   │   │ D │ E │ F │
     └───┴───┴───┴───┴───┴───┘
       ▲   ▲       ▲
      tail         head
      (1)         (3)

  tail 绕回到了数组前面，充分利用了空间
  下标计算：next = (current + 1) % capacity

Java 的 ArrayDeque 就是用循环数组实现的，这也是它比 LinkedList 做队列更快的原因——连续内存，缓存友好。

常见应用场景

场景	队列类型	说明
BFS 广度优先搜索	普通队列	层序遍历树/图
任务调度	普通/优先队列	线程池的任务排队
消息队列	阻塞队列	生产者-消费者模式
缓存淘汰（LRU）	双端队列	最近使用的放队头，淘汰队尾
定时任务	延迟队列	到期时间最早的先出队

Java 映射

数据结构	Java 实现	说明
普通队列	`ArrayDeque`（推荐）	循环数组实现
普通队列	`LinkedList`	双向链表实现
优先队列	`PriorityQueue`	小顶堆实现
阻塞队列	`ArrayBlockingQueue`	有界阻塞，线程安全
延迟队列	`DelayQueue`	元素到期后才能出队

哈希表（Hash Table）

是什么

哈希表是一种通过键（Key）直接定位值（Value） 的数据结构。核心思想：用一个哈希函数把键转换成数组下标，从而实现近似 O(1) 的查找。

工作原理

put("apple", 100) 的过程：

1. 计算哈希值：  hash("apple") = 2036578       ← hashCode()
2. 映射到下标：  2036578 % 16 = 2              ← 假设数组长度 16
3. 存入桶：      table[2] = Entry("apple", 100)

get("apple") 的过程：

1. 计算哈希值：  hash("apple") = 2036578       ← 同样的计算
2. 映射到下标：  2036578 % 16 = 2              ← 直达目标位置
3. 取出值：      table[2].value → 100

哈希表内部结构：

下标:  0      1      2              3      ...    15
     ┌──────┬──────┬──────────────┬──────┬──────┬──────┐
     │ null │ null │ apple:100    │ null │ ...  │ null │
     └──────┴──────┴──────────────┴──────┴──────┴──────┘

哈希冲突

哈希函数把无限的输入映射到有限的数组空间，冲突不可避免——不同的键可能算出相同的下标。

解决冲突的两种主流方案：

拉链法（Separate Chaining）——Java HashMap 的选择：

下标 2 处发生冲突（apple 和 grape 算出同一个下标）：

table[2]:  [apple:100] ──► [grape:200] ──► null
           链表或红黑树

查找 grape 时：先到 table[2]，再在链表中逐个比较 key

链表长了查找就退化成 O(n)，所以 Java 8 的 HashMap 在链表长度超过 8 且数组长度 ≥ 64 时，会将链表转为红黑树，把最坏情况从 O(n) 降到 O(log n)。

开放寻址法（Open Addressing）——如 Python dict、Java ThreadLocalMap：

发生冲突时，按照某种探测规则找下一个空位：

线性探测：h, h+1, h+2, h+3, ...
二次探测：h, h+1, h+4, h+9, ...

table:  [_, apple:100, grape:200, _, ...]
              ▲            ▲
           下标 1        下标 2 冲突了，放到下标 3（线性探测改为下标 2 放 grape）

关键操作与复杂度

操作	平均	最坏	说明
插入	O(1)	O(n)	最坏：所有键都冲突到同一个桶
查找	O(1)	O(n)	实际中几乎总是 O(1)
删除	O(1)	O(n)	同上

好的哈希函数的特征

均匀分布：不同的键尽可能映射到不同的下标，减少冲突
计算高效：哈希函数本身要快，不能成为瓶颈
确定性：相同的键必须产生相同的哈希值

Java HashMap 在 hashCode() 的基础上做了一次扰动（将高 16 位异或到低 16 位），让键的分布更均匀：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 高位参与运算，减少只有低位不同的键之间的冲突

Java 映射

数据结构	Java 实现	说明
哈希表	`HashMap`	数组 + 链表 + 红黑树（JDK 8+）
有序哈希表	`LinkedHashMap`	HashMap + 双向链表，保持插入/访问顺序
线程安全哈希表	`ConcurrentHashMap`	分段锁 / CAS，高并发性能优秀
哈希集合	`HashSet`	底层就是 HashMap（value 用一个固定对象占位）

树（Tree）

是什么

树是一种层级结构——一个根节点向下分出多个子节点，每个子节点又可以有自己的子节点，形成"一对多"的关系。

树就像一个家族族谱：一个祖先（根节点）有若干子女（子节点），每个子女又有自己的子女，逐层展开。

基本术语

        A          ← 根节点（root），深度 0
       / \
      B   C        ← A 的子节点，深度 1
     / \   \
    D   E   F      ← 叶子节点（leaf），深度 2
   /
  G                ← 深度 3

节点 B 的：
  - 父节点：A
  - 子节点：D, E
  - 兄弟节点：C
  - 子树：以 B 为根的 {B, D, E, G}

树的高度 = 最大深度 + 1 = 4

二叉树

每个节点最多有两个子节点（左子节点和右子节点）。大多数实际底层场景中涉及的树都是二叉树。

满二叉树：每层都填满       完全二叉树：最后一层靠左填充
       1                        1
      / \                      / \
     2   3                    2   3
    / \ / \                  / \ /
   4  5 6  7                4  5 6

                        （最后一层可以不满，但必须从左到右连续）

二叉搜索树（BST）

在二叉树的基础上加一个约束：左子节点 < 父节点 < 右子节点。这使得查找操作可以像二分查找一样，每次排除一半的节点。

         8
        / \
       3   10
      / \    \
     1   6    14
        / \   /
       4   7 13

查找 7 的过程：
  8 → 7 < 8，往左
  3 → 7 > 3，往右
  6 → 7 > 6，往右
  7 → 找到了！

操作	平均	最坏（退化成链表）
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

最坏情况出现在数据有序插入时——BST 退化成一条链：

顺序插入 1, 2, 3, 4, 5：

  1
   \
    2
     \
      3
       \
        4
         \
          5       ← 变成链表了，查找退化为 O(n)

自平衡二叉树

为了避免退化，我们需要自动保持平衡的树：

类型	平衡策略	应用
AVL 树	左右子树高度差不超过 1，通过旋转调整	查找密集型场景
红黑树	用颜色标记保持近似平衡（最长路径不超过最短路径的 2 倍）	Java `TreeMap`、`TreeSet`
B/B+ 树	多路搜索树，降低树的高度	数据库索引（MySQL InnoDB）

四种遍历方式

        1
       / \
      2   3
     / \
    4   5

前序遍历（根-左-右）：1, 2, 4, 5, 3    ← 用于复制树
中序遍历（左-根-右）：4, 2, 5, 1, 3    ← BST 中得到有序序列
后序遍历（左-右-根）：4, 5, 2, 3, 1    ← 用于删除树、计算目录大小
层序遍历（逐层从左到右）：1, 2, 3, 4, 5  ← 用 BFS + 队列实现

Java 映射

数据结构	Java 实现	说明
红黑树	`TreeMap`	按 key 排序的 Map
红黑树	`TreeSet`	按元素排序的 Set
红黑树	`HashMap` 桶内	链表过长时转为红黑树

堆（Heap）

是什么

堆是一种特殊的完全二叉树，满足堆序性：

最大堆（Max Heap）：父节点 ≥ 子节点，根节点是最大值
最小堆（Min Heap）：父节点 ≤ 子节点，根节点是最小值

堆就像一个金字塔形的排名系统：老板（根节点）的工资最高（或最低），每个经理的工资都高于（或低于）自己的下属，但同级之间不需要排序。

用数组存储的巧妙设计

完全二叉树可以完美地映射到数组，不浪费任何空间：

最小堆示例：

树形表示：                   数组表示：
         1                   [1, 3, 5, 7, 8, 9, 6]
        / \                   0  1  2  3  4  5  6
       3   5
      / \ / \
     7  8 9  6

父子关系公式（下标从 0 开始）：
  父节点下标：(i - 1) / 2
  左子节点下标：2 * i + 1
  右子节点下标：2 * i + 2

这就是为什么堆用数组实现而不用链表——完全二叉树的结构特征让数组能完美表达父子关系，无需指针，省内存又缓存友好。

核心操作

上浮（Sift Up）——插入新元素时：

插入 2 到最小堆 [1, 3, 5, 7, 8, 9, 6]：

步骤1：放到末尾       [1, 3, 5, 7, 8, 9, 6, 2]
步骤2：与父节点比较   2 < 7（父），交换
                      [1, 3, 5, 2, 8, 9, 6, 7]
步骤3：继续上浮       2 < 3（父），交换
                      [1, 2, 5, 3, 8, 9, 6, 7]
步骤4：2 > 1（根），停止

下沉（Sift Down）——删除堆顶时：

删除堆顶（最小值 1）：

步骤1：用末尾元素替换堆顶  [7, 2, 5, 3, 8, 9, 6]
步骤2：7 与较小的子节点比较 7 > 2，交换
                            [2, 7, 5, 3, 8, 9, 6]
步骤3：7 与较小的子节点比较 7 > 3，交换
                            [2, 3, 5, 7, 8, 9, 6]
步骤4：7 没有子节点了，停止

关键操作与复杂度

操作	时间复杂度	说明
获取最大/最小值	O(1)	就是数组的第一个元素
插入	O(log n)	放到末尾 + 上浮
删除堆顶	O(log n)	替换堆顶 + 下沉
建堆（从无序数组）	O(n)	从最后一个非叶子节点开始逐个下沉

常见应用场景

场景	说明
优先队列	总是取优先级最高的元素
Top-K 问题	用大小为 K 的堆维护 K 个最大/最小元素
堆排序	O(n log n) 排序，且原地操作
合并 K 个有序链表	用最小堆维护 K 个链表的当前头节点
任务调度	操作系统用优先队列选择下一个执行的进程

Java 映射

数据结构	Java 实现	说明
最小堆	`PriorityQueue`	默认最小堆，传入 `Comparator.reverseOrder()` 可变为最大堆

图（Graph）

是什么

把图想象成一张城市交通网：城市是顶点，公路是边，有的公路是单行道（有向图），有的是双向的（无向图），有的路比其他路远（带权图）。

图的分类

无向图：          有向图：          带权图：
  A ── B          A ──► B          A ──3── B
  |    |          ▲     |          |       |
  C ── D          C ◄── D          5       2
                                   |       |
 AB 之间可以       A→B 但不能       C ──4── D
 双向通行          B→A             边上有权重（距离/费用等）

存储方式

邻接矩阵——用二维数组表示：

无向图 A-B, A-C, B-D, C-D：

     A  B  C  D
A [  0  1  1  0 ]     1 表示有边，0 表示没边
B [  1  0  0  1 ]
C [  1  0  0  1 ]     对称矩阵（无向图）
D [  0  1  1  0 ]

优点：O(1) 判断两点是否相连
缺点：空间 O(V²)，稀疏图浪费严重

邻接表——每个顶点维护一个邻居列表：

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

优点：空间 O(V + E)，稀疏图很省空间
缺点：判断两点是否相连需要遍历邻居列表

存储方式	空间	查询边	遍历邻居	适用场景
邻接矩阵	O(V²)	O(1)	O(V)	稠密图（边数接近 V²）
邻接表	O(V+E)	O(度)	O(度)	稀疏图（边数远小于 V²）

实际工程中绝大多数图都是稀疏的（社交网络、地图、网页链接），所以邻接表用得更多。

两种遍历方式

BFS（广度优先搜索）——用队列，逐层扩展：

从 A 出发做 BFS：

      A ── B         访问顺序：A → B, C → D, E
      |    |
      C    D ── E

第 0 层：A
第 1 层：B, C（A 的邻居）
第 2 层：D, E（B、C 的未访问邻居）

BFS 适合：最短路径、层序遍历

DFS（深度优先搜索）——用栈（或递归），一条路走到底：

从 A 出发做 DFS（假设先访问编号小的邻居）：

      A ── B         访问顺序：A → B → D → E → C
      |    |
      C    D ── E

先沿 A→B→D→E 走到底，再回溯到 A，再访问 C

DFS 适合：连通性判断、拓扑排序、环检测

常见应用场景

场景	图类型	算法
社交网络好友推荐	无向图	BFS 找共同好友
地图导航最短路	带权有向图	Dijkstra / A*
课程先修关系	有向无环图（DAG）	拓扑排序
网络流量优化	带权有向图	最大流算法
垃圾回收（GC）	有向图	可达性分析（从 GC Roots 做 DFS/BFS）

Java 映射

Java 标准库没有提供通用的图实现，需要自己构建或使用第三方库（如 JGraphT）。常见的自建方式：

// 邻接表表示
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
// ...

全景对比

数据结构	查找	插入	删除	空间	核心优势
数组	O(1) 按下标	O(n)	O(n)	O(n)	随机访问极快
链表	O(n)	O(1) 已知位置	O(1) 已知位置	O(n)	动态增删不移动元素
栈	O(n)	O(1) 栈顶	O(1) 栈顶	O(n)	LIFO 语义
队列	O(n)	O(1) 队尾	O(1) 队头	O(n)	FIFO 语义
哈希表	O(1) 平均	O(1) 平均	O(1) 平均	O(n)	键值查找最快
BST	O(log n) 平均	O(log n) 平均	O(log n) 平均	O(n)	有序 + 高效增删查
堆	O(1) 极值	O(log n)	O(log n)	O(n)	快速取最大/最小值
图	O(V+E)	O(1)	O(V)	O(V+E)	表达复杂关系

怎么选择数据结构

面对一个具体问题时，问自己三个问题：

需要什么操作？ 频繁查找 → 哈希表；频繁取极值 → 堆；需要有序 → 树
数据有什么特征？ 键值对 → 哈希表/树；线性序列 → 数组/链表；层级关系 → 树；网状关系 → 图
需要什么保证？ 排序 → 树；FIFO → 队列；LIFO → 栈；唯一性 → 集合（Set）

没有"最好的"数据结构，只有最适合当前问题的数据结构。