ArrayList Implementation in Java

ArrayList 是 Java 集合框架中的一个类。它使用动态数组来存储对象。它与 Array 非常相似，但没有大小限制。我们可以随时添加或删除元素。我们可以使用 ArrayList 存储重复的元素；它在内部管理插入的顺序。

ArrayList 类比传统的 Array 更灵活。它实现了 List 接口，可以使用 List 接口的所有方法。它位于 java.util 包中。理解其实现对于任何希望在其代码中获得精通和优雅的 Java 开发人员来说都是基础。在本节中，我们将讨论 Java 中的 ArrayList 实现，以及它的特性、优点和最佳实践。

ArrayList 类继承了 AbstractList 类并实现了 List 接口。它的元素可以被随机访问。它不能用于原始类型，如 int、char 等；对于这些数据类型，我们需要一个包装类。

Array 和 ArrayList 之间的区别在于 ArrayList 提供了一个动态数组，可以在需要时进行扩展。在 Array 中，我们必须在初始化时指定 Array 的大小，但对于 ArrayList 则不必。默认情况下，它的大小为 10。

ArrayList 类可以声明如下

ArrayList 可以定义如下

请看以下示例

文件名：ArrayListLExample.java

输出

List objects are: [Sam, Sandy, Joe, Arya, Nik]
After Removing Nik, List Objects are: [Sam, Sandy, Joe, Arya]

从上面的示例可以看出，我们如何添加或删除 List 的对象。

让我们了解它是如何工作的

ArrayList 在内部如何工作？

当我们使用以下语法初始化 ArrayList 时

它会创建一个具有默认容量（10）的 Array。它调用 ArrayList 类的默认构造函数。它使用一个空数组实例来创建新对象，并且以下代码由 Java 编译器执行

在 Java 7 或更早版本中

在 Java 8 或更高版本中

在上面的代码片段中，我们可以看到一个内部创建的空 ArrayList，其默认容量为 10。当我们向其中添加第一个元素时，它将被扩展到 DEFAULT_CAPACITY。

ArrayList 使用 Object [] 数组来添加、删除和遍历元素。

对于 Java 8 之前的版本，它指定对象如下

在上面的代码片段中，我们可以看到数组大小将等于指定的 Array。

我们也可以定义具有特定容量的 List。当我们提供初始容量时，ArrayList 构造函数会在内部调用以在内部指定 Array。例如，如果我们定义一个容量为 20 的 ArrayList，我们必须如下定义 ArrayList

然后以下代码将由 Java 编译器执行

在 Java 7 或更早版本中

从上面的代码可以看出，数组大小将等于指定的 Array。

在 Java 8 或更高版本中

从上面的代码可以看出，数组大小将等于指定的 Array。

我们也可以通过执行以下代码行来创建 ArrayList 的对象

上面的代码将创建一个非空列表，其中包含 LinkedList 的对象。

ArrayList 的关键特性

• 动态调整大小： 与 Java 中固定大小的传统数组不同，ArrayList 会动态地调整自身大小，从而在存储元素方面具有灵活性，而无需担心大小限制。
• 随机访问： ArrayList 为检索或设置元素提供常量时间的位置访问，使其在随机访问操作方面效率很高。
• 支持泛型： ArrayList 支持泛型，可以实现类型安全的集合，并确保编译时类型检查，从而提高代码的可靠性。
• 可迭代接口： ArrayList 实现 Iterable 接口，方便使用增强 for 循环或迭代器轻松遍历元素。

ArrayList 是如何动态增长的？

当我们向 ArrayList 添加新对象时，它会检查 ArrayList 的初始大小，看是否有空间。如果新对象有足够的空间，它将简单地使用 add() 方法添加。如果空间不足以添加新对象，它将以该容量动态增加 Array 的大小。

考虑 add() 方法的以下实现（Java 7 及更高版本）

在上面的代码中，上面提到的代码

• ensureCapacityInternal() 用于确定当前已占用对象的数量和 Array 的最大大小。
• grow 方法用于扩展 Array 的新大小。
• minCapacity 确定对象的当前大小；它包括新指定的元素。
• copyOf 用于复制指定的 Array。
• max 用于返回传入参数的最大值。

ArrayList 实现细节

Java 中的 ArrayList 在内部由对象数组 (Object[]) 支持以存储元素。让我们探讨一些关键的实现细节

容量和大小： ArrayList 维护两个主要参数：容量和大小。容量表示内部数组的当前大小，而大小表示 ArrayList 中存在的元素数量。

调整大小策略： 当添加的元素超出当前容量时，ArrayList 会自动增加其容量以容纳新元素。它通常会将其内部数组的大小加倍，以在追加操作中保持摊销的恒定时间复杂度。

性能考虑： 虽然 ArrayList 在随机访问和在列表末尾插入/删除方面效率很高，但由于数组复制，从中间插入或删除元素会产生更高的计算开销。

遍历 ArrayList： ArrayList 提供了多种遍历其元素的方法，包括传统的 for 循环、增强 for 循环以及通过 iterator() 方法获取的迭代器。

ArrayList 的性能

在 ArrayList 中，add 操作需要 O(n) 时间；其他操作以线性时间运行。

size、isEmpty、get、set、iterator 和 listIterator 任务以 O(1) 的恒定时间运行。

总结

• ArrayList 是一个可定制的数组实现；我们可以动态地向 List 中添加对象。
• ArrayList 使用 Object 类数组来存储对象。
• 默认情况下，ArrayList 创建一个大小为 10 的数组。
• 在初始化 Array 时，我们可以指定 Array 的大小。
• 在添加或删除元素时，Array 中的空间将自动调整。

其动态调整大小、高效的随机访问和对泛型的支持使其成为管理元素集合的通用选择。通过理解其内部机制、利用最佳实践并了解性能注意事项，开发人员可以充分发挥 ArrayList 的潜力，编写出高效且健壮的 Java 代码。