Java 数据结构深度解析

Java 集合框架（Java Collections Framework, JCF）是工业级面向对象架构与泛型抽象的典范：

• 接口与实现彻底分离：定义统一高层接口（List、Set、Map、Queue、Deque），底层提供针对不同硬件局部性与并发模型的具体实现。
• 现代 Java (Java 21 LTS) 增强：引入顺序集合（Sequenced Collections，如 getFirst(), reversed()）、record 极简节点建模与流式计算（Stream API）。

---

📊 核心集合实现对照

接口	核心实现类	底层原理	典型时间复杂度	最佳使用建议
List	ArrayList	Object[] 动态扩容数组	索引 $O(1)$，尾插均摊 $O(1)$	绝大多数场景的首选序列容器
Deque	LinkedList / ArrayDeque	双向链表 / 循环数组双端队列	首尾操作 $O(1)$	栈与双端操作
Map	HashMap / TreeMap	哈希桶 / 经典红黑树	增删查平均 $O(1)$ / $O(\log n)$	通用键值映射与范围检索
Queue	PriorityQueue	动态数组小顶堆 (Binary Heap)	堆顶 $O(1)$，插入/弹出 $O(\log n)$	任务调度、Top-K 统计

---

1. 线性结构：动态数组与双向链表

动态数组 (ArrayList 与 Stream 聚合)

public class DynamicArrayDemo {
    public static void main(String[] args) {
        System.out.println("=== Java ArrayList & Vector Demo ===");
        java.util.List<Integer> list = new java.util.ArrayList<>();
        list.add(10);
        list.add(20);
        list.add(30);

        if (list.size() != 3 || list.get(1) != 20) {
            throw new RuntimeException("Assertion failed");
        }

        int sum = list.stream().mapToInt(Integer::intValue).sum();
        if (sum != 60) {
            throw new RuntimeException("Sum assertion failed");
        }

        System.out.println("Java ArrayList size=" + list.size() + ", sum=" + sum);
        System.out.println("Java Dynamic Array tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java ArrayList & Vector Demo ===
Java ArrayList size=3, sum=60
Java Dynamic Array tests passed successfully.

双向链表与双端队列 (LinkedList)

public class LinkedListDemo {
    public static void main(String[] args) {
        System.out.println("=== Java LinkedList & Deque Demo ===");
        java.util.LinkedList<String> list = new java.util.LinkedList<>();
        list.addFirst("first");
        list.addLast("last");

        if (!list.getFirst().equals("first") || !list.getLast().equals("last")) {
            throw new RuntimeException("LinkedList assertion failed");
        }

        System.out.println("Java LinkedList elements: " + list);
        System.out.println("Java LinkedList tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java LinkedList & Deque Demo ===
Java LinkedList elements: [first, last]
Java LinkedList tests passed successfully.

---

2. 树与堆：二叉搜索树与优先队列

二叉搜索树实现 (BST)

public class BstDemo {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else if (val > root.val) root.right = insert(root.right, val);
        return root;
    }

    static boolean search(Node root, int val) {
        if (root == null) return false;
        if (root.val == val) return true;
        return val < root.val ? search(root.left, val) : search(root.right, val);
    }

    public static void main(String[] args) {
        System.out.println("=== Java Binary Search Tree ===");
        Node root = null;
        root = insert(root, 50);
        root = insert(root, 30);
        root = insert(root, 70);

        if (!search(root, 30) || search(root, 99)) {
            throw new RuntimeException("BST search assertion failed");
        }
        System.out.println("Java BST search tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java Binary Search Tree ===
Java BST search tests passed successfully.

优先队列与小顶堆 (PriorityQueue)

public class HeapDemo {
    public static void main(String[] args) {
        System.out.println("=== Java PriorityQueue (Min/Max Heap) ===");
        java.util.PriorityQueue<Integer> minHeap = new java.util.PriorityQueue<>();
        minHeap.offer(50);
        minHeap.offer(15);
        minHeap.offer(30);

        if (minHeap.peek() != 15) throw new RuntimeException("Heap peek failed");
        if (minHeap.poll() != 15) throw new RuntimeException("Heap poll failed");
        if (minHeap.poll() != 30) throw new RuntimeException("Heap poll failed");
        if (minHeap.poll() != 50) throw new RuntimeException("Heap poll failed");

        System.out.println("Java PriorityQueue tests passed successfully.");
    }
}

🐳 Docker Verified📋eclipse-temurin:21-jdk-alpine

Exit Code: 0

=== Java PriorityQueue (Min/Max Heap) ===
Java PriorityQueue tests passed successfully.