Java标准库数据结构的基本用法

目前我的算法教程基本上都是用 Java 语言写的代码，主要有以下几个原因：

1、Java 是强类型语言。因为我们就是要学习运用各种数据结构写算法嘛，所以清楚地知道每个变量是什么类型非常重要，方便你 debug，也方便 IDE 进行语法检查。如果是 Python 这样的动态语言，每个变量的类型不明显，可能有碍大家的理解。

2、Java 这种语言中规中矩，没有什么语法糖，即便之前没学过 Java 语言，单看代码也能理解逻辑。所以如果你有其他比较熟悉的语言，完全可以根据我的解法代码用自己的语言实现。

对于一些不怎么熟悉 Java 的小伙伴，初学时肯定会有一点吃力。不过不用担心，下面我会讲讲学习我的算法教程所需的 Java 基本用法，以便不了解 Java 的小伙也能伴顺畅地学习我的文章。

首先，Java 的基本语法可以参考这个网站的教程，我就不重复造轮子了：

https://www.runoob.com/java/java-tutorial.html

我圈出的这一部分是 Java 的基本用法，当然这个网站也有其他的 Java 基础知识，你有空也可以快速浏览一下：

下面我介绍一下我在教程中会用到的 Java 的标准库的数据结构以及一些可能踩坑的语言特性。

Java 标准库数据结构的基本用法

Java 中最基本的数据类型叫 Primitive Type（原始类型），比如 int, char, long, boolean 这种小写字母的关键字。大家应该都学过 C 语言，所以对于原始类型应该不陌生，因为 C 语言里几乎只有原始类型，连字符串都只能用 char[] 字符数组来表示，只能使用指针进行操作，使用起来非常不方便。

当然，作为高级编程语言，Java 提供了很多高级数据类型，都封装成了标准库中的类（Java 中类的名字都以大写字母开头），比如 Java 中的字符串就是 String 类，这个类有 length(), substring() 等方法，这样我们就不用管底层的操作细节，使用起来方便多了。我会在数据结构精品课会中带大家实现标准库中的常见数据结构类，深入理解其底层的实现细节，帮助大家更深入地理解常用数据结构。

以下是一些基本的 Java 类型。

1、数组。

初始化方法：

int m = 5, n = 10;

// 初始化一个大小为 10 的 int 数组
// 其中的值默认初始化为 0
int[] nums = new int[n]

// 初始化一个 m * n 的二维布尔数组
// 其中的元素默认初始化为 false
boolean[][] visited = new boolean[m][n];

作为原始类型，这就类似 C 语言的 int 数组，操作起来比较麻烦，所以我们更多地使用 ArrayList 动态数组，后面的视频课会详细讲解。

2、字符串 String

Java 的字符串处理起来挺麻烦的，因为它不支持用 [] 直接访问其中的字符，而且不能直接修改，要转化成 char[] 类型才能修改。主要说下 String 中我们会用到的一些特性：

String s1 = "hello world";
// 获取 s1[2] 那个字符 l
char c = s1.charAt(2);

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
// 输出：hallo world
System.out.println(s2);

// 注意，一定要用 equals 方法判断字符串是否相同
if (s1.equals(s2)) {
    // s1 和 s2 相同
} else {
    // s1 和 s2 不相同
}

// 字符串可以用加号进行拼接
String s3 = s1 + "!";
// 输出：hello world!
System.out.println(s3);

Java 的字符串不能直接修改，要用 toCharArray 转化成 char[] 的数组进行修改，然后再转换回 String 类型。

另外，虽然字符串支持用 + 进行拼接，但是效率并不高，并不建议在 for 循环中使用。如果需要进行频繁的字符串拼接，推荐使用 StringBuilder/StringBuffer：

StringBuilder sb = new StringBuilder();

for (char c = 'a'; c <= 'f'; c++) {
    sb.append(c);
}

// append 方法支持拼接字符、字符串、数字等类型
sb.append('g').append("hij").append(123);

String res = sb.toString();
// 输出：abcdefghij123
System.out.println(res);

还有一个重要的问题就是字符串的相等性比较，这个问题涉及语言特性，简单说就是一定要用字符串的 equals 方法比较两个字符串是否相同，不要用 == 比较，否则可能出现不易察觉的 bug。

3、动态数组 ArrayList

ArrayList 相当于把 Java 内置的数组类型做了包装，初始化方法：

// 初始化一个存储 String 类型的动态数组
ArrayList<String> nums = new ArrayList<>();

// 初始化一个存储 int 类型的动态数组
ArrayList<Integer> strings = new ArrayList<>();

常用的方法如下（E 代表元素类型）：

// 判断数组是否为空
boolean isEmpty()

// 返回数组的元素个数
int	size()

// 返回索引 index 的元素
E get(int index)

// 在数组尾部添加元素 e
boolean	add(E e)

我们做算法题时这些最简单的方法就够用了，你应该看一眼就能明白。如果你对这些数据结构的底层实现感兴趣，我会在数据结构精品课中讲解。

4、双链表 LinkedList

ArrayList 列表底层是数组实现的，而 LinkedList 底层是双链表实现的，初始化方法也是类似的：

// 初始化一个存储 int 类型的双链表
LinkedList<Integer> nums = new LinkedList<>();

// 初始化一个存储 String 类型的双链表
LinkedList<String> strings = new LinkedList<>();

一般算法题中我们会用到以下方法（E 代表元素类型）：

// 判断链表是否为空
boolean	isEmpty()

// 返回链表的元素个数
int	size()

// 判断链表中是否存在元素 o
boolean	contains(Object o)

// 在链表尾部添加元素 e
boolean	add(E e)

// 在链表尾部添加元素 e
void addLast(E e)

// 在链表头部添加元素 e
void addFirst(E e)

// 删除链表头部第一个元素
E removeFirst()

// 删除链表尾部最后一个元素
E removeLast()

这些也都是最简单的方法，和 ArrayList 不同的是，我们更多地使用了 LinkedList 对于头部和尾部元素的操作，因为底层数据结构为链表，直接操作头尾的元素效率较高。其中只有 contains 方法的时间复杂度是 O(N)，因为必须遍历整个链表才能判断元素是否存在。

在数据结构精品课中我们会亲自实现一个 MyLinkedList 类，之后你就会理解每个方法的时间复杂度了。

5、哈希表 HashMap

哈希表是非常常用的数据结构，用来存储键值对映射，初始化方法：

// 整数映射到字符串的哈希表
HashMap<Integer, String> map = new HashMap<>();

// 字符串映射到数组的哈希表
HashMap<String, int[]> map = new HashMap<>();

在算法题中，我们只会用以下几个基本方法（K 代表键的类型，V 代表值的类型）：

// 判断哈希表中是否存在键 key
boolean	containsKey(Object key)

// 获得键 key 对应的值，若 key 不存在，则返回 null
V get(Object key)

// 将 key, value 键值对存入哈希表
V put(K key, V value)

// 如果 key 存在，删除 key 并返回对应的值
V remove(Object key)

在数据结构精品课中，我会手把手带你实现 MyHashMap 类，深入理解和实现两种处理哈希冲突的方法。

6、哈希集合 HashSet

初始化方法：

1 2	// 新建一个存储 String 的哈希集合 Set<String> set = new HashSet<>();

我们可能在算法题中用到的方法（E 表示元素类型）：

// 如果 e 不存在，则添加 e 到哈希集合
boolean	add(E e)

// 判断元素 o 是否存在于哈希集合中
boolean	contains(Object o)

// 如果元素 o 存在，在删除元素 o
boolean	remove(Object o)

等你实现了 MyHashMap，就知道 HashSet 底层和 HashMap 其实是一样的。

Java 类的一些基本用法

首先说一下泛型编程。泛型是 Java 提供的一种模板，能够将数据结构的实现和数据类型解耦。

比如说我们在使用 LinkedList 双链表的时候，可以随意设置其中的元素类型。不过需要注意，在泛型中只能使用类，不能使用原始类型：

// 装整数的双链表
LinkedList<Integer> list1 = new LinkedList<>();
// 报错，不能用 int 这种原始类型作为泛型
LinkedList<int> list2 = new LinkedList<>();

// 装字符串的双链表
LinkedList<String> list3 = new LinkedList<>();

我们在实现自己的数据结构类时，也需要使用泛型，以便我们的数据结构能够装任何类型。

我们在数据结构精品课中实现所有数据结构都需要使用泛型，比如 MyLinkedList，在 new 的时候传入 Integer 类型，那么这个 E 就会变成什么类型：

public class MyLinkedList<E> {

    // 在链表尾部添加元素
    public void addLast(E e) {
        // ...
    }
}

// 使用方法：
MyLinkedList<Integer> list1 = new MyLinkedList<>();
MyLinkedList<String> list2 = new MyLinkedList<>();

当然，某些特殊数据结构对存储的数据类型有要求。比如 TreeMap 这种数据结构，由于底层是用 BST（二叉搜索树）来存储键值对，所以 TreeMap 要求存入其中的键必须是「可比较的」，即对于任意两个键，必须能够知道它俩谁大谁小。

在 Java 中，可以给泛型变量添加 extends 来指定该泛型的某些特性：

// MyTreeMap 接收两个泛型 K 和 V，其中 K 必须实现 Comparable 接口
public class MyTreeMap<K extends Comparable<K>, V> {
    public V put(K key, V val) {
        // ...
    }
}

// 使用方法：
MyTreeMap<Integer, Integer> map1 = new MyTreeMap<>();
MyTreeMap<String, Integer> map2 = new MyTreeMap<>();

这个 Comparable 是 Java 标准库提供的一个接口，实现如下：

1
2
3

public interface Comparable<T> {
    public int compareTo(T o);
}

所以 K extends Comparable<K> 的意思就是说，泛型 K 实现了这个接口，即类型 K 有 compareTo 这个方法，这意味着两个 K 类型的数据可以比较大小。

另外再说下 Java 的接口，免得有些读者疑惑。我们有时候会看到这样的写法：

1 2	Queue<String> q = new LinkedList<>(); List<String> list = new LinkedList<>();

实际 new 出来的是 LinkedList 类型，但为什么用 Queue 类型和 List 类型接收呢？因为 Queue 和 List 都是 Java 标准库中的接口类型：

public interface Queue<E> extends Collection<E> {
    boolean offer(E e);
    E poll();
    E peek();
    // 还有若干方法...
}

public interface List<E> extends Collection<E> {
    // 若干方法...
}

所谓接口，就是一组方法的集合，只要一个类使用 implements 关键词申明自己实现了接口中的所有方法，那么就可以用这个接口的类型来接收这个类的实例化对象。

具体地，标准库提供的 LinkedList 类实现了 List 接口中的所有方法，且使用 implements 关键词申明自己实现了 List 接口：

// Deque 是 Queue 的子接口，所以可以认为 LinkedList 也实现了 Queue 接口
// 还有若干接口，这里省略了
public class LinkedList<E> implements List<E>, Deque<E> {
    // ...

    // Queue 接口中声明的若干方法都会被实现
    boolean offer(E e) {...}
    E poll() {...}
    E peek() {...}
    // ...

    // List 接口的若干方法也都会被实现
    // ...
}

所以可以用 List 接口接收 LinkedList 类型，Queue 接口同理。

当然，编程语言的接口和继承往深里说有很多设计方法的学问，不过我们当前的重点在数据结构和算法，所以只讲这些最基本的知识便于理解算法代码，大家有兴趣可以自己搜索学习。