数据结构基础

开篇：数据结构是算法的地基

学算法之前，先要把数据结构搞清楚。选对了数据结构，算法往往就呼之欲出；选错了，再精妙的算法也写不出优雅的代码。

本文从最基础的线性结构（数组、链表、栈、队列）出发，一路讲到树、图、堆，每个结构都配上 Java 代码和面试高频考点。目标不是面面俱到，而是帮你建立一张数据结构的心智地图——拿到一道题，能迅速判断该用什么结构。

---

一、线性结构

线性结构是最基础的数据结构，也是所有复杂结构的构建基石。面试中关于线性结构的考察不会太难，但作为基础一定要扎实。

1.1 数组 vs 链表

从存储方式上看，数组和链表是两个极端：

• 数组：连续内存，支持 O(1) 随机访问，但插入/删除需要移动元素。大小固定，申请时就确定。
• 链表：不连续内存，每个节点存储数据 + 指向下一个节点的指针。插入/删除只需修改指针（O(1)），但查找必须从头遍历（O(n)）。

比较项	数组	链表
内存连续	是	否
随机访问	O(1) 通过下标	O(n) 需遍历
按值查找	O(n)，有序数组可 O(log n)	O(n)
插入/删除	O(n)，需移动元素	O(1)，修改指针
空间	可能浪费（预分配）	额外存指针

链表还有几种变体值得了解：

• 双向链表：每个节点同时存储前驱和后继指针，支持双向遍历。Java 的 LinkedList 就是双向链表实现。
• 环形链表：尾节点指向头节点（或中间某个节点），形成环。判断链表是否有环是经典面试题——用快慢指针，快指针每次走两步、慢指针每次走一步，如果存在环，它们最终一定会相遇。

1.2 栈和队列

栈和队列的区别只有一个：栈是先进后出（LIFO），队列是先进先出（FIFO）。

从实现角度看，栈通常用数组实现（操作集中在一端，数组的尾部操作是 O(1)），队列通常用链表实现（需要在两端操作）。

栈的数组实现：

class StackByArray {
    private int top = -1;
    private int maxSize;
    private int[] stack;

    public StackByArray(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public boolean isFull() { return top == maxSize - 1; }
    public boolean isEmpty() { return top == -1; }

    public void push(int data) {
        if (isFull()) return;
        stack[++top] = data;
    }

    public int pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return stack[top--];
    }
}

栈的链表实现：

class StackByLink {
    private Node head;

    public void push(int data) {
        Node temp = new Node(data);
        if (head != null) temp.next = head;
        head = temp;
    }

    public int pop() {
        if (head == null) return 0;
        int ans = head.data;
        head = head.next;
        return ans;
    }

    private static class Node {
        public int data;
        public Node next;
        public Node(int data) { this.data = data; }
    }
}

队列的链表实现：

class QueueByLink {
    Node front;
    Node tail;
    int size;

    public void offer(int data) {
        Node temp = new Node(data);
        if (isEmpty()) {
            front = temp;
            tail = front;
        } else {
            tail.next = temp;
            tail = temp;
        }
        size++;
    }

    public int poll() {
        if (isEmpty()) return 0;
        int data = front.data;
        front = front.next;
        size--;
        return data;
    }

    public boolean isEmpty() { return size == 0; }

    private static class Node {
        public int data;
        public Node next;
        public Node(int data) { this.data = data; }
    }
}

在 Java 中，日常使用的写法是：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.pop();

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.poll();

栈的应用：递归的底层实现就是调用栈；JVM 方法执行时会压入栈帧；括号匹配、表达式求值也离不开栈。

队列的应用：消息队列（生产者-消费者模型）、BFS 遍历、缓冲区，这些场景都需要先进先出的特性。

1.3 双端队列和循环队列

双端队列（Deque） 打破了栈和队列的单端限制，允许在两端插入和删除：

Deque<Integer> deque = new LinkedList<>();
deque.offerFirst(1);  // 头部插入
deque.offerLast(2);   // 尾部插入
deque.pollFirst();    // 头部删除
deque.pollLast();     // 尾部删除

循环队列 解决了数组实现队列时的"假溢出"问题。普通数组队列中，当尾指针到达数组末尾时，即使前面有空位也无法使用。循环队列通过取模运算让数组空间循环利用：

class CircularQueue {
    private final int[] items;
    private int head = 0, tail = 0;

    public CircularQueue(int length) {
        this.items = new int[length];
    }

    public boolean push(int data) {
        if (((tail + 1) % items.length) == head) return false; // 满了
        items[tail] = data;
        tail = (tail + 1) % items.length;
        return true;
    }

    public int pop() {
        int data = items[head];
        head = (head + 1) % items.length;
        return data;
    }
}

循环队列在实际工程中经常作为缓冲区使用——如果 index 超出，直接覆盖旧数据就行。

---

二、树结构

树是面试中的重头戏。从基础的二叉树遍历到 B+ 树、红黑树，几乎每场面试都会涉及。

2.1 树的分类概览

先建立一个全局认知，了解不同树结构各自擅长什么：

• 二叉搜索树（BST）：左子树所有节点小于根，右子树所有节点大于根。中序遍历结果有序。最坏情况退化为链表。
• 平衡二叉树（AVL）：严格平衡的 BST，任何节点的左右子树高度差不超过 1。查找快但更新代价高。
• 红黑树：近似平衡的 BST，通过颜色规则保证最长路径不超过最短路径的两倍。Java 的 HashMap（链表转树时）和 TreeMap 都用红黑树。
• B 树 / B+ 树：多路搜索树，用于数据库索引。通过增大节点"宽度"降低树的高度，减少磁盘 I/O。
• 前缀树（Trie）：用于字符串集合的高效检索，共享公共前缀以节省空间。
• 哈夫曼树：用于数据的无损压缩（哈夫曼编码），大学数据结构必修内容，面试一般不考。

2.2 二叉树遍历：递归 + 迭代两种写法

面试官问二叉树遍历时，递归写法只是入门。他们真正想考的是用栈/队列实现的迭代写法——因为递归谁都会写，但你是否真正理解了遍历的过程，要通过迭代实现来检验。

前序遍历（根 -> 左 -> 右）

递归版本是基线，先确保你能秒写：

List<Integer> output = new ArrayList<>();
private void preOrder(TreeNode node) {
    if (node == null) return;
    output.add(node.val);
    preOrder(node.left);
    preOrder(node.right);
}

迭代版本的思路：用栈模拟递归。根节点入栈，出栈时先把右孩子入栈、再把左孩子入栈（因为栈是后进先出，所以左孩子会先被处理）。

public List<Integer> preorderWithStack(TreeNode root) {
    List<Integer> output = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) return output;
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        output.add(node.val);
        if (node.right != null) stack.push(node.right); // 先右
        if (node.left != null) stack.push(node.left);   // 再左
    }
    return output;
}

中序遍历（左 -> 根 -> 右）

递归：

List<Integer> ints = new ArrayList<>();
private void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    ints.add(node.val);
    inOrder(node.right);
}

迭代版本是三种遍历中最需要理解的。关键思路：先沿左子树一路走到底，把沿途节点全部压栈；然后出栈处理当前节点，再转向它的右子树，重复这个过程。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {    // 一路向左，全部压栈
            stack.push(node);
            node = node.left;
        }
        TreeNode temp = stack.pop();
        list.add(temp.val);       // 处理当前节点
        node = temp.right;        // 转向右子树
    }
    return list;
}

后序遍历（左 -> 右 -> 根）

递归：

List<Integer> ints = new ArrayList<>();
private void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    ints.add(node.val);
}

迭代版本需要两个栈。思路：用第一个栈做类似前序的处理但顺序改为"根-右-左"，把结果压入第二个栈，最后从第二个栈依次弹出，顺序自然变成"左-右-根"。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ints = new ArrayList<>();
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    if (root == null) return ints;
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);                               // 不直接输出，压入第二个栈
        if (node.left != null) stack1.push(node.left);   // 先左
        if (node.right != null) stack1.push(node.right); // 再右
    }
    while (!stack2.isEmpty()) ints.add(stack2.pop().val);
    return ints;
}

层序遍历（BFS）

用队列实现。每一层的节点全部出队处理，同时把它们的子节点入队，逐层推进。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> list = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null) queue.offer(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> ints = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            TreeNode node = queue.poll();
            ints.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        list.add(ints);
    }
    return list;
}

2.3 深度优先 vs 广度优先

这两个概念不仅适用于树，也适用于图，甚至更广泛的搜索问题。

• DFS（深度优先）：一条路走到底，走不通再回退。树的前序、中序、后序遍历都属于 DFS。底层数据结构是栈（递归调用本身就是隐式地使用了系统调用栈）。
• BFS（广度优先）：先把当前层的所有邻居都访问完，再进入下一层。树的层序遍历就是 BFS。底层数据结构是队列。

选择 DFS 还是 BFS 取决于问题：需要找最短路径用 BFS，需要探索所有可能路径用 DFS。

2.4 B 树与 B+ 树

B 树和 B+ 树是数据库索引的核心数据结构。B 是 Balanced（平衡）的首字母。

B 树是一种多路平衡搜索树，每个节点可以有多个子节点和多个关键字。它的设计目标是减少磁盘 I/O——通过增加每个节点的"宽度"（存更多 key），降低树的高度，从而减少查找时的磁盘访问次数。

一棵 m 阶 B 树满足：

• 每个节点最多 m 个子节点
• 非叶子节点（除根）至少有 ceil(m/2) 个子节点
• 根节点至少 2 个子节点（非叶时）
• 有 k 个子节点的非叶节点包含 k-1 个关键字
• 所有叶子在同一层（这是"平衡"的体现）

B 树的关键字和数据可以存储在任何节点上，搜索可能在非叶节点就结束。

B+ 树是 B 树的变体，有两个关键区别：

1. 数据只存在叶子节点。非叶子节点只存索引信息（key 的副本），这意味着非叶节点能存更多 key，树更矮。
2. 叶子节点之间用指针相连，形成有序双向链表，范围查询时只需沿链表扫描即可，效率极高。

MySQL InnoDB 使用 B+ 树做索引，MongoDB 使用 B 树——因为 MongoDB 更侧重点查询，而 MySQL 需要大量范围查询。

2.5 红黑树

红黑树是一种自平衡的二叉搜索树，通过节点颜色（红/黑）和五条规则来保证树的大致平衡：

1. 每个节点要么红要么黑
2. 根节点是黑色
3. 红色节点的子节点必须是黑色（红色不能相邻）
4. 每个叶子节点（NIL 空节点）是黑色
5. 从任一节点到其所有叶子的路径上，黑色节点数量相同

这五条规则保证了最长路径不超过最短路径的两倍（最长路径是红黑交替，最短路径是全黑），因此所有操作的最坏时间复杂度都是 O(log n)。

与 AVL 树相比，红黑树不追求严格平衡，所以插入/删除时需要的旋转操作更少，更新性能更好。这就是为什么实际工程中（如 Java HashMap、TreeMap）更倾向于用红黑树而不是 AVL 树。

插入时的自平衡通过变色 + 旋转实现，核心看叔叔节点的颜色：

• 叔叔是红色 -> 直接变色：父亲和叔叔变黑，祖父变红，然后对祖父递归处理
• 叔叔是黑色且新节点在内侧 -> 先旋转成外侧情况
• 叔叔是黑色且新节点在外侧 -> 父亲变黑，祖父变红，对祖父旋转

记不住所有情况没关系，面试时只要能说清"通过变色和旋转来维持五条性质"就足够了。

2.6 前缀树（Trie）

前缀树是一种专门用于字符串检索的树形结构。它的核心思想是共享公共前缀：多个字符串如果前缀相同，就共用同一段路径。

比如 abc, bac, bbc, ca 四个字符串，bac 和 bbc 共享 b 这个前缀节点。查询一个长度为 m 的字符串，时间复杂度从哈希表的 O(m)（计算哈希值）没有本质区别，但 Trie 的优势在于前缀匹配和空间压缩——大量有公共前缀的字符串，Trie 能节省大量空间。

class Trie {
    private Trie[] children;
    private boolean isWord;

    public Trie() {
        this.isWord = false;
        this.children = new Trie[26]; // 26 个小写字母
    }

    public void insert(String word) {
        Trie next = this;
        for (char c : word.toCharArray()) {
            if (next.children[c - 'a'] == null) {
                next.children[c - 'a'] = new Trie();
            }
            next = next.children[c - 'a'];
        }
        next.isWord = true;
    }

    public boolean search(String word) {
        Trie next = this;
        for (char c : word.toCharArray()) {
            if (next.children[c - 'a'] == null) return false;
            next = next.children[c - 'a'];
        }
        return next.isWord; // 必须是完整单词
    }

    public boolean startsWith(String prefix) {
        Trie next = this;
        for (char c : prefix.toCharArray()) {
            if (next.children[c - 'a'] == null) return false;
            next = next.children[c - 'a'];
        }
        return true; // 前缀存在即可
    }
}

前缀树的常见应用：

• 搜索引擎的自动补全：输入前缀，快速找到所有匹配的词
• 拼写检查：判断一个词是否在词典中
• 字符串排序：对 Trie 做先序遍历，输出顺序就是字典序
• 词频统计：大量有公共前缀的字符串，Trie 比 HashMap 更省空间
• IP 路由的最长前缀匹配

---

三、图结构

图是用来表示多对多关系的数据结构，由顶点（vertex）和边（edge）组成。社交网络、交通网络、依赖关系都是图的典型应用场景。

3.1 有向图与无向图

• 无向图：边没有方向。A-B 表示 A 和 B 互相可达。适合表示对等关系，如友谊、合作。
• 有向图：边有方向。A->B 表示从 A 到 B 有路径，但 B 到 A 不一定有。适合表示单向关系，如关注、依赖。

还有有权图和无权图的区别：有权图的边附带权重（可以是距离、成本、时间等），无权图的边只表示是否连接。最短路径问题在有权图上用 Dijkstra，在无权图上直接用 BFS。

3.2 图的存储方式

邻接矩阵：二维数组 matrix[i][j] 表示节点 i 到节点 j 是否有边（或边的权重）。

• 优点：O(1) 判断两个节点是否相连
• 缺点：空间 O(V^2)，稀疏图会浪费大量空间
• 对于无向图，矩阵是对称的

邻接表：每个节点维护一个列表，存储与它直接相连的节点。

• 优点：空间 O(V+E)，适合稀疏图
• 缺点：判断两点是否相连需要遍历链表

实际工程中，大多数图是稀疏的，所以邻接表用得更多。

3.3 图的遍历：DFS 与 BFS

DFS：从起点出发，沿着一条路径尽可能深入，走到头（遇到已访问节点或死路）再回溯，尝试下一条路径。需要一个 visited 数组防止重复访问。用栈或递归实现。

BFS：从起点出发，先访问所有距离为 1 的邻居，再访问距离为 2 的邻居，逐层扩展。用队列实现。BFS 天然适合求无权图的最短路径——第一次到达某个节点时，经过的层数就是最短距离。

---

四、堆与优先队列

这里的"堆"是数据结构中的堆，和 JVM 内存中的堆区没有任何关系。

4.1 什么是堆

堆是一种特殊的完全二叉树，有两种形式：

• 大顶堆（大根堆）：任意节点的值都大于或等于其子节点的值。堆顶是最大值。
• 小顶堆（小根堆）：任意节点的值都小于或等于其子节点的值。堆顶是最小值。

因为是完全二叉树，堆可以用数组高效存储，不需要指针。对于下标为 i 的节点：

• 父节点下标：(i-1)/2
• 左孩子下标：2*i+1
• 右孩子下标：2*i+2

4.2 堆的核心操作

插入（上浮 / Heapify Up）：新元素放到数组末尾（完全二叉树的最后一个位置），然后和父节点比较。以小顶堆为例，如果比父节点小就交换，一直往上冒泡，直到满足堆的性质或到达堆顶。

删除堆顶（下沉 / Heapify Down）：把堆顶元素和数组末尾元素交换，删除末尾（原堆顶），然后新的堆顶和它较小的子节点比较（小顶堆），如果比子节点大就交换，一直往下沉，直到满足堆的性质或到达叶子。

两个操作的时间复杂度都是 O(log n)。

4.3 堆的应用场景

堆的用武之地非常广泛，这里列出面试中最常被问到的几个：

1. 优先队列：Java 的 PriorityQueue 底层就是小顶堆。O(log n) 插入，O(1) 获取最小值。
2. Top K 问题：从海量数据中找最大的 K 个数，用大小为 K 的小顶堆（详见下面的专题）。
3. 堆排序：先建大顶堆，然后不断把堆顶（最大值）和末尾交换并缩小堆，最终数组有序。时间 O(N log N)，空间 O(1)。
4. 定时器：用小顶堆管理定时事件，堆顶永远是最近要触发的任务。从堆顶不断取出并执行。
5. Dijkstra 算法：用小顶堆（优先队列）作为辅助结构，每次取出当前距离最小的节点进行松弛。
6. TP99 计算：维护一个大顶堆（存 99% 的请求时间）和一个小顶堆（存 1%），保持两者的比例为 99:1。大顶堆的堆顶就是 TP99 值。新数据到来时，根据大小决定放入哪个堆，再调整比例。

4.4 Top K 问题详解

这是堆最经典的面试题。问题：从海量数据中找最大的 K 个数。

用小顶堆，而不是大顶堆。原因：小顶堆只需维护 K 个元素，空间 O(K)；大顶堆需要存储全量数据，空间 O(N)。当 N 是十亿级别时，这个差距是致命的。

算法步骤：

1. 初始化一个大小为 K 的小顶堆
2. 遍历数据流中的每个元素：
   • 堆未满：直接入堆
   • 堆已满且元素大于堆顶：替换堆顶，重新堆化
   • 堆已满且元素不大于堆顶：丢弃
3. 遍历结束，堆中的 K 个元素就是最大的 K 个数

每次插入操作 O(log K)，总时间 O(N log K)。而且这个方法支持动态数据流——不需要一次性加载所有数据到内存。

4.5 位图（BitMap）

位图的思想极简：用一个 bit 来标记一个元素是否存在。

一个 bit 只有 0 和 1 两种状态，但占用的空间极小。存储 1、4、6 三个整数，用普通 int 数组需要 12 字节（96 bit），用位图只需要 1 字节（8 bit）就可以覆盖 0-7 的范围。

位图最大的优势是极致的空间效率，特别适合：

• 去重：每个数字对应一个 bit，遇到就置 1，已经是 1 的就是重复的
• 排序：遍历位图，输出值为 1 的位的编号，天然有序
• 判断存在性：O(1) 时间判断某个数字是否存在

布隆过滤器（Bloom Filter） 是位图思想的扩展：用 K 个哈希函数将元素映射到位数组的 K 个位置。查询时检查所有位置是否都为 1——都为 1 则"可能存在"（有误判），只要有一个为 0 则"一定不存在"。用极小的内存实现海量数据的存在性判断。

位图的限制：只能表示"存在/不存在"的二值状态，无法存储其他信息。

---

五、常见面试题精选

5.1 海量数据找 Top K，为什么用小顶堆

上文已经详细讲了 Top K 的算法。这里再强调面试中必须说清楚的一点：为什么用小顶堆而不是大顶堆。

大顶堆的做法是把所有数据都放进堆，然后依次弹出 K 个最大值。问题是当数据量是十亿级别时，你根本放不下。

小顶堆只维护 K 个元素，堆顶是这 K 个中最小的。新来一个数如果比堆顶大，说明它有资格进入 Top K，替换掉堆顶；如果比堆顶小，说明它连 Top K 中最小的都不如，直接丢弃。

5.2 什么时候选什么数据结构

这张表是面试和日常开发中最实用的决策参考：

需求	推荐数据结构	原因
快速查找/去重	HashMap / HashSet	O(1) 查找
有序数据 + 范围查询	TreeMap / 红黑树	O(log n) 有序操作
频繁头部插入/删除	LinkedList	O(1) 头部操作
Top K / 优先级调度	堆 / PriorityQueue	O(log K) 维护
字符串前缀匹配	前缀树（Trie）	O(m) 查询，共享前缀
海量数据判存在	位图 / 布隆过滤器	极小内存
数据库索引	B+ 树	低树高，范围查询快
无权图最短路径	BFS	层序天然最短
有权图最短路径	Dijkstra（堆优化）	O((V+E) log V)

---

小结

数据结构的学习没有捷径，但有方法。建议按这个优先级建立知识体系：

1. 先掌握线性结构：数组、链表、栈、队列。它们是所有复杂结构的基础，也是面试的热身题。
2. 重点突破树结构：二叉树遍历（递归 + 迭代必须都会写）是基本功；BST 的中序遍历性质要能灵活运用；红黑树和 B+ 树不需要手写代码，但核心思想和应用场景要说得清楚。
3. 理解堆和优先队列：Top K 问题、堆排序、TP99 计算这些场景都离不开堆。PriorityQueue 的使用要熟练。
4. 图作为拓展：DFS/BFS 的代码模板要熟，Dijkstra 等最短路径算法了解思想即可。

面试时，数据结构题最忌讳的是"只说名字不说原理"。比如问你"什么是红黑树"，不要只回答"一种自平衡的二叉搜索树"，要能说清楚它的五条规则以及为什么这些规则能保证近似平衡——面试官要的是你对底层原理的理解深度。

---

附录：数据结构复杂度速查

数据结构	查找	插入	删除	空间
数组	O(1) 下标 / O(n) 值	O(n)	O(n)	O(n)
链表	O(n)	O(1) 已知位置	O(1) 已知位置	O(n)
栈	O(n)	O(1) push	O(1) pop	O(n)
队列	O(n)	O(1) offer	O(1) poll	O(n)
哈希表	O(1) 平均	O(1) 平均	O(1) 平均	O(n)
BST	O(log n) 平均	O(log n) 平均	O(log n) 平均	O(n)
AVL 树	O(log n)	O(log n)	O(log n)	O(n)
红黑树	O(log n)	O(log n)	O(log n)	O(n)
B+ 树	O(log n)	O(log n)	O(log n)	O(n)
堆	O(1) 最值 / O(n) 任意	O(log n)	O(log n) 堆顶	O(n)
前缀树	O(m) m=字符串长	O(m)	O(m)	O(字符总数)