常用数据结构

这篇是整个教程中最重要的一篇。算法题的本质就是对数据结构进行操作，如果你不熟悉 Java 标准库提供的这些数据结构，看算法代码就会一头雾水。

好消息是，你不需要记住每个数据结构的所有 API，只需要掌握最常用的那几个方法就够了。用多了自然就记住了，忘了随时可以回来查。

有一点需要提前说明：不同数据结构的同一个操作，效率可能差很多。比如 ArrayList 按索引取值很快，但在头部插入元素就很慢；LinkedList 正好反过来。选错数据结构或者调错方法，算法题可能会超时。

不过本篇先专注于用法，不深入讲时间复杂度。具体的复杂度分析和底层实现原理，会在后面的数据结构章节详细展开。

¶数组

数组是最基本的数据结构，大小固定，通过下标（索引）访问元素。

数组和后面要讲的 ArrayList 的区别是：数组大小固定，创建后不能增删元素；ArrayList 大小可变，可以动态增删。算法题中两者都非常常用。

¶二维数组

二维数组就是「数组的数组」，常用来表示矩阵或网格：

¶Arrays 工具类

java.util.Arrays 提供了一些操作数组的常用方法：

¶字符串

Java 中字符串用 String 类表示。和 char 不同，String 用双引号，char 用单引号。

¶String 的不可变性

String 对象一旦创建就不能修改。所有看起来在「修改」字符串的操作，实际上都是创建了一个新的字符串：

String s = "hello";
s = s + " world";  // 不是修改 s，而是创建了新字符串 "hello world"，让 s 指向它

¶常用方法

特别强调：比较两个字符串是否相等一定要用 equals() 方法，不要用 ==。因为 == 比较的是两个变量是否指向同一个对象，而不是内容是否相同。这是 Java 新手最常踩的坑之一。

¶StringBuilder

因为 String 不可变，每次拼接都会创建新对象。如果需要频繁拼接字符串（比如在循环中），用 StringBuilder 效率更高：

¶字符与 ASCII 码

char 类型本质上是一个整数，可以和 int 互相转换：

¶List：ArrayList 与 LinkedList

数组大小固定，不太方便。Java 标准库提供了 ArrayList（动态数组）和 LinkedList（双链表），它们都实现了 List 接口，可以动态增删元素。关于数组和链表的底层原理，后面的 数组基本原理 和 链表基本原理 会详细讲解，这里先学会怎么用就行。

¶ArrayList

ArrayList 是最常用的集合类，底层就是一个自动扩容的数组：

注意泛型里只能写引用类型，不能写基本类型。所以是 ArrayList<Integer> 而不是 ArrayList<int>。Integer 是 int 的包装类，Java 会自动在两者之间转换（后面的「算法题常用技巧」一章会详细讲）。

¶LinkedList

LinkedList 是双链表实现，在头尾增删元素效率比 ArrayList 高：

简单记：需要频繁在头部增删时用 LinkedList，其他场景一律用 ArrayList。

¶Map：HashMap 与 TreeMap

Map 存储键值对（key-value），通过 key 快速查找 value。这里只讲用法，关于哈希表的底层原理，后面的 哈希表核心原理 会详细讲解；关于 TreeMap 的底层原理，可以看 二叉搜索树的应用。

¶HashMap

HashMap 是最常用的 Map 实现，增删查改效率都很高：

getOrDefault 在算法题中特别好用，比如统计字符出现次数时：

// 统计每个字符出现的次数
HashMap<Character, Integer> count = new HashMap<>();
for (char c : "hello".toCharArray()) {
    count.put(c, count.getOrDefault(c, 0) + 1);
}

¶TreeMap

TreeMap 和 HashMap 的 API 基本一样，区别是 TreeMap 的 key 是有序的（按照 key 的自然顺序排列），并且提供了一些额外的方法来利用这个有序性：

TreeMap 的增删查改比 HashMap 慢一些，但在需要有序性的场景下很有用。

¶Set：HashSet 与 TreeSet

Set 存储不重复的元素，主要用来去重和判断元素是否存在。

TreeSet 和 HashSet 的关系类似 TreeMap 和 HashMap：TreeSet 中的元素是有序的，也提供了 first()、last()、floor()、ceiling() 等方法，用法和 TreeMap 类似，这里就不重复了。

¶Queue 与 Deque

¶Queue（队列）

队列是先进先出（FIFO）的数据结构，Java 中用 LinkedList 来实现 Queue 接口。关于栈和队列的底层原理，后面的 队列/栈基本原理 会详细讲解，这里先学会怎么用：

队列常用的就三个方法：offer（入队）、poll（出队）、peek（看队头）。

¶Deque（双端队列）

Deque 是双端队列，两头都可以进出。ArrayDeque 是它最常用的实现：

¶PriorityQueue（优先队列）

PriorityQueue 基于二叉堆实现，每次 poll 出来的都是当前最小的元素（默认小顶堆），在 Dijkstra 最短路径、合并 K 个有序链表等算法题中大量使用。关于二叉堆的底层原理，后面的 二叉堆核心原理 会详细讲解。

¶Stack（栈）

栈是后进先出（LIFO）的数据结构，核心操作就三个：push（入栈）、pop（出栈）、peek（看栈顶）。

Java 标准库中的 Stack 类继承自 Vector，带有不必要的同步开销，官方更推荐用 Deque<Integer> stack = new ArrayDeque<>() 来实现栈。不过 Stack 的 API 更直观（push/pop/peek），用来刷题完全没问题。

¶小结

把这篇的数据结构和它们的核心方法汇总一下：

不需要一次记住所有方法，用多了自然就熟了。下一篇会讲一些算法题中的实用技巧，比如排序、类型转换等。