一、线性结构

1. 数组 Array

特点

固定长度、连续内存、查询快、增删慢，分一维数组、二维数组。

示例代码

java

运行

public class ArrayDemo {
    public static void main(String[] args) {
        // 1. 一维数组定义
        int[] arr = {10, 20, 30, 40};
        // 根据下标取值
        System.out.println(arr[1]); // 20

        // 遍历数组
        for (int num : arr) {
            System.out.print(num + " ");
        }

        // 2. 二维数组（矩阵）
        int[][] matrix = {{1,2},{3,4}};
        System.out.println("\n" + matrix[0][1]); // 2
    }
}

核心解释

1. 长度初始化后不可修改；
2. 随机访问时间复杂度 O(1)；
3. 中间插入 / 删除需要移动元素，O(n)；
4. 适合长度固定、频繁查询场景。

---

2. ArrayList 动态数组（List 实现）

特点

底层数组封装，自动扩容，有序可重复，查询快、中间增删慢。

示例代码

java

运行

import java.util.ArrayList;

public class ArrayListDemo {
    public static void main(String[] args) {
        // 创建集合
        ArrayList<String> list = new ArrayList<>();
        // 添加元素
        list.add("Java");
        list.add("MySQL");
        list.add("Redis");
        // 指定下标插入
        list.add(1, "Spring");

        // 获取元素
        System.out.println(list.get(1)); // Spring
        // 删除元素
        list.remove("MySQL");
        // 遍历
        for (String s : list) {
            System.out.print(s + " ");
        }
        // 获取长度
        System.out.println("\n长度：" + list.size());
    }
}

核心解释

1. 默认容量 10，扩容规则：原容量*1.5；
2. 允许null、元素可重复、有序；
3. 尾部增删效率高，中间操作大量移位。

---

3. LinkedList 双向链表（List/Deque）

特点

底层双向链表，无扩容，头尾增删极快，随机查询慢。

示例代码

java

运行

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> link = new LinkedList<>();
        // 尾部添加
        link.add(1);
        // 头部添加
        link.addFirst(0);
        // 尾部添加
        link.addLast(2);

        System.out.println(link.getFirst()); // 0
        System.out.println(link.getLast());  // 2

        link.removeFirst(); // 删除头节点
        System.out.println(link); // [1, 2]
    }
}

核心解释

1. 每个节点存 prev、value、next；
2. 头尾增删 O(1)，按索引查找 O(n)；
3. 同时实现队列、双端队列接口，可做栈 / 队列。

---

4. Stack 栈（后进先出 LIFO）

特点

先进后出，Java 推荐用Deque代替老旧 Stack 类。

示例代码

java

运行

import java.util.Deque;
import java.util.LinkedList;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new LinkedList<>();
        // 入栈
        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println(stack.peek()); // 取栈顶不删除 C
        System.out.println(stack.pop());  // 出栈 C
        System.out.println(stack);        // [B, A]
    }
}

核心解释

1. push 入栈、pop 出栈、peek 查看栈顶；
2. 适用场景：表达式求值、括号匹配、函数调用栈。

---

5. Queue 队列（先进先出 FIFO）

普通队列 LinkedList

java

运行

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

public class QueueDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1); // 入队
        queue.offer(2);
        queue.offer(3);

        System.out.println(queue.peek()); // 队首 1
        System.out.println(queue.poll()); // 出队 1
        System.out.println(queue); // [2, 3]
    }
}

优先级队列 PriorityQueue

自动元素排序，默认小顶堆

java

运行

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        Queue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(2);
        pq.add(8);
        // 自动从小到大出队
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // 2 5 8
        }
    }
}

解释

• Queue：offer 入队、poll 出队、peek 队首；
• PriorityQueue：底层二叉堆，自定义对象需重写比较器。

---

二、哈希结构（无序、去重、键值映射）

1. HashSet 哈希集合（元素唯一，无序）

底层 HashMap，只存 key

java

运行

import java.util.HashSet;
import java.util.Set;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("苹果");
        set.add("香蕉");
        set.add("苹果"); // 重复元素自动丢弃

        System.out.println(set); // [苹果, 香蕉]
        System.out.println(set.contains("香蕉")); // true
        set.remove("香蕉");
    }
}

解释

1. 元素不可重复，无序；
2. 增删查平均 O(1)；
3. 自定义对象必须重写 equals() + hashCode()。

2. TreeSet 有序集合（红黑树）

自动升序去重

java

运行

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(9);
        treeSet.add(3);
        treeSet.add(6);
        System.out.println(treeSet); // [3, 6, 9] 自动排序
    }
}

解释

底层红黑树，查找、插入删除 O(logn)；元素必须实现 Comparable。

3. HashMap 键值对哈希表（最常用）

java

运行

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

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        // 存键值
        map.put("张三", 20);
        map.put("李四", 22);
        map.put("张三", 21); // 覆盖旧值

        System.out.println(map.get("张三")); // 21
        // 判断key是否存在
        System.out.println(map.containsKey("李四"));
        // 遍历键值对
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }
    }
}

核心解释

1. JDK1.8 底层：数组 + 链表 + 红黑树；
2. key 唯一，value 可重复，允许一个 null key、多个 null value；
3. 负载因子 0.75，达到阈值自动扩容 2 倍；
4. 平均读写 O(1)。

4. TreeMap 有序 Map（红黑树）

key 自动排序

java

运行

import java.util.TreeMap;

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("b", 2);
        treeMap.put("a", 1);
        System.out.println(treeMap); // {a=1, b=2}
    }
}

5. LinkedHashMap / LinkedHashSet

保留插入顺序

java

运行

LinkedHashMap<String, Integer> linkMap = new LinkedHashMap<>();
linkMap.put("1",1);
linkMap.put("2",2);
System.out.println(linkMap); // 按插入顺序输出

---

三、树结构

1. 二叉树（自定义实现）

java

运行

// 树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeDemo {
    // 中序遍历：左->根->右
    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        // 构建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        inOrder(root); // 2 1 3
    }
}

解释

二叉树每个节点最多两个子节点；遍历分为前序、中序、后序、层序。

2. 二叉搜索树 BST

左子树 < 根 < 右子树，中序遍历有序，TreeSet/TreeMap 底层。

---

四、并发安全集合（多线程专用）

1. ConcurrentHashMap（线程安全 Map）

java

运行

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentMapDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        map.put("a", 1);
        map.get("a");
    }
}

解释

分段锁 / CAS，高并发性能远优于 Hashtable。

2. CopyOnWriteArrayList 线程安全 List

写时复制，读不加锁，适合读多写少场景。

java

运行

import java.util.concurrent.CopyOnWriteArrayList;

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("test");