Java 中的数据结构

Java 中的数据结构是指数据在计算机程序中组织、存储和处理的各种方式。这些结构提供了一种系统化的方法来有效地处理和管理数据，从而实现插入、删除、检索和遍历等有用的操作。

本文将探讨 Java 中数据结构的所有相关内容，帮助初学者轻松有效地理解。

• 什么是 Java？
• Java 中的数据结构是什么？
• Java 中的数据结构类型
• Java 中数据结构的优点
• 数据结构的分类
• Java 数据结构常见问题解答

什么是 Java？

Java 是一种流行的面向对象编程语言，以其庞大的标准库和平台独立性而闻名。它为创建可在各种平台上无需重新编译即可运行的程序提供了坚实的架构。Java 著名的库提供了一系列记录系统，可以有效地处理各种数据类型。

Java 中的数据结构是什么？

数据在程序内存中的组织和存储方式与 Java 记录结构密切相关。Java 标准库包含大量内置数据结构。一些允许程序员快速简单地存储和组织数据的记录系统包括链表、堆栈、队列和数组。开发人员可以快速执行插入、删除、搜索和排序等操作，因为它们提供了一系列访问、修改和管理数据的机制。通过使用这些数据结构，Java 程序员可以减少内存使用量，并显著提高程序的整体效率。

Java 中的数据结构类型

下面列出了 Java 中的数据结构

1. 数组
2. ArrayList
3. LinkedList
4. Stack
5. Queue
6. HashMap
7. HashSet
8. TreeSet
9. TreeMap
10. Graph
11. Tree

下图清楚地解释了 Java 中数据结构的类型。

数据结构的进一步分类

数据结构有两种类型：

1. 基本数据结构
2. 非基本数据结构

1) 基本数据结构： 也称为基本数据类型，它们是 Java 中基本的内置数据类型。它们包括

• byte： 存储从 -128 到 127 的整数。
• short： 存储从 -32,768 到 32,767 的整数。
• int： 存储从 -2,147,483,648 到 2,147,483,647 的整数。
• float： 存储单精度浮点数。
• char： 存储单个字符。
• boolean： 存储 true 或 false 值。
• long： 存储较大的整数。
• Double： 存储双精度浮点数。

2) 非基本数据结构： 非基本记录结构更复杂，由基本信息类型组成。它们还可以分为两类

1. 线性数据结构： 在线性数据结构中，元素按线性或顺序排列。示例如下
   • Arrays： 一组相同类型的元素，按照预先确定的排列方式存储在数组中。
   • Stacks： 后进先出 (LIFO) 结构，只能添加或删除最上面的项目。
   • Queues： 先进先出 (FIFO) 结构用于队列，其中项目在后端插入，在前端取出。
   • Linked List： 链表由一系列称为节点的项组成，每个节点都包含指向后一个节点的引用以及其中的数据。
2. 非线性数据结构： 在非线性数据结构中，元素以非顺序方式排列。示例如下
   • Trees： 树是一种基于节点的层级结构，顶部有一个根节点，子节点从中分支出来。示例包括红黑树、AVL 树、二叉搜索树和二叉树。
   • Graphs： 由边连接的节点集合，其中节点可以具有任意数量的连接。图用于表示项之间的复杂关系。
   • Heap： 一种特殊的基于树的结构，其中每个父节点的值比其子节点的值更大或更小，具体取决于它是最大堆还是最小堆。
   • Hash： 使用哈希函数将键映射到值的哈希数据结构。示例包括哈希集和哈希映射，它们提供基于精确键的高效数据检索和存储。

Java 中数据结构的优点

1. 高效的数据组织： 数据结构提供了组织化的数据存储和管理方式，能够进行高效的访问、操作和检索。它们优化内存使用并促进算法更快地执行。
2. 更好的性能： 开发人员可以通过为特定活动选择合适的数据结构来提高速度和内存利用率方面的性能。性能得到优化，因为某些数据结构专为在搜索、排序或插入信息等特定操作方面表现出色而设计。
3. 代码重用性： Java 提供了广泛的内置数据结构，程序员可以轻松使用。这些可重用的数据结构节省了时间和精力，无需从头开始创建复杂的算法。
4. 代码简洁性： 数据结构使复杂进程的实现更容易编码。它们提供高级抽象并封装数据管理的细节，从而提高代码的可读性、可维护性和清晰度。
5. 灵活性和适应性： 数据结构提供了处理不同类型和大小数据的灵活性。它们可以动态调整以适应不断变化的数据需求，并提供高效数据操作的机制。
6. 标准化和经过充分测试： Java 的标准库包含经过大量测试和优化的内置数据结构，保证了它们的可靠性和性能。使用这些标准数据结构可以降低出错的可能性，并为应用程序开发提供坚实的基础。
7. 可伸缩性： 数据结构提供了可伸缩性选项，使应用程序能够有效地处理大量数据。它们可以根据数据大小动态增长或缩小，即使数据需求增加也能确保最佳性能。
8. 算法设计： 数据结构在算法设计和分析中至关重要。它们提供了实现各种算法和解决复杂问题所需的底层结构和操作。

1) 数组

在 Java 数据结构方面，数组是一种基本且常用的数据结构。它提供了一种存储相同类型元素固定集合的方法。由于它们根据索引提供对元素的快速简便访问，因此数组是管理和组织数据的重要工具。

优点

1. 数据组织： 数组提供了一种结构化的方式来存储和组织元素，从而改进了数据管理。
2. 随机访问： 可以使用索引直接访问元素，从而实现高效的检索和修改。
3. 固定大小： 数组具有预定的尺寸，可以实现高效的内存分配。
4. 同质元素： 数组存储相同类型的元素，确保数据一致性并简化操作。
5. 迭代： 数组支持轻松地遍历元素，从而实现遍历和处理。
6. 排序和搜索： 数组与排序和搜索算法配合良好，提供高效的操作。
7. 内存效率： 数组通过在连续区域中存储元素来优化内存使用。
8. 兼容性： 数组在 Java 中得到广泛支持，使其与各种框架和工具兼容。

缺点

1. 固定大小： 数组不能动态调整大小，需要重新创建才能更改大小。
2. 内存浪费： 较大数组中未使用的元素可能导致内存浪费。
3. 插入和删除的开销： 在数组中间插入或删除元素需要移动后续元素，导致效率低下。
4. 缺乏灵活性： 数组具有严格的数据类型，并且无法在没有其他数组或数据结构的情况下容纳不同类型的数据。

函数

1. 创建数组： 使用数组类型和 new 关键字声明并初始化具有特定大小的数组。
2. 访问元素： 使用索引访问数组中的单个元素。
3. 修改元素： 通过将新值分配给数组中的特定索引来更新元素的值。
4. 查找长度： 使用 length 属性确定数组的长度。
5. 遍历数组： 使用循环遍历数组中的每个元素并执行

实施

文件名： ArrayExample.java

输出

Element at index 0:10
Element at index 2:30
Element at index 4:50
Sum of array elements:150
Updated element at index 2:35
Elements in the array:
10
20
35
40
50

2) ArrayList

Java 中的 ArrayList 是一种动态数据结构，允许存储和操作元素。它是 Java 集合框架的一部分，并在内部使用数组实现。

优点

1. 动态大小： 与数组不同，ArrayList 的大小可以随着元素的添加或删除而动态增长或缩小。它消除了手动调整大小的需要，并允许方便地处理可变数量的数据。
2. 轻松的元素操作： ArrayList 提供在列表的任何位置添加、删除和修改元素的方法。其灵活性简化了插入、删除和更新等常见操作，使得元素操作更加高效。
3. 随机访问： ArrayList 支持使用索引对元素进行随机访问，从而可以快速检索和修改列表中特定位置的元素。它有助于高效的元素访问并提高整体性能。
4. 与 Java 集合框架兼容： ArrayList 实现 List 接口，使其与其他 Java 集合框架中的集合类兼容。其兼容性允许与框架提供的各种算法和操作无缝集成。

缺点

1. 较高的内存开销： ArrayList 需要额外的内存来维护其内部结构，与数组相比，内存开销更高。在处理大量元素集合时，这可能是一个问题。
2. 插入和删除速度较慢： 在 ArrayList 中间插入或删除元素需要移动元素，对于大型列表来说，这可能很耗时。在预期会有频繁插入或删除操作的情况下，LinkedList 等其他数据结构可能提供更好的性能。
3. 搜索性能较低： 在未排序的 ArrayList 中搜索元素需要遍历元素直到找到匹配项。这是一种线性搜索方法，与针对搜索进行了优化的数据结构（如 HashSet 或 TreeMap）相比，搜索性能较慢。
4. 不支持原始类型： ArrayList 只能存储对象，不支持 int 或 char 等原始数据类型。要存储原始类型，需要使用 Integer 或 Character 等包装类，这可能导致自动装箱和拆箱开销。

函数

1. 创建 ArrayList： 使用 ArrayList 类声明并初始化 ArrayList，并在尖括号内指定元素类型。
2. 添加元素： 使用 add 方法将元素附加到 ArrayList 的末尾。
3. 访问元素： 使用 get 方法检索所选索引处元素的价位。
4. 修改元素： 使用 set 方法更新特定索引处元素的成本。
5. 查找大小： 使用 dimensions 方法获取 ArrayList 中因素的当前数量。
6. 删除元素： 使用 remove 方法通过提供对象引用或在特定索引处删除元素。
7. 遍历 ArrayList： 使用循环遍历 ArrayList 中的每个元素并对其执行操作。

实施

文件名： ArrayListExample.java

输出

Element at index 0:10
Element at index 2:30
Element at index 4:50
Sum of ArrayList elements:150
Updated element at index 2:35
Elements in the ArrayList:
10
20
35
40
50

3) LinkedList

链表是一种线性数据结构，其中元素存储在称为节点的单独对象中。每个节点的数据元素都包含指向序列中下一个节点的引用链接。链表的最后一个节点指向 null，表示链表已结束。

与数组不同，链表不需要连续的内存分配。链表中的每个节点都可以独立分配，从而实现动态内存分配以及高效的插入和删除操作。

优点

1. 动态大小： LinkedList 可以动态增长或缩小，适合可变或未知的数据大小。
2. 高效的插入和删除： 在 LinkedList 中插入或删除元素非常高效，因为它不需要移动元素。
3. 无需连续内存： LinkedList 不需要连续内存分配，这使其灵活且适合不可预测的内存情况。
4. 轻松修改： LinkedList 可以通过更改引用指针轻松修改元素，从而实现高效的操作。

缺点

1. 随机访问速度较慢： LinkedList 的随机访问速度较慢，因为它需要遍历列表才能按索引访问元素。
2. 内存开销增加： LinkedList 需要额外的内存来存储引用和节点，与数组相比，内存开销有所增加。
3. 低效搜索： LinkedList 的搜索操作速度较慢，需要顺序遍历才能找到特定元素。

函数

1. 创建 LinkedList： 使用 LinkedList 类声明并初始化 LinkedList。
2. 添加元素： 使用 add 方法将元素附加到 LinkedList 的末尾。
3. 访问元素： 使用 get 方法检索特定索引处元素的 قيمة。
4. 修改元素： 使用 set 方法使用 set 方法更新特定索引处元素的 قيمة。
5. 删除元素： 使用 remove 方法通过提供对象引用或在特定索引处删除元素。

实施

文件名： LinkedList1.java

输出

LinkedList:[10, 20, 30, 40, 50]
LinkedList after removing first element:[20, 30, 40, 50]
LinkedList contains element 30?true
First element:20
Last element:50
LinkedList after clearing:[]

4) Stack

后进先出 (LIFO) 原则规定，最后插入的元素也是最先被移除的元素。栈是一种遵循此规则的线性数据结构。它使用“push”和“pop”命令将元素添加到栈中，并相应地从栈中移除顶部元素。“peek”方法还可以访问顶部元素而不将其移除。

栈的特点

1. LIFO行为： 最后压入栈的元素是最先弹出的元素，使其适用于插入和移除顺序很重要的应用程序。
2. 访问受限： 栈通常提供对元素的受限访问。您只能访问最上面的元素，要访问其他元素，您需要弹出它们上面的元素。
3. 动态大小： 栈可以使用数组或链表实现，允许动态大小。它们可以在运行时根据需要增长或缩小。

优点

1. 简单性： 栈易于理解和实现。
2. 效率： 插入和删除操作的时间复杂度为 O(1)。
3. 函数调用管理： 栈有效地管理函数调用和变量存储。
4. 撤销/重做功能： 栈支持应用程序中的撤销和重做操作。

缺点

1. 访问受限： 元素只能访问栈的顶部。
2. 大小限制： 栈可能根据实现有大小限制。
3. 不适用于所有场景： 栈特定于 LIFO 行为，在其他情况下可能不适用。

实施

文件名： StackExample.java

输出

Top element:30
Popped element:30
Is stack empty?false
Stack size:2
Stack elements:
10
20

5) Queue

队列是一种 Java 中的线性数据结构，遵循先入先出 (FIFO) 原则。它表示一个元素集合，其中元素在尾部插入，在头部移除。

特点

1. 入队： 将元素添加到队列的尾部。
2. 出队： 从队列的前部移除元素。
3. 查看： 在不移除队列前端元素的情况下检索它。
4. 大小： 确定队列中元素的数量。
5. 空检查： 检查队列是否为空。

优点

1. FIFO行为： 元素按照插入的顺序进行处理，确保原始序列的保持。
2. 高效的插入和删除： 从队列中添加和删除元素速度很快，并且具有 O(1) 的恒定时间复杂度。
3. 同步： Java 提供了同步队列实现，使其在并发编程中是安全的。
4. 标准化接口： Java 中的 Queue 接口提供了一组通用方法，可以轻松地在不同的队列实现之间进行交换。

缺点

1. 不支持随机访问： 队列不支持直接访问中间的元素。访问特定位置需要先出队前面的元素。
2. 大小受限： 某些队列实现具有固定的大小或容量，在超过最大大小时会导致溢出或异常。
3. 低效搜索： 在队列中搜索元素需要出队直到找到匹配项，导致线性搜索，时间复杂度可能很高。

实施

文件名： QueueExample.java

输出

Front element:10
Dequeued element:10
Dequeued element:20
Dequeued element:30
Dequeued element:40
Dequeued element:50

6) HashMap

HashMap 是一种 Java 数据结构，提供了一种存储和检索键值对的方法。它是 Java 集合框架的一部分，并基于哈希表数据结构实现。

函数

• put(key, value)： 将指定的键值对插入 HashMap。
• get(key)： 检索与指定键关联的值。
• containsKey(key)： 检查 HashMap 是否包含指定的键。
• containsValue(value)： 检查 HashMap 是否包含指定的值。
• remove(key)： 从 HashMap 中移除与指定键关联的键值对。
• size()： 返回 HashMap 中键值对的数量。
• isEmpty()： 检查 HashMap 是否为空。
• keySet()： 返回一个包含 HashMap 中所有键的 Set。
• values()： 返回一个包含 HashMap 中所有值的 Collection。
• clear()： 从 HashMap 中移除所有键值对。

优点

1. 高效检索： HashMap 提供基于键的快速值检索，时间复杂度为 O(1)。
2. 灵活的键值对： HashMap 允许任何非 null 对象作为键，从而可以自定义键来存储和检索数据。
3. 动态大小： HashMap 可以动态地增长或缩小，以处理可变数量的数据。
4. 与 Java 集合框架兼容： HashMap 实现 Map 接口，允许与其他集合类无缝集成。

缺点

1. 缺乏顺序： HashMap 不保留元素顺序。如果需要特定顺序，请使用 LinkedHashMap 或 TreeMap。
2. 内存开销增加： HashMap 需要额外的内存来存储哈希码和内部结构，与更简单的数据结构相比，内存开销更大。
3. 迭代速度较慢： 由于遍历底层哈希表，迭代 HashMap 可能比数组或列表慢。

实施

文件名： HashMapExample.java

输出

Age of John:25
Age of Alice:30
Is Bob present?true
Key-Value pairs in the HashMap:
Bob:35
Alice:32
Size of the HashMap:2

7) HashSet

HashSet 是一种 Java 数据结构，它实现 Set 接口并在哈希表中存储元素。

特点

1. 存储唯一元素： HashSet 不允许重复元素。HashSet 中的每个元素都是唯一的。
2. 使用基于哈希的查找： HashSet 使用每个元素的哈希值来确定其存储位置，从而实现高效的元素检索。
3. 无序集合： HashSet 中的元素未按特定顺序存储。元素顺序可能会随时间而改变。

优点

1. 快速元素查找： HashSet 提供快速的查找操作，从而可以高效地检查元素是否存在于集合中。
2. 无重复元素： HashSet 自动处理重复元素并确保每个元素都是唯一的。
3. 与 Java 集合框架集成： HashSet 实现 Set 接口，使其与其他 Java 集合框架中的集合类兼容。

缺点

1. 不保证顺序： HashSet 不维护元素顺序。如果元素顺序很重要，则不适合使用 HashSet。
2. 无索引： HashSet 不提供直接索引或按位置访问元素。要访问元素，您需要遍历集合。
3. 内存开销较高： HashSet 需要额外的内存来存储哈希值并维护哈希表结构，与某些其他数据结构相比，内存使用量更高。

实施

文件名： HashSetExample.java

输出

HashSet:[Apple, Grapes, Mango, Orange, Banana]
Contains 'Apple':true
Updated HashSet:[Apple, Grapes, Mango, Orange]
Size of HashSet:4
Is HashSet empty?true

8) TreeSet

TreeSet 是 Java 中 SortedSet 接口的实现，它使用一种自平衡二叉搜索树（红黑树）来以排序顺序存储元素。

优点

1. 排序顺序： TreeSet 根据其自然排序顺序或自定义比较器自动以排序顺序维护元素。它允许按升序或降序高效地搜索和检索元素。
2. 无重复元素： TreeSet 不允许重复元素。它确保集合中的每个元素都是唯一的，这在应避免重复值的场景中可能很有用。
3. 高效操作： TreeSet 提供高效的插入、删除和搜索等操作。这些操作的时间复杂度为 O(log n)，其中 n 是集合中的元素数量。
4. 导航集操作： TreeSet 提供额外的导航方法，如 higher()、lower()、ceiling() 和 floor()，允许您查找大于、小于或等于给定值的元素。

缺点

1. 开销： TreeSet 需要额外的内存来存储内部数据结构，与 HashSet 等其他集实现相比，内存开销可能更高。
2. 插入和删除速度较慢： TreeSet 中的插入和删除操作涉及维护元素的排序顺序，这可能需要树重构。与 HashSet 或 LinkedHashSet 相比，这可能会使这些操作稍慢一些。
3. 自定义限制： TreeSet 主要设计用于自然排序或单个自定义比较器。对于多个排序标准或复杂的排序逻辑，它可能需要更多灵活性。

函数

• add(element)： 在保持排序顺序的同时将元素添加到 TreeSet。
• remove(element)： 从 TreeSet 中移除指定的元素。
• contains(element)： 检查 TreeSet 是否包含指定的元素。
• size()： 返回 TreeSet 中的元素数量。
• first()： 返回 TreeSet 中最小（最低）的元素。
• last()： 返回 TreeSet 中最大（最高）的元素。
• higher(element)： 返回 TreeSet 中严格大于给定元素的最小元素。
• lower(element)： 返回 TreeSet 中严格小于给定元素的最大元素。

实施

文件名： TreeSetExample.java

输出

Elements in the TreeSet:[1, 2, 4, 5, 8]
Does TreeSet contain 4? true
Elements in the TreeSet after removal:[1, 4, 5, 8]
Size of the TreeSet:4First element:1
Last element:8
Iterating over the TreeSet:
1
4
5
8

9) TreeMap

TreeMap 是 Java 中的一个类，它实现 Map 接口，并提供基于键的自然顺序或自定义比较器的已排序键值映射。

优点

1. 排序顺序： TreeMap 以排序顺序维护键，从而可以高效地进行搜索、检索和基于范围的操作。
2. 键值映射： TreeMap 存储键值对，从而可以根据关联键高效地查找和检索值。
3. 红黑树实现： TreeMap 内部使用平衡二叉搜索树（红黑树），即使对于大型数据集也能确保高效的性能。
4. 支持自定义比较器： TreeMap 允许使用自定义比较器来定义键的排序顺序，从而在排序标准方面提供灵活性。

缺点

1. 内存开销： TreeMap 需要额外的内存来存储内部树结构和关联对象，与 HashMap 等更简单的数据结构相比，内存使用量更高。
2. 插入和删除速度较慢： TreeMap 中的插入和删除操作由于需要进行树重构，时间复杂度为 O(log n)，因此比 HashMap 或 LinkedHashMap 慢。
3. 对无序数据的性能较低： TreeMap 对已排序数据性能良好，但处理无序数据或频繁修改时性能可能会下降，因为它需要维护排序顺序。

函数

• put(key, value)： 将键值对插入 TreeMap。
• get(key)： 检索与指定键关联的值。
• containsKey(key)： 检查 TreeMap 是否包含特定键。
• remove(key)： 移除与指定键关联的键值对。
• size()： 返回 TreeMap 中键值对的数量。
• keySet()： 返回 TreeMap 中所有键的集合。
• values()： 返回 TreeMap 中所有值的集合。
• entrySet()： 返回 TreeMap 中键值对的集合。

实施

文件名： TreeMapExample.java

输出

Score of Alice:90
Score of Charlie:95
Score of David:87
Scores in the TreeMap:
Alice:90
Bob:85
Charlie:95
David:87

10) Graph

图是一种数据结构，表示一组相互连接的节点或顶点。它们由顶点和边组成，其中顶点代表实体，边代表实体之间的关系。

优点

1. 多功能性： 图可以表示各种现实世界的场景，因此适用于各种应用，例如社交网络、交通系统和计算机网络。
2. 关系表示： 图提供了一种表示实体之间关系和连接的自然方式，从而可以有效地分析和遍历这些关系。
3. 高效搜索和遍历： 图算法，如广度优先搜索 (BFS) 和深度优先搜索 (DFS)，可以高效地遍历和搜索图的顶点和边。
4. 建模复杂关系： 图可以建模复杂的关系，包括层级结构、循环依赖以及实体之间的多重连接。

缺点

1. 空间复杂度： 图可能会消耗大量内存，尤其是具有许多顶点和边的超大型图。
2. 操作的复杂性： 某些图操作，例如查找最短路径或检测循环，可能具有高时间复杂度，尤其是在密集图中。
3. 维护困难： 修改或更新图可能很复杂，因为图结构的更改可能会影响其连接性和现有算法。

实施

文件名： GraphExample.java

输出

BFS traversal: 0 1 2 3 4 
DFS traversal: 0 1 3 2 4

11) Tree

树是计算机科学中一种常用的数据结构，用于表示层级结构。它由通过边连接的节点组成，每个节点可以有零个或多个子节点。

优点

1. 层级结构： 树提供了一种表示层级关系（如文件系统、组织结构图或 HTML/XML 文档）的自然方式。
2. 高效搜索： 二叉搜索树能够以 O(log n) 的时间复杂度进行高效搜索，因此适用于存储和检索排序数据。
3. 快速插入和删除： 树数据结构提供高效的插入和删除操作，尤其是在平衡时，例如 AVL 树或红黑树。
4. 有序遍历： 二叉搜索树的中序遍历按排序顺序给出元素，这对于打印元素或查找下一个/上一个元素等任务很有用。

缺点

1. 高内存开销： 树需要额外的内存来存储节点引用或指针，与数组或列表等线性数据结构相比，这可能导致内存使用量更高。
2. 实现复杂： 与数组或列表等其他数据结构相比，实现和维护树数据结构可能更复杂，尤其是对于平衡树变体。
3. 操作有限： 某些树变体（如二叉搜索树）不支持查找第 k 小元素或查找元素排名等高效操作。

函数

1. 插入： 将新节点添加到树中。
2. 删除： 从树中移除节点。
3. 搜索： 在树中查找特定节点或元素。
4. 遍历： 以不同顺序遍历树，例如中序、前序或后序。
5. 高度/深度： 计算树的高度或深度。
6. 平衡： 确保树保持平衡以维持高效的操作。

实施

文件名： TreeExample.java

输出

In-order Traversal:20 30 40 50 60 70 80 
Search for value 40: true
Search for value 90: false
Minimum value in the tree: 20
Maximum value in the tree: 80