基本数据结构：数组、链表、栈、队列、哈希表

这一课你将能做到

1. 说出数组、链表、栈、队列、哈希表的核心特性和适用场景
2. 手写链表反转、栈模拟括号匹配、哈希表统计词频
3. 在判题中正确选择数据结构解决具体问题

为什么要学

这五种数据结构是编程世界的「积木」。数组是默认选择，链表解决动态插入，栈处理嵌套结构，队列保证公平顺序，哈希表实现极速查找。不会它们，就像厨师不会用刀。

人话：数组是连续停车位，链表是寻宝游戏（每个节点指向下一个），栈是叠盘子（后进先出），队列是排队买票（先进先出），哈希表是字典（拼音查字）。

先建立图像

数组:  [1][2][3][4][5]        ← 连续内存，下标直达
链表:  [1]→[2]→[3]→[4]→[5]   ← 指针串联，顺序访问
栈:    [3]← top               ← 后进先出 (LIFO)
       [2]
       [1]
队列:  [1]→[2]→[3]→[4]→[5]   ← 先进先出 (FIFO)
       front           rear
哈希表: key → hash → bucket   ← 键值对，O(1) 查找

跟着做

步骤 1：数组——最基础的结构

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};
        Arrays.sort(arr);                    // 排序
        int idx = Arrays.binarySearch(arr, 8); // 二分查找
        System.out.println(Arrays.toString(arr)); // [1, 2, 5, 8, 9]
        System.out.println("8 在位置: " + idx);
    }
}

数组特点：查询 O(1)，插入删除 O(n)，大小固定。

步骤 2：链表——动态插入删除

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        // 反转链表
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 输出: 3 -> 2 -> 1
        while (prev != null) {
            System.out.print(prev.val + " ");
            prev = prev.next;
        }
    }
}

链表特点：插入删除 O(1)，查询 O(n)，内存不连续。

步骤 3：栈——括号匹配

import java.util.Stack;

public class Main {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isValid("()[]{}")); // true
        System.out.println(isValid("(]"));     // false
    }
}

栈特点：push/pop O(1)，只能操作栈顶。

步骤 4：队列——BFS 基础

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);  // 入队
        queue.offer(2);
        queue.offer(3);
        
        while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " "); // 出队: 1 2 3
        }
    }
}

队列特点：offer/poll O(1)，先进先出。

步骤 5：哈希表——词频统计

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

public class Main {
    public static void main(String[] args) {
        String[] words = {"apple", "banana", "apple", "orange", "banana", "apple"};
        Map<String, Integer> count = new HashMap<>();
        
        for (String w : words) {
            count.put(w, count.getOrDefault(w, 0) + 1);
        }
        
        count.forEach((k, v) -> System.out.println(k + ": " + v));
        // apple: 3, banana: 2, orange: 1
    }
}

哈希表特点：查找/插入/删除平均 O(1)，需要处理哈希冲突。

步骤 6：Deque——双端队列实战

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

public class Main {
    public static void main(String[] args) {
        // 用 Deque 同时当栈和队列
        Deque<Integer> deque = new ArrayDeque<>();
        
        // 当栈用（后进先出）
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque.pop()); // 3
        
        // 当队列用（先进先出）
        deque.offer(4);
        deque.offer(5);
        System.out.println(deque.poll()); // 1
        
        // 双端操作
        deque.addFirst(0);
        deque.addLast(6);
        System.out.println(deque); // [0, 2, 4, 5, 6]
    }
}

Deque 是本站判题中最常用的结构，滑动窗口、单调栈、BFS 都靠它。

讲清楚要点

1. 时间复杂度对比：数组查询 O(1) 插入 O(n)；链表查询 O(n) 插入 O(1)；哈希表平均 O(1) 最坏 O(n)。
2. 内存占用：数组最省；链表每个节点多一个指针；哈希表有负载因子，通常浪费 25% 空间。
3. Java 集合选择：ArrayList 替代数组，LinkedList 替代链表（实际很少用），Deque 替代栈和队列，HashMap/HashSet 是主力。
4. 判题场景：排行榜用堆/有序集合，缓存用哈希表，表达式解析用栈，消息队列用队列。

你可能会懵的地方

• ArrayList 和 LinkedList 怎么选？ 99% 场景用 ArrayList。LinkedList 只在频繁在头部插入删除时有优势，但缓存不友好，实际性能常常更差。

• Stack 类和 Deque 接口用哪个？ 官方推荐用 Deque（ArrayDeque 实现），Stack 是历史遗留，基于 Vector，有同步开销。

• HashMap 的初始容量设多少？ 默认 16，如果知道要存 1000 个元素，设 new HashMap<>(2048) 避免 rehash。

• 哈希冲突怎么解决？ Java 用链地址法：冲突元素挂到同一个桶的链表上，Java 8+ 在链表长度超过 8 时转红黑树。

• 为什么 LinkedList 查询慢？ 必须从头遍历，无法随机访问。即使知道索引，也要走 O(n)。

错法对照

错法	问题	正解
用数组频繁在中间插入	每次移动后面所有元素 O(n)	改用链表或 ArrayList 的 subList
用 LinkedList 按下标查询	每次 O(n)，n 大时 TLE	改用 ArrayList 或数组
用 Stack 类做高并发	Vector 同步开销大	用 Deque + ArrayDeque
HashMap 不预估容量	频繁 rehash 性能差	初始化时给足容量
在循环中删除 ArrayList 元素	会漏删或抛异常	用迭代器或倒序遍历

卡点急救

1. 链表操作断链：画图！先画原链表，再画操作后的样子，最后写代码。
2. 栈溢出：递归深度超过 10^4 就危险，改迭代或显式栈。
3. 哈希表 Key 乱序：HashMap 不保证顺序，需要顺序用 LinkedHashMap，需要排序用 TreeMap。

面试常问

• 数组和链表的区别？ 数组连续内存，随机访问 O(1)，插入删除 O(n)；链表指针串联，插入删除 O(1)，查询 O(n)。数组缓存友好，链表内存利用率高。

• 哈希表怎么实现 O(1) 查找？ 哈希函数把 key 映射到桶下标，理想情况下直接定位。冲突时用链表或红黑树挂起来。负载因子控制在 0.75 以下。

• 栈在 JVM 中的应用？ 每个线程有独立的虚拟机栈，方法调用就是栈帧的压栈弹栈。栈溢出（StackOverflowError）就是递归太深导致。

自测三问

1. 数组和链表在插入删除操作上的时间复杂度分别是多少？
2. Java 中为什么推荐用 Deque 而不是 Stack？
3. HashMap 在 Java 8 中链表长度超过多少会转红黑树？

小结一句话

数组、链表、栈、队列、哈希表是编程的五大基础积木，理解它们的特性和复杂度，是写出高效代码的第一步。

延伸

• Java 集合框架官方文档
• 下一课：算法复杂度分析——Big O 表示法与性能评估。