Java 中的动态数组

在创建不同复杂程度的程序时，每个开发人员都会使用许多数据类型，包括数组。这种结构非常适合存储一组单一类型，提供出色的性能，并且通常很方便。 数组的一个显着缺点是它们是静态的：必须提前指定它们的大小。然而，程序员还不知道如何预测未来（当然，除非人工智能能够以惊人的速度处理信息并能够预测任何事件）。为此，我们创建了一个可以在程序运行时改变其大小的结构。它被称为动态数组。

JavaRush 课程中的动态数组

该主题在 Java 语法任务中的 JavaRush 课程的第 7 级和部分第 8 级中以非常容易理解和清晰的方式进行了介绍。在多个讲座和多达 18 个问题的过程中，涵盖了关键问题、动态数组的类型以及它们之间的差异，包括性能。这个主题非常重要，因为动态数组可以缓解开发人员的抑郁和头痛，并节省大量时间。

什么是动态数组？

动态数组是在程序执行过程中可以改变其大小的数组。在Java中，这个角色主要由ArrayList和LinkedList类来扮演。与数组不同，ArrayList 和 LinkedList 只包含引用数据类型，即它们只能存储对象。幸运的是，Java 具有自动装箱和自动拆箱机制，允许您在动态数组中存储基本类型。与静态数组一样，动态数组是同构的，即它可以存储单一数据类型。然而，由于继承机制和接口的正确使用，可以在一个动态数组中存储从一个公共类继承的一系列不同的类，但下面会详细介绍。也就是说，静态数组的工作方式是这样的： 而Java 中的动态数组的工作方式如下（继续第三步的图）： Java 使用特殊的原生函数来复制数组，所以这样的“移动”并不是很方便。昂贵的。

为什么我们需要动态数组？

Java 中的动态数组用于处理在编写程序时其大小未知的同类数据集。例如，您可能希望缓存当前正在使用该应用程序的每个客户端的数据。无法提前预测此类客户的数量。如果没有动态数组，可以通过以下选项解决此问题：

1. 创建一个100%可能满足需求的大数组；
2. 创建一个用作缓冲区的静态数组；
3. 应用其他动态结构，例如集合。

第一个选项仅适用于严格限制范围的情况。在其他情况下，这样的数组会占用大量的内存空间，效率极低。第二个需要实施额外的机制来清除缓冲区、读取等等。由于功能差异，第三种也有缺点。

Java中动态数组的作用是什么

在Java 语言中，ArrayList 和LinkedList 类充当动态数组。最常用的是 ArrayList，因为它充当经典数组，与实现双向链表概念的 LinkedList 不同。我们稍后再讨论。

ArrayList、LinkedList——概念及操作规则

ArrayList是一个经典的数组，可以在程序执行过程中扩展。它基于常规数组：创建时其大小为 10 个元素。随着尺寸的增加，容量也随之增加。ArrayList 的工作规则：

• 就像静态数组一样，它从0开始索引；
• 末尾插入和索引访问非常快 - O(1)；
• 要在开头或中间插入元素，您需要将所有元素复制到右侧一个单元格，然后将新元素粘贴到所需位置；
• 按值访问取决于元素的数量 - O(n)；
• 与经典数组不同，它可以存储 null；

对于 LinkedList，一切都有点复杂：它基于双向链表。也就是说，从结构上来说，这个动态Java数组是许多分散的互相引用的对象。用图片来解释更容易。在 LinkedList 中，我们有一个主对象Head，它存储有关元素数量的信息，以及指向第一个和最后一个元素的链接： 现在字段size = 0是 ,first和last = null。添加到此列表的每个元素都是单独内部对象的内容。让我们添加一个元素Johnny： 现在我们有一个值为“Johnny”的节点。对于主元素，第一个和最后一个元素的链接指向新节点。该对象还具有到上一个和下一个元素的链接。到前一个元素的链接将始终为 null，因为这是第一个元素，而到下一个元素的链接将始终为 null，因为它尚不存在。让我们解决这个问题： 添加一个值为“Watson”的新元素，它成为第二个元素。请注意，第一个元素有一个next指向下一个元素的字段，新元素有一个previous指向前一个元素的字段。对于主元素，最后一个元素的链接现在指向新节点。下图显示了如何将元素添加到列表的中间： 添加了一个新元素“Hamish”。要将其插入到列表的中间，只需重新分配元素的链接即可，如图所示。这些插图解释了顶层双向链表的过程，但没有详细说明。总结一下 LinkedList 的故事，我们可以得出其运行的几个规则：

• 就像数组一样，索引从0开始；
• 对第一个和最后一个元素的访问不依赖于元素的数量 - O(1)；
• 通过索引获取元素，从列表中间插入或删除取决于元素的数量 - O(n)；
• 可以使用迭代器机制：那么插入和删除将在常数时间内发生；
• 与经典数组不同，它可以存储 null。

代码示例

让我们来看一些例子。代码片段包括 ArrayList 和 LinkedList 的示例。

创建

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

添加元素

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

乍一看，add()AND方法addLast()执行相同的功能，但方法add()是从接口来到 LinkedList List，而方法addLast又来自接口Deque。LinkedList 实现了这两个接口。在这种情况下，一个好的做法是使用最适合上下文的方法。如果LinkedList用作队列，那么最好使用addLast. 如果 LinkedList 用作列表，则使用add().

删除一个元素

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

如果按索引删除对象，则该方法返回已删除的对象。如果按值删除对象（或者删除 LinkedList 的第一个或最后一个元素），则如果找到并删除该对象，该方法将返回true ，否则返回 false。

访问项目并搜索列表

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

绕圈行走

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

这里值得多说几句关于搜索的事情。许多新手开发人员在搜索列表中的元素时，会在循环中开始搜索，将所有元素与搜索到的元素进行比较，尽管存在方法indexOf()和lastIndexOf()。您还可以使用该方法contains()来获取元素在列表中的事实：

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

进一步阅读的链接

1. 这里有一篇关于从 ArrayList 中删除元素的优秀文章。由于这是一个动态 Java 数组，因此删除元素有很多微妙之处。
2. 此处详细说明了 ArrayList 的工作原理。
3. 有关 LinkedList 的更多信息。
4. Habr 的几篇关于ArrayList和LinkedList的文章。