数据结构

这一课你将能做到

1. 说出数组、链表、栈、队列、哈希表、树、图各自的增删查代价与典型用途
2. 面对一个业务需求，能在 Java 集合框架中选对 ArrayList / ArrayDeque / HashMap / TreeMap / LinkedHashSet
3. 能手写链表反转、二叉树层序遍历，并解释哈希冲突的两种处理方式

为什么要学

数据结构是「摆放数据的方式」。同样的数据，摆法不同，同一个操作可能从 1 毫秒变成 10 秒。判题平台里处处是这种选择：

• 题目标签列表用 ArrayList 还是 LinkedList？
• 判题机实例池、题目提交计数、相似题关系图分别该用什么结构？

框架不会替你做这些决定。而面试中超过一半的算法题，考的其实就是「认出该用哪个结构」。本课把七种核心结构一次讲透，并落到 Java 17 集合框架的真实选择上。

先建立图像

线性结构（一对一）
数组 ArrayList  [A][B][C][D] 连续内存  随机访问 O(1)，中间增删 O(n)
链表 LinkedList A→B→C→D 零散内存+指针 访问 O(n)，已知节点增删 O(1)
栈 Stack：LIFO  push/pop        ← 函数调用、括号匹配
队列 Queue：FIFO offer/poll      ← 任务排队、连接池
双端队列 Deque：两端可进出（开发中用它模拟栈和队列）

非线性结构
哈希表：key ──hash()──▶ 桶下标，平均 O(1)；冲突时桶内挂链表/红黑树
树（一对多）：二叉搜索树「左小右大」，平衡后查找 O(log n)
图（多对多）：顶点+边，邻接矩阵/邻接表
   题A ─── 题B（相似）   题C ─── 题D

记忆主线：数组和链表是两块地基，栈和队列是受限的线性表，哈希表是「数组 + 哈希函数」的组合，树和图是在它们之上表达层级与关系。

跟着做

步骤 1：对比数组与链表的真实代价

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListBench {
    public static void main(String[] args) {
        int n = 100_000;
        List<Integer> array = new ArrayList<>();
        List<Integer> linked = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            array.add(i);
            linked.add(i);
        }

        long t1 = System.nanoTime();
        for (int i = 0; i < n; i++) {
            array.get(i);                       // 按下标取：数组 O(1)
        }
        long t2 = System.nanoTime();
        for (int i = 0; i < n; i++) {
            linked.get(i);                      // 按下标取：链表要从头数，O(n)
        }
        long t3 = System.nanoTime();

        System.out.println("ArrayList 随机访问(ms): " + (t2 - t1) / 1_000_000);
        System.out.println("LinkedList 随机访问(ms): " + (t3 - t2) / 1_000_000);
    }
}

你会看到数量级的差距。业务里多数场景是「遍历、按下标取、末尾追加」，正是 ArrayList 的主场；链表的价值在「已知节点的 O(1) 增删」以及实现 LRU（第 12 课）。

步骤 2：手写链表反转（面试第一高频题）

public class ReverseList {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    // 迭代：用三个指针逐个翻转指向
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;   // 先存好下一个
            curr.next = prev;            // 翻转指针
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        ListNode r = reverse(head);
        while (r != null) {
            System.out.print(r.val + " ");   // 3 2 1
            r = r.next;
        }
    }
}

要点：链表题的通用套路是「画图 + 用指针保存现场」，先保 next 再改指向，否则链表会断。

步骤 3：栈与队列——用 ArrayDeque，别用 Stack/LinkedList

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

public class StackQueueDemo {
    public static void main(String[] args) {
        // 当栈用：判题平台用栈检查用户代码括号是否匹配
        Deque<Character> stack = new ArrayDeque<>();
        String code = "public class A { void f() { int[] a = {1}; } }";
        for (char c : code.toCharArray()) {
            if (c == '{' || c == '(' || c == '[') {
                stack.push(c);
            } else if (c == '}' || c == ')' || c == ']') {
                if (!stack.isEmpty()) stack.pop();
            }
        }
        System.out.println("括号是否全部闭合: " + stack.isEmpty());

        // 当队列用：offer/poll，提交任务排队等待空闲判题机
    }
}

注意：java.util.Stack 继承自 Vector，全部方法加 synchronized，又慢又过时；队列用 LinkedList 也能跑，但 ArrayDeque 基于数组、缓存友好，是 JDK 官方推荐的栈和双端队列实现。

步骤 4：哈希表与冲突处理

import java.util.HashMap;
import java.util.Map;

public class MapDemo {
    public static void main(String[] args) {
        // key=题目ID，value=AC 提交数
        Map<Long, Long> acCount = new HashMap<>();
        acCount.merge(1L, 1L, Long::sum);
        acCount.merge(1L, 1L, Long::sum);
        acCount.merge(2L, 1L, Long::sum);
        System.out.println(acCount);   // {1=2, 2=1}

        System.out.println(acCount.getOrDefault(99L, 0L));   // 不存在给默认值 0
    }
}

底层直觉：HashMap 用 key 的 hashCode() 扰动后取模定位桶；同桶即哈希冲突，两类解法：

• 链地址法（HashMap 采用）：桶内挂链表，过长（≥8）且表够大时转红黑树
• 开放寻址法：冲突后按规则找下一个空桶，ThreadLocal 用此法，缓存友好但怕聚集

步骤 5：树的层序遍历（判题机按层调度任务的模板）

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

public class TreeBfs {

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public static void levelOrder(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();              // 关键：先记下当前层的节点数
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            System.out.println();                  // 每一层换行
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        levelOrder(root);                          // 1 / 2 3
    }
}

图遍历只需加 Set<Node> visited 防环；社交关系、相似题推荐、调用链都用邻接表。

讲清楚要点

1. 数组赢在随机访问和缓存友好：下标直接算地址（基地址 + 下标 × 元素大小）；代价是中间插入要挪动、扩容要整体拷贝。
2. 链表赢在已知节点的增删：改两个指针即可；代价是不能随机访问、节点额外占内存、缓存不友好。
3. 栈和队列是「受限的线性表」：限制入口出口换取语义清晰——编译器用栈处理调用与括号，系统用队列调度任务。
4. 哈希表用空间换时间：平均 O(1) 依赖好的哈希函数、合理的负载因子（默认 0.75 扩容）、不可变 key。
5. 平衡树让「有序 + 快速」兼得：红黑树查找 O(log n)，范围查询用 TreeMap；数据库 B+ 树思想同源。图用邻接表（稀疏）或邻接矩阵（稠密）。

你可能会懵的地方

• HashMap 的 key 为 null 会怎样？为什么自定义对象当 key 要重写两个方法？ HashMap 允许一个 null key，固定放 0 号桶。自定义对象当 key 必须同时重写 hashCode() 和 equals()：hashCode 决定进哪个桶，equals 决定是不是同一个 key。只重写 equals 会出现「逻辑相等的两个对象查不到值」。

• 栈内存和「栈」这种数据结构是一回事吗？ 有关联但不是一个层面的概念。JVM 的虚拟机栈是线程私有的内存区域，它用栈这种 LIFO 结构管理一个个方法调用的栈帧；数据结构课讲的栈是抽象逻辑工具。

• 数组下标为什么从 0 开始？ 下标本质是「相对首地址的偏移量」，首元素偏移 0，所以地址 = base + index × size，省去一次减法。C 语言定下的惯例，Java 沿袭。

• 二叉搜索树什么时候会退化？ 按有序顺序插入（1、2、3、4、5…）时，树退化成一条链表，查找从 O(log n) 变 O(n)。红黑树、AVL 树通过旋转保持平衡来解决，所以工程代码永远用平衡树而不裸用 BST。

• 为什么实际代码里几乎不用 LinkedList？ 「缓存不友好 + 每节点对象开销」常抵消理论上的插入优势；LinkedHashMap、跳表才是链表思想真正的落脚点。

错法对照

错法	问题	正解
for-each 遍历中直接 list.remove(x)	触发 ConcurrentModificationException	用 Iterator.remove() 或 removeIf()
用可变对象当 HashMap 的 key，put 后再修改它	hashCode 变化，数据「丢」在桶里找不回	key 用不可变对象，或保证放入后不再改
new HashMap<>() 不预估容量，塞百万数据	反复扩容 rehash，性能差	已知大小时 new HashMap<>(expected / 0.75f + 1)
用 Stack 或 Vector 求新	同步开销大、设计过时	ArrayDeque 当栈；需要并发用 ConcurrentHashMap 等
图遍历不带 visited	有环时无限循环	用 Set/boolean[] 记录已访问节点

卡点急救

1. 并发更新 Map 出现数据丢失或异常：HashMap 线程不安全，不要靠「Collections.synchronizedMap 包一下就万事大吉」（复合操作仍不原子）；判题统计这类并发计数用 ConcurrentHashMap + merge/compute。
2. 集合里查元素慢：检查是否在循环里反复 List.contains()（O(n²) 雏形）；判重改用 HashSet。
3. 树/图递归栈溢出：判题服务执行用户递归代码时深递归可能爆栈；自己写遍历可改成基于 ArrayDeque 的迭代写法，或对递归深度做前置校验。

面试常问

• ArrayList 和 LinkedList 的区别？什么场景下 LinkedList 更快？ 数组连续内存，随机访问 O(1)、中间增删 O(n)；链表节点带指针，随机访问 O(n)、已知节点增删 O(1)。理论上频繁在头部/已知位置增删时链表快，但工程上 ArrayList 凭借缓存友好常常反超，所以默认选 ArrayList。

• HashMap 底层原理讲一下。 数组 + 链表/红黑树；key 经 hashCode 扰动定位桶；冲突用链地址法，链表长度到 8 且数组容量到 64 转红黑树，缩到 6 退化为链表；负载因子 0.75，容量翻倍扩容；1.8 后尾插且并发依然不安全，多线程用 ConcurrentHashMap。

• 栈和队列各自的工程应用？ 栈：调用栈、括号匹配、撤销、DFS；队列：任务排队、连接池、BFS。判题平台的提交排队就是队列语义。

自测三问

1. 不看资料，列出七种结构的「查找 / 头部插入 / 中间插入」复杂度表。
2. 为什么判题统计适合 HashMap 而排行榜需要 TreeMap 或堆？各写出一句理由。
3. 哈希冲突的两种解法各自怕什么？HashMap 为什么要在链表和红黑树之间互相转换？

小结一句话

数据结构没有银弹，本质是在「连续还是分散、有序还是无序、一对一还是多对多」之间做权衡——看清操作模式（查多还是改多、要不要顺序、要不要去重），选择就自然浮现。

延伸

• OpenJDK：Collections Framework 官方指南——集合框架每个类的契约与复杂度的权威说明
• VisuAlgo 数据结构可视化——链表、树、哈希表演练的直观工具
• 《算法（第 4 版）》配套站点——Java 描述的数据结构经典，Red Book 正身
• 下一课：算法与搜索排序——有了摆放数据的方式，接下来学习操作它们的步骤：排序、二分、BFS/DFS 与高频解题模式。