Java数据结构基础：从线性结构到非线性结构的全面解析

数据结构是计算机科学中组织和存储数据的方式，直接影响程序的性能和效率。作为Java开发者，理解各种数据结构的特点和适用场景至关重要。本文将深入探讨Java中的基础数据结构，包括线性结构和非线性结构，并提供实际应用示例。

一、线性结构

1. 数组（静态/动态）

概念解释：
数组是最基础的数据结构，由相同类型的元素按顺序存储在连续内存中。Java中的数组是静态的，一旦创建大小固定不变。

// 静态数组示例
int[] staticArray = new int[5]; // 固定长度为5
staticArray[0] = 10; // 通过索引访问

动态数组（如ArrayList）在底层使用静态数组，当容量不足时自动扩容：

// 动态数组示例
List<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(10); // 自动管理容量

实践建议：

• 优先选择动态数组（ArrayList）除非明确知道固定大小且性能敏感
• 预估大小时尽量指定初始容量避免频繁扩容
• 随机访问时间复杂度O(1)，插入删除平均O(n)

2. 链表（单向/双向/循环）

概念解释：
链表通过节点链接实现，每个节点包含数据和指向下一个节点的引用。

graph LR
    A[单向链表] --> B[数据|next] --> C[数据|next] --> D[数据|null]
    E[双向链表] --> F[prev|数据|next] <--> G[prev|数据|next]
    H[循环链表] --> I[数据|next] --> J[数据|next] --> H

Java实现示例：

// 单向链表节点定义
class Node<T> {
    T data;
    Node<T> next;
    
    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

// Java标准库中的LinkedList是双向链表实现
List<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);

实践建议：

• 频繁插入删除操作时选择链表（LinkedList）
• 需要双向遍历时选择双向链表
• 随机访问性能差（O(n)），适合顺序访问
• 内存开销比数组大（每个元素需要额外存储引用）

3. 栈（LIFO）与队列（FIFO/优先队列）

栈（后进先出）：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 压栈
int top = stack.pop(); // 弹栈

队列（先进先出）：

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
int head = queue.poll(); // 出队

优先队列：

Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(3);
priorityQueue.offer(1);
priorityQueue.poll(); // 返回1（最小优先）

实践建议：

• 使用Deque接口实现栈（而非遗留的Stack类）
• 需要优先级处理时使用PriorityQueue
• 广度优先搜索使用队列，深度优先搜索使用栈

二、非线性结构

1. 树结构

二叉树

二叉搜索树（BST）

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// 插入BST
TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insert(root.left, val);
    else root.right = insert(root.right, val);
    return root;
}

平衡树（AVL/红黑树）

Java中的TreeMap和TreeSet使用红黑树实现：

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One"); // 自动保持有序

实践建议：

• 需要有序数据时选择TreeSet/TreeMap
• 红黑树提供O(log n)的查询性能
• 自己实现树结构时考虑平衡性问题

2. 图结构

概念解释：
图由顶点和边组成，可分为有向图和无向图。

// 邻接表表示图
class Graph {
    private int V; // 顶点数
    private LinkedList<Integer>[] adj; // 邻接表
    
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
    
    void addEdge(int v, int w) { adj[v].add(w); }
}

实践建议：

• 稀疏图使用邻接表，稠密图使用邻接矩阵
• 考虑使用专业图库如JGraphT处理复杂图算法
• 注意循环引用和遍历终止条件

3. 哈希表

概念解释：
哈希表通过哈希函数将键映射到存储位置，Java中HashMap是典型实现。

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 1);
hashMap.put("banana", 2);
int value = hashMap.get("apple"); // 1

冲突解决：

• 开放寻址法
• 链地址法（Java HashMap使用）

实践建议：

• 自定义对象作为键时必须正确实现hashCode()和equals()
• 初始容量和负载因子影响性能，默认0.75负载因子是良好平衡
• Java 8+中，桶内元素超过8个时会转为红黑树

三、数据结构选择指南

四、性能优化技巧

1. 预分配容量：对于集合类型如ArrayList、HashMap，预估大小并指定初始容量

   List<Integer> list = new ArrayList<>(1000); // 避免扩容开销

2. 选择合适结构：根据主要操作类型选择，如：

   • 读多写少：ArrayList
   • 写多读少：LinkedList
   • 唯一性检查：HashSet
   • 范围查询：TreeSet

3. 利用视图：减少数据复制

   List<Integer> subList = list.subList(0, 5); // 原始列表的视图

4. 不可变集合：线程安全且更安全

   List<Integer> immutable = Collections.unmodifiableList(list);

五、常见问题解答

Q：ArrayList和LinkedList哪个更快？
A：取决于操作类型：

• 随机访问：ArrayList O(1) vs LinkedList O(n)
• 头部插入：ArrayList O(n) vs LinkedList O(1)
• 迭代：两者都是O(n)，但ArrayList缓存友好

Q：HashMap线程不安全怎么办？
A：使用：

1. Collections.synchronizedMap()
2. ConcurrentHashMap（推荐）
3. 不可变Map（Java 9+）

Q：如何选择Set实现？
A：

• HashSet：通用，O(1)操作
• TreeSet：需要有序，O(log n)
• LinkedHashSet：保持插入顺序

六、总结

掌握数据结构是成为优秀Java开发者的基础。理解每种结构的内部实现和性能特征，才能在实际开发中做出合理选择。记住：

• 线性结构适合顺序数据
• 树结构提供高效搜索和排序
• 图结构处理复杂关系
• 哈希表实现快速查找

根据具体场景选择最合适的数据结构，往往能带来显著的性能提升和更简洁的代码实现。