数据结构

这一课你将能做到

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;
        }
    }
}