常见数据结构

数据结构（Data Structure）是计算机中存储、组织数据的方式。选择合适的数据结构可以显著提升算法的效率和代码的可读性。

分类概览

数据结构
├── 线性结构
│   ├── 数组（Array）
│   ├── 链表（Linked List）
│   │   ├── 单向链表
│   │   ├── 双向链表
│   │   └── 循环链表
│   ├── 栈（Stack）
│   ├── 队列（Queue）
│   │   ├── 普通队列
│   │   ├── 双端队列
│   │   └── 优先队列
│   └── 哈希表（Hash Table）
├── 树形结构
│   ├── 二叉树（Binary Tree）
│   │   ├── 二叉搜索树（BST）
│   │   ├── 平衡二叉树（AVL）
│   │   ├── 红黑树（Red-Black Tree）
│   │   └── 堆（Heap）
│   ├── 多路树
│   │   ├── B 树
│   │   └── B+ 树
│   └── 其他
│       ├── 前缀树（Trie）
│       └── 线段树（Segment Tree）
├── 图形结构
│   ├── 有向图
│   ├── 无向图
│   └── 加权图
└── 高级/特殊结构
    ├── 布隆过滤器（Bloom Filter）
    ├── 并查集（Union-Find）
    ├── LRU 缓存（Least Recently Used）
    └── 跳表（Skip List）

---

数组（Array）

定义

数组是连续内存空间中存储相同类型元素的集合，通过**下标（索引）**随机访问。

特性

特性	说明
内存布局	连续内存块，元素依次排列
访问速度	O(1) — 通过索引直接计算内存地址
插入/删除	O(n) — 需要移动后续元素
搜索	O(n) — 未排序；O(log n) — 已排序（二分查找）

适用场景

• 需要快速随机访问的场景（如矩阵运算、查找表）
• 数据规模固定或变化不频繁

链表（Linked List）

定义

链表由一系列节点组成，每个节点包含数据和指向下一个（或上一个）节点的指针。

类型对比

类型	结构	特点
单向链表	data → next	只能从头到尾遍历
双向链表	prev ↔ data ↔ next	可双向遍历，Java LinkedList
循环链表	尾节点指向头节点	适用于环形调度

特性

操作	时间复杂度
访问	O(n)
头部插入	O(1)
尾部插入（有尾指针）	O(1)
中间插入	O(n)
删除	O(1)（已知节点）

适用场景

• 频繁插入/删除的场景
• 无法预先确定数据量
• 实现栈、队列等结构的基础

栈（Stack）

定义

后进先出（LIFO, Last In First Out）的线性结构。

入栈 → [底部 ... 顶部] → 出栈

基本操作

操作	说明	时间复杂度
push(x)	元素入栈	O(1)
pop()	弹出栈顶元素	O(1)
peek()	查看栈顶元素	O(1)
isEmpty()	检查是否为空	O(1)

常见应用

• 函数调用栈 — 递归调用、方法嵌套
• 括号匹配 — {[()]} 有效性检查
• 表达式求值 — 中缀转后缀
• 撤销操作 — Ctrl+Z
• 浏览器后退 — 页面历史

代码示例

import java.util.ArrayDeque;
import java.util.Deque;

// 使用 Deque 作为栈（推荐，比 Stack 类更快）
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.push("C");
System.out.println(stack.pop()); // C
System.out.println(stack.peek()); // B

队列（Queue）

定义

先进先出（FIFO, First In First Out）的线性结构。

入队 → [尾部 ... 头部] → 出队

基本操作

操作	说明	时间复杂度
offer(x)	元素入队	O(1)
poll()	出队	O(1)
peek()	查看队首	O(1)

常见应用

• 任务队列 — 线程池、消息队列
• BFS（广度优先搜索）
• 缓冲区 — IO 缓冲、打印队列

双端队列（Deque）

可在两端插入/删除：

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A");
deque.addLast("B");
deque.removeFirst();
deque.removeLast();

优先队列（Priority Queue）

元素按优先级出队，底层通常用堆实现。

// 小顶堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
System.out.println(minHeap.poll()); // 1

哈希表（Hash Table）

定义

通过哈希函数将键（Key）映射到数组索引，实现 O(1) 的查找、插入、删除。

工作原理

键（Key） → 哈希函数 → 哈希值 → 数组索引 → 值（Value）

解决哈希冲突

方法	说明
链地址法	每个桶用链表/树存储冲突元素（Java HashMap）
开放地址法	冲突时寻找下一个空位
再哈希法	使用多个哈希函数

Java HashMap 演进

JDK 版本	实现
JDK 7	数组 + 链表
JDK 8+	数组 + 链表 / 红黑树（链表长度 ≥ 8 时树化）

适用场景

• 快速查找（字典、缓存）
• 去重统计
• 索引映射

二叉树（Binary Tree）

定义

每个节点最多有两个子节点（左子节点、右子节点）。

      A
     / \
    B   C
   / \   \
  D   E   F

遍历方式

遍历方式	顺序	结果
前序	根 → 左 → 右	A B D E C F
中序	左 → 根 → 右	D B E A C F
后序	左 → 右 → 根	D E B F C A
层序	逐层从左到右	A B C D E F

二叉搜索树（BST）

左子树所有节点 < 根节点 < 右子树所有节点。

      5
     / \
    3   8
   / \   \
  2   4   9

操作	平均	最坏
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

平衡二叉树（AVL）

严格平衡 — 任意节点的左右子树高度差 ≤ 1。

• 通过旋转（左旋、右旋、左右旋、右左旋）保持平衡
• 适合读多写少的场景

红黑树

近似平衡的二叉搜索树，Java TreeMap、HashMap 使用。

规则：

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 叶子节点（NIL）是黑色
4. 红色节点的子节点必须是黑色
5. 任意节点到叶子的所有路径包含相同数量的黑节点

特性	AVL	红黑树
平衡程度	严格平衡	近似平衡
查询	更快	略慢
插入/删除	较慢（旋转多）	更快（旋转少）
适用场景	查询密集型	插入/删除频繁

堆（Heap）

完全二叉树，用于实现优先队列。

类型	特性
大顶堆	父节点 ≥ 子节点，根最大
小顶堆	父节点 ≤ 子节点，根最小

操作	时间复杂度
插入	O(log n)
删除根	O(log n)
建堆	O(n)

应用：

• 堆排序（O(n log n)）
• Top K 问题（如最大的 10 个数）
• 合并 K 个有序链表

B 树与 B+ 树

B 树

多路平衡查找树，每个节点包含多个键和子节点，广泛应用在数据库和文件系统中。

          [10, 20]
         /    |    \
    [5,8]  [15,18] [25,30]

特性：

• 所有叶子节点在同一层
• 每个节点可存储多个键
• 保持平衡，高度可控

B+ 树

B 树的变体，MySQL InnoDB 索引底层结构。

           [10, 20]          ← 索引节点（仅存键）
          /    |    \
     [5,8] [15,18] [25,30]    ← 叶子节点（存数据+链表指针）
      ↓      ↓       ↓
     ──── 链表连接 ──── →     ← 范围查询高效

特点：

特性	B 树	B+ 树
数据存储	所有节点	仅叶子节点
叶子节点连接	不连接	链表连接
范围查询	较差	极快
单记录查询	可能更快	需要到叶子

图（Graph）

定义

由**顶点（Vertex）和边（Edge）**组成的数据结构。

    A ── B
    │    │
    C ── D

分类

类型	说明
无向图	边没有方向，A-B
有向图	边有方向，A→B
加权图	边带有权重（距离、成本等）
连通图	任意两点都有路径

存储方式

方式	说明	适用场景
邻接矩阵	N×N 二维数组	稠密图
邻接表	每个顶点一个链表	稀疏图

常见算法

算法	用途	复杂度
DFS（深度优先搜索）	遍历、连通分量、拓扑排序	O(V+E)
BFS（广度优先搜索）	最短路径（无权图）	O(V+E)
Dijkstra	单源最短路径（加权）	O((V+E)logV)
Floyd-Warshall	全源最短路径	O(V³)
Kruskal / Prim	最小生成树	O(ElogE)

代码示例

import java.util.*;

// 邻接表表示的图
public class Graph {
    private int V; // 顶点数
    private List<Integer>[] adj; // 邻接表

    public Graph(int v) {
        V = v;
        adj = new List[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u); // 无向图
    }

    // BFS
    public void bfs(int start) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            System.out.print(curr + " ");
            for (int next : adj[curr]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
    }
}

其他常用结构

前缀树（Trie）

用于高效存储和检索字符串集合中的键。

        root
       / | \
      a  b  c
     /   |   \
    p    e    a
   /     |     \
  p      g      t
   \
    l

应用：

• 自动补全 / 拼写检查
• IP 路由前缀匹配
• 词典搜索

布隆过滤器（Bloom Filter）

概率性数据结构，用于判断元素一定不在或可能在集合中。

特性	说明
空间	极小，比哈希表省 90%+
误判率	可能误判"存在"，但不会误判"不存在"
删除	不支持

应用：

• Redis 缓存穿透防护
• 爬虫 URL 去重
• 垃圾邮件过滤

LRU 缓存（Least Recently Used）

淘汰最久未使用的数据。

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

跳表（Skip List）

基于多级索引的链表，支持 O(log n) 的查找。

Level 3: 1 ───────────────────→ 9
Level 2: 1 ─────→ 5 ─────→ 9
Level 1: 1 ─→ 3 ─→ 5 ─→ 7 ─→ 9
Level 0: 1 → 2 → 3 → ... → 9

应用：Redis Zset（有序集合） 的底层实现。

并查集（Union-Find）

用于处理不相交集合的合并与查询。

class UnionFind {
    int[] parent;
    int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        // 按秩合并
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
    }
}

数据结构选择指南

需求场景	推荐数据结构
快速随机访问	数组
频繁插入/删除	链表
后进先出	栈
先进先出	队列
快速查找	哈希表
有序数据	二叉搜索树、跳表
范围查询	B+ 树
优先级调度	堆（优先队列）
层级关系	树、图
自动补全	前缀树（Trie）
空间敏感的去重	布隆过滤器
LRU 淘汰	LinkedHashMap

各语言内置数据结构

Java

结构	实现类
动态数组	ArrayList
链表	LinkedList
栈	ArrayDeque（推荐）、Stack
队列	LinkedList、ArrayDeque
优先队列	PriorityQueue
哈希表	HashMap、HashSet
有序映射	TreeMap（红黑树）
有序集合	TreeSet（红黑树）

JavaScript

结构	实现方式
动态数组	Array（原生）
栈/队列	Array（push/pop/shift）
哈希表	Map、Set、Object
优先队列	需手动实现或用第三方库

Python

结构	实现方式
动态数组	list
栈/队列	list、collections.deque
哈希表	dict、set
优先队列	heapq（堆）、queue.PriorityQueue
有序映射	sortedcontainers（第三方库）