Java 数据结构(建议收藏)

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ,你将获得:专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸:仿小红书(微服务架构)》 正在持续爆肝中,基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...点击查看项目介绍 ;
  • 《从零手撸:前后端分离博客项目(全栈开发)》 2 期已完结,演示链接: http://116.62.199.48/ ;

截止目前, 星球 内专栏累计输出 82w+ 字,讲解图 3441+ 张,还在持续爆肝中.. 后续还会上新更多项目,目标是将 Java 领域典型的项目都整一波,如秒杀系统, 在线商城, IM 即时通讯,权限管理,Spring Cloud Alibaba 微服务等等,已有 2900+ 小伙伴加入学习 ,欢迎点击围观

前言

在编程世界中,数据结构是解决问题的基石,而Java 数据结构作为面向对象语言的核心组成部分,直接影响着程序的效率与可维护性。无论是开发一个简单的计算器,还是构建复杂的分布式系统,理解数据如何组织和操作都是关键。本文将从零开始,通过生活化的比喻、代码示例和场景分析,帮助编程初学者和中级开发者系统性掌握 Java 中的核心数据结构,并了解它们的实际应用价值。


一、数据结构的基础概念与重要性

1.1 什么是数据结构?

数据结构(Data Structure)是计算机中存储、组织数据的方式,它定义了数据的逻辑关系、操作方法以及物理存储形式。例如,一个图书馆的书籍分类系统(按作者、主题排列)可以看作一种数据结构,而 Java 中的 ArrayListLinkedList 则是程序中的具体实现。

比喻
如果把数据比作“建筑材料”,那么数据结构就是“施工图纸”——它决定了如何将零散的砖块(数据)组合成一座高楼(高效程序)。

1.2 为什么学习 Java 数据结构?

  • 提升代码效率:选择合适的数据结构可以减少算法的时间和空间复杂度。例如,用哈希表(Hash Table)查找数据的时间复杂度为 O(1),而用数组逐个遍历则是 O(n)。
  • 解决实际问题:如社交媒体的朋友推荐(图结构)、电商的购物车(链表)或日志处理(队列)。
  • 为算法学习打下基础:排序算法(如快速排序)、搜索算法(如二叉树遍历)都依赖数据结构的支持。

二、Java 核心数据结构详解

2.1 数组(Array)

定义:数组是固定大小的连续内存空间,通过索引快速访问元素。

特点与适用场景

特点优势局限性
连续存储支持随机访问(O(1))长度不可动态扩展
索引访问遍历和访问效率高插入/删除元素时需移动大量数据

代码示例

// 定义并初始化一个整型数组  
int[] scores = {90, 85, 95};  
// 通过索引访问元素  
System.out.println("第二个成绩是:" + scores[1]); // 输出 85  

生活比喻
想象一个书架上的书按顺序排列,每本书都有固定位置(索引)。找书很快,但新增一本需要腾出空间,而删除一本则留下空位。


2.2 链表(Linked List)

定义:链表由**节点(Node)**组成,每个节点包含数据和指向下一个节点的指针,形成动态结构。

单链表与双链表对比

类型结构描述适用场景
单链表(SLL)每个节点仅指向下一个节点插入/删除频繁的场景(如队列)
双链表(DLL)节点同时指向前后节点需要双向遍历的场景(如浏览器历史记录)

代码示例:单链表的插入操作

class Node {  
    int data;  
    Node next;  
    public Node(int data) { this.data = data; }  
}  

// 在链表头部插入新节点  
public void addFirst(int value) {  
    Node newNode = new Node(value);  
    newNode.next = head;  
    head = newNode;  
}  

生活比喻
链表像一列火车,每个车厢(节点)通过挂钩(指针)连接。增加或移除车厢无需移动整列车,只需调整挂钩即可。


2.3 栈(Stack)与队列(Queue)

2.3.1 栈:后进先出(LIFO)

核心操作

  • push():将元素压入栈顶。
  • pop():弹出栈顶元素。
  • peek():查看栈顶元素而不移除。

代码示例:计算器表达式求值

Stack<Integer> stack = new Stack<>();  
stack.push(5);  
stack.push(10);  
System.out.println("栈顶元素:" + stack.peek()); // 输出 10  
stack.pop(); // 弹出 10 后,栈顶变为 5  

生活比喻
栈如同叠放盘子的托盘,最后放上去的盘子(元素)最先被取走。

2.3.2 队列:先进先出(FIFO)

核心操作

  • enqueue():在队尾添加元素。
  • dequeue():移除队首元素。

代码示例:打印任务队列

Queue<String> printQueue = new LinkedList<>();  
printQueue.add("文档A");  
printQueue.add("文档B");  
System.out.println("下一个打印任务:" + printQueue.peek()); // 输出 "文档A"  
printQueue.poll(); // 移除 "文档A"  

生活比喻
队列如同银行排队系统,先到达的人(元素)最先被服务。


2.4 树(Tree)与图(Graph)

2.4.1 树:分层结构

二叉树是树的典型代表,每个节点最多有两个子节点(左、右)。

  • 应用场景:文件系统目录、数据库索引(如 B+ 树)。

代码示例:二叉树的前序遍历

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

public void preOrder(TreeNode node) {  
    if (node != null) {  
        System.out.print(node.val + " "); // 访问当前节点  
        preOrder(node.left); // 遍历左子树  
        preOrder(node.right); // 遍历右子树  
    }  
}  

生活比喻
家庭族谱是一棵典型的树结构,每个祖先(父节点)可以有多个后代(子节点)。

2.4.2 图:复杂关系网络

定义:由节点(Vertex)和边(Edge)组成,边可以是有向或无向的。

  • 应用场景:社交网络(如朋友关系)、路线规划(如导航系统)。

代码示例:图的邻接表表示法

// 节点类  
class Vertex {  
    String name;  
    List<Vertex> neighbors;  
    public Vertex(String name) {  
        this.name = name;  
        this.neighbors = new ArrayList<>();  
    }  
}  

// 添加边  
vertexA.neighbors.add(vertexB);  
vertexB.neighbors.add(vertexC);  

生活比喻
城市交通网络如同图结构,每个路口(节点)通过道路(边)连接,可能形成环路或分支。


三、Java 内置数据结构与集合类

3.1 列表(List):动态数组的实现

Java 的 ArrayList 是基于数组实现的动态列表,扩容时会创建新数组并复制元素。而 LinkedList 则基于链表,适合频繁插入/删除操作。

性能对比
| 操作 | ArrayList | LinkedList |
|---------------|-----------------|--------------------|
| 随机访问 | O(1) | O(n) |
| 插入/删除末尾 | O(1)(无扩容) | O(1) |
| 插入/删除中间 | O(n) | O(n)(需遍历查找) |


3.2 集合(Set)与映射(Map)

  • Set:存储不重复元素,如 HashSet 通过哈希表实现快速查找。
  • Map:键值对存储,如 HashMap 通过哈希表关联键(Key)和值(Value)。

代码示例:去重与快速查找

// 使用 Set 去重  
Set<String> uniqueWords = new HashSet<>();  
uniqueWords.add("apple");  
uniqueWords.add("banana");  
uniqueWords.add("apple"); // 第二次添加无效  

// 使用 Map 存储用户信息  
Map<String, Integer> userAges = new HashMap<>();  
userAges.put("Alice", 30);  
int aliceAge = userAges.get("Alice"); // 获取值  

四、实战案例:数据结构的应用场景

4.1 用栈实现括号匹配

public boolean isBalanced(String expression) {  
    Stack<Character> stack = new Stack<>();  
    for (char c : expression.toCharArray()) {  
        if (c == '(' || c == '{' || c == '[') {  
            stack.push(c);  
        } else if (c == ')' || c == '}' || c == ']') {  
            if (stack.isEmpty()) return false; // 无匹配左括号  
            char top = stack.pop();  
            if (!isMatch(top, c)) return false;  
        }  
    }  
    return stack.isEmpty(); // 确保所有左括号都被弹出  
}  

private boolean isMatch(char left, char right) {  
    return (left == '(' && right == ')') ||  
           (left == '{' && right == '}') ||  
           (left == '[' && right == ']');  
}  

解释:栈的 LIFO 特性完美匹配括号的“成对闭合”规则。

4.2 用优先队列实现任务调度

// 定义任务类  
class Task implements Comparable<Task> {  
    String name;  
    int priority;  
    public Task(String name, int priority) {  
        this.name = name;  
        this.priority = priority;  
    }  
    public int compareTo(Task other) {  
        return Integer.compare(this.priority, other.priority); // 优先级升序  
    }  
}  

// 使用优先队列  
PriorityQueue<Task> taskQueue = new PriorityQueue<>();  
taskQueue.add(new Task("任务A", 3));  
taskQueue.add(new Task("任务B", 1));  
taskQueue.add(new Task("任务C", 2));  
System.out.println(taskQueue.poll().name); // 输出 "任务B"(优先级最低)  

结论

Java 数据结构不仅是编程的“工具箱”,更是解决问题的思维框架。通过掌握数组、链表、栈、队列、树、图等核心结构,开发者可以更高效地设计算法、优化代码,并理解高级框架(如数据库索引、分布式系统)的底层逻辑。

对于初学者,建议从简单结构(如数组、栈)入手,逐步过渡到复杂结构(如图、树),并通过实际项目(如实现计算器、社交网络关系图)巩固知识。中级开发者则可深入研究集合类的源码实现,理解 HashMap 的哈希冲突解决或 TreeMap 的红黑树平衡机制,从而在性能优化时做出更明智的选择。

记住,数据结构的学习是一个循序渐进的过程——每一次对代码的优化、对问题的抽象,都在帮助你构建更强大的“数据思维”。

最新发布