简要

本文主要介绍数据结构以及在 Java 中有哪些直接可用的数据结构（不涉及并发编程使用场景）。

常见的数据结构

下面直接介绍的常见的数据结构：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、堆（Heap）、散列表（Hash）、图（Graph）

数组（Array）

数组是最基本的数据结构，有一维数组，二维数组等等，底层存储方式是连续的内存。 Java 中的使用：

int[] array1 = new int[10];
int[][] array2 = new int[10][10];
array1[1] = 10;
array2[0][10] = 11;

栈（Stack）

栈是先进后出（FILO，First In Last Out）的数据结构。 Stack 类在 java.util 包下，使用：

import java.util.Stack;

public class UseStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        // 入栈，push
        stack.push(1);
        stack.push(2);
        // 瞥一眼，但不会弹出
        Integer peek = stack.peek();
        // 只要不是空，就继续弹
        while (!stack.isEmpty()){
            // 出栈，pop
            Integer pop = stack.pop();
        }
    }
}

队列（Queue）

队列是先进先出（FIFO）结构。队列在 Java 中没有直接的实现，只是定义了接口。一般使用 LinkedList 类去充当队列使用。实现了 Queue 接口的常见类有：LinkedList 类，PriorityQueue 类（优先级队列，即堆）。

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

public class UseQueue {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        // 加入队列
        queue.add(1);
        queue.add(2);
        queue.add(3);
        // peek，瞥一眼但不会弹出
        Integer peek = queue.peek();
        while (!queue.isEmpty()){
            // 出队
            Integer poll1 = queue.poll();
        }
    }
}

链表（Linked List）

在 java 的实现中，LinkedList 直接是可以当成双向链表使用。Java 中也有 ArrayList，是使用数组的方式去实现的链表。由于双向链表的特殊性，所以可以当成队列，也可以当成栈使用，在 Java 中都实现了这些方法。在这里为了避免理解造成歧义，还是用比较符合人的常规理解去使用他比较好，示例：

import java.util.LinkedList;

public class UseLinkedList {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        // 添加到头部
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        // 添加到尾部
        linkedList.addLast(3);
        linkedList.addLast(4);
        // 此时应该是2-1-3-4，分别瞥见头部和尾部应该是2，4
        System.out.println(linkedList.peekFirst());
        System.out.println(linkedList.peekLast());
        // 弹出头部
        linkedList.removeFirst();
        // 弹出尾部
        linkedList.removeLast();
        while (!linkedList.isEmpty()) {
            // 一直从头部弹出，直至结束
            linkedList.removeFirst();
        }
    }
}

树（Tree）

树是典型的非线性结构。树的使用在做题中很常见，在题目中最常见的是二叉树，二叉树有广度遍历（按层遍历）和深度遍历（先序、中序、后序）。关于按层遍历，主要实现方式是使用一个队列即可。关于代码实现的方式可以是递归（系统压栈），使用栈，这些都是要额外空间复杂度的，还有空间复杂度为 O(1) 的遍历方法即 Morris 遍历。 Java 中没有 Tree 的数据结构，不过我们可以自己写一个，至于拓展，自己可以随便玩：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        this.val = x;
    }
}

堆（Heap）

堆分为大根堆和小根堆，大根堆是大的在根部上，小根堆是小的在根部上。每次加入或者弹出新的元素，内部通过调整维持优先级顺序，其实也就是优先级队列。在 Java 中，直接就是优先级队列。默认小根堆，也可以改默认，构造时传入比较器即可，使用示例：

import java.util.Comparator;
import java.util.PriorityQueue;

public class UseHeap {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(5);
        minHeap.add(0);
        minHeap.add(10);
        // 瞥一眼，不会弹出，此时根部应该是0
        Integer peekMin = minHeap.peek();
        while (!minHeap.isEmpty()) {
            // 依次弹出0、5、10
            System.out.println(minHeap.poll());
        }
        
        // 大根堆，传入比较器，反转顺序
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(5);
        maxHeap.add(0);
        maxHeap.add(10);
        // 瞥一眼，不会弹出，此时根部应该是10
        Integer peekMax = maxHeap.peek();
        while (!maxHeap.isEmpty()) {
            // 依次弹出10、5、0
            System.out.println(maxHeap.poll());
        }
    }
}

散列表（Hash）

散列表就是一个 Key-Value 结构。Key 通过哈希函数（Hash Function）映射到某个存储位置，从而实现查询时间复杂度为 O(1)。哈希冲突的解决方法常见的有线性探测法，拉链法等。在 Java 中其叫做 HashMap，使用示例：

import java.util.HashMap;

public class UseHashMap {
    public static void main(String[] args) {
        // 构造函数可传入初始容量（默认是16），如果需要比较大的容量，可以避免动态拓展带来的性能消耗
        HashMap<Integer, String> hashMap = new HashMap<>();
        // 存入key-value对
        hashMap.put(1, "张三");
        hashMap.put(2, "李四");
        hashMap.put(3, "王五");
        // 是否包含key，这里是true
        System.out.println(hashMap.containsKey(1));
        String name = hashMap.get(2);
        // 没有key默认"佚名"
        hashMap.getOrDefault(10,"佚名");
        // 移除key-value对
        hashMap.remove(1);
    }
}

图（Graph）

Java 中也没有图，图用的相对少，以后用到再补充。

Java的中的容器类

Java 中的容器类（常见的一些数据结构，数据结构就是数据的容器），一般放在 java.util 包下。主要有两大类集合（Collection）和映射（Map）。

集合

实现集合接口主要有三大接口：

Set：常见实现类，TreeSet，HashSet，LinkedHashSet
List：常见实现类，ArrayList，LinkedList
Queue：常见实现类，LinekdList，PriorityQueue

分别介绍：

TreeSet：key 有序，底层实现是红黑树去维持 key 的顺序，插入和查询的时间复杂度会上升但 key 有序
HashSet：key 查询快，底层实现是使用哈希表的方式，value 是一个 Object 对象，移除的时候如果是 null 不好判断是否移除成功
LinkedHashSet：比 HashSet 多了一个功能，那就是使用双向链表维护添加 key 的顺序
ArrayList：链表的实现方式，顺序存储。查询快，插入慢
LinkedList：链表的实现方式，链式存储。查询慢，插入快
PriorityQueue：优先级队列，底层实现使用数组实现

映射

实现 Map 接口的常见类有：HashMap，LinkedHashMap，TreeMap

分别介绍：

HashMap：最常用的
LinkedHashMap：使用双向链表维护添加顺序，可以是插入顺序和 LRU 顺序，通过继承该类，重写 removeEldestEntry 方法可以实现一个 LRU 缓存
TreeMap：有序的映射，底层实现是红黑树，插入和查询的时间复杂度会降低，但 key 有序