以下是对每个数据结构的 详细补充说明，包括核心概念、操作逻辑、复杂度分析和应用场景：

1. 数组 (Array)

核心概念

• 连续内存分配：元素在内存中连续存储，通过索引直接访问。
• 固定大小：初始化时需指定长度，动态扩容需重新分配内存。

操作细节

• 访问：通过下标 arr[i] 直接定位内存地址，时间复杂度 O(1)。
• 插入/删除：
  • 头部插入需要移动所有元素，时间复杂度 O(n)。
  • 尾部插入若空间足够，时间复杂度 O(1)。
• 动态数组（如 ArrayList）：自动扩容（通常扩容为原容量的1.5倍），但扩容时需要复制数据。

Java示例（动态数组）

ArrayList<Integer> list = new ArrayList<>();
list.add(10);       // 尾部插入 O(1)（均摊）
list.add(0, 5);      // 头部插入 O(n)
list.remove(1);      // 删除中间元素 O(n)

应用场景

• 需要快速随机访问（如矩阵计算）。
• 数据量固定且无需频繁增删（如缓存池）。

2. 链表 (Linked List)

单链表 vs 双向链表

核心操作复杂度

• 插入：
  • 头部插入：O(1)（单链表和双向链表）。
  • 尾部插入：单链表需遍历到尾部（O(n)），双向链表可优化为 O(1)。
• 删除：
  • 已知节点时，双向链表删除为 O(1)（单链表需要找到前驱节点，O(n)）。

循环链表应用

• 实现轮询调度算法（如操作系统进程调度）。
• 约瑟夫问题（Josephus problem）。

3. 栈 (Stack)

核心特性

• LIFO（后进先出）：最后压入栈的元素最先弹出。
• 递归调用：函数调用栈保存返回地址和局部变量。

实现方式

1. 数组实现：适合固定大小栈（如 Stack 类）。
2. 链表实现：动态扩容（无大小限制）。

Java示例（链表实现）

class LinkedStack {
    private static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }
    
    private Node top;
    
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }
    
    public int pop() {
        if (top == null) throw new EmptyStackException();
        int data = top.data;
        top = top.next;
        return data;
    }
}

应用场景

• 括号匹配检查（如 {[()]}）。
• 逆波兰表达式求值。

4. 队列 (Queue)

普通队列 vs 循环队列

• 普通队列：front 和 rear 指针单向移动，容易浪费空间。
• 循环队列：利用模运算 (rear = (rear + 1) % capacity) 重用空间。

双端队列 (Deque)

• 允许两端插入和删除，Java 中由 ArrayDeque 实现。
• 可同时作为队列和栈使用。

优先队列 (Priority Queue)

• 基于堆实现，保证每次取出最小（或最大）元素。
• 应用场景：Dijkstra 最短路径算法、任务调度。

5. 树 (Tree)

二叉树遍历

二叉搜索树 (BST) 的缺陷

• 若插入有序数据（如 1, 2, 3, 4），退化为链表，搜索效率降至 O(n)。
• 解决方案：使用平衡二叉搜索树（如 AVL 树、红黑树）。

6. 哈希表 (Hash Table)

哈希冲突解决

1. 链地址法（Java HashMap 实现）：
   • 每个桶存储链表或红黑树（Java 8+）。
2. 开放寻址法：
   • 线性探测、二次探测、双重哈希。

负载因子与扩容

• 负载因子 = 元素数量 / 桶数量（默认 0.75）。
• 当负载因子超过阈值，哈希表扩容并重新哈希所有元素。

Java示例（自定义哈希函数）

public int hashCode(String key) {
    int hash = 0;
    for (char c : key.toCharArray()) {
        hash = 31 * hash + c;  // 31 是经验值，减少冲突
    }
    return hash;
}

7. 图 (Graph)

表示方式对比

关键算法

1. DFS（深度优先搜索）：
   • 应用：拓扑排序、连通分量检测。
2. BFS（广度优先搜索）：
   • 应用：最短路径（无权图）、社交网络好友推荐。

8. 堆 (Heap)

核心特性

• 完全二叉树：除最后一层外，其他层节点必须填满。
• 堆序性：父节点值 ≥ 子节点（大顶堆）或父节点值 ≤ 子节点（小顶堆）。

Java实现（优先队列）

// 小顶堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

应用场景

• 合并 K 个有序链表。
• 实时数据流的中位数计算（双堆法）。

总结与学习路径

1. 理解基础操作：手动实现每个数据结构的核心方法（如链表的反转、树的遍历）。
2. 复杂度分析：明确不同场景下的最优数据结构选择。
3. 实际应用：
   • 数组：缓存系统、图像处理。
   • 哈希表：数据库索引、缓存（LRU Cache）。
   • 图：社交网络、路由算法。
4. 进阶学习：
   • 红黑树（Java TreeMap 实现）。
   • B树/B+树（数据库索引）。
   • 跳表（Redis 有序集合）。

通过结合理论学习和 LeetCode 实践（如题目 206-反转链表、215-数组中的第K大元素），可以深入掌握数据结构的应用技巧。