ArrayList类详解【第1部分】

本文将详细介绍 Collections Framework 中的 ArrayList 类，该类可能是最容易理解的，因为它基于常规数组。在面试中你几乎肯定会被问到关于这个类及其在 Java 中的实现的问题。在第二部分中，我们将分析其余方法并编写我们自己的数字动态数组的实现。ArrayList类继承自AbstractList类，并实现了以下接口：List、RandomAccess、Cloneable、Serializable。 ArrayList类详细分析[第2部分] ArrayList类支持动态数组，可以根据需要进行扩展。它的必要性和有效性是通过以下事实来解释的：常规数组具有固定长度：一旦创建，它就不能增长或收缩，如果不知道需要多大的数组，就会施加限制。本质上，ArrayList 类是对象引用的可变长度列表数组。重要的是要理解，当从内部数组中删除元素时，内部数组的大小（单元数）不会自动减小。size事实上，表示数组中实际存在的元素数量的变量 的值减少了。假设我们创建 ArrayList 类的一个新对象并向其添加 5 个元素。默认情况下，创建一个包含 10 个元素的数组。在这种情况下，我们对象的所谓容量（大小/体积）将等于 10，但变量的值size将等于 5。当我们删除元素时，我们会看到变量值的变化size，因为我们.length无法访问 ArrayList 类的内部数组并找出它的长度。可以使用附加方法来减小大小trimToSize()，这将在稍后讨论。让我们看看类字段。

• 负责动态数组默认体积的字段：

  private static final int DEFAULT_CAPACITY = 10

  当创建一个新对象new ArrayList<>()（不带参数的构造函数）时，内部会创建一个包含10个元素的数组。

• 存储集合所有元素的字段：

  transient Object[] elementData

  用关键字标记transient- 使用标准序列化算法时，该字段不会写入字节流。值得注意的是，该字段没有用关键字 标记private，但这样做是为了方便从嵌套类（例如 SubList）访问该字段。

• 一个计数器字段，用于存储数组中实际元素的数量：

  private int size

  当执行插入和删除等操作时，该值会递增/递减。

该类中还有 3 个字段，但本质上它们是附加的，因此没有必要考虑它们。该类具有三个构造函数：

1. public ArrayList()– 创建一个包含 10 个元素的空列表数组；
2. public ArrayList(Collection < ? extends E > c)– 创建一个列表数组，并使用传递的集合中的元素进行初始化（如果我们想基于某个集合创建一个新的 ArrayList）；
3. public ArrayList(int initialCapacity)– 创建一个具有初始容量的列表数组。如果传递的参数initialCapacity大于0，则创建指定大小的数组（内部字段elementData被分配一个指向大小为initialCapacity的Object类型的新数组的链接）。如果参数为 0，则创建一个空数组。如果指定的参数小于 0，则抛出 IllegalArgumentException。

创建对象

List < String> list = new ArrayList<>();

新创建的对象list包含属性（字段）elementData和size。在我们的例子中，值存储elementData只不过是特定类型的数组（在通用 - 中指定<>）String[]。如果调用不带参数的构造函数，则默认情况下将创建一个包含 10 个 Object 类型元素的数组（当然，会强制转换为该类型）。 添加元素 传统上，向列表数组添加元素是使用add().

public boolean add(E элемент)

好吧，让我们添加： list.add("0"); 在这个方法中，调用该方法的重载版本add()，标记为private，它又将三个参数作为输入：要添加的元素、内部数组及其大小。在私有方法中，会进行一次检查：如果传递的 size 参数等于内部数组的长度（即数组已满），则将方法的结果（字段的grow(int minCapacity)当前值）赋给数组size + 1 传递给该方法，因为有必要考虑要添加的元素），其中为数组内部分配一个指向通过复制原始数组的元素获得的新创建数组的链接：

Arrays.copyOf(elementData, newCapacity(minCapacity))

作为该方法的第二个参数，copyOf我们指示该方法的结果newCapacity(int minCapacity)，其中计算新的数组大小。它使用以下公式计算： int newCapacity = oldCapacity + (oldCapacity >> 1) 对于具有默认大小的数组，以下情况成立： >> 1– 按位右移一位（将数字减少到一半的运算符）。本质上，它的意思是除以 2 的 1 次方。事实证明，我们将 10 除以 2 并加上 10。总计，数组的新容量为 15，但由于我们要添加第 11 个元素，因此 15 + 1 = 16. 让我们回到我们的列表，假设我们已经向其中添加了 10 个元素，并尝试添加 11 个。检查将显示数组中没有空间。相应地，创建并调用一个新数组Arrays.copyOf，该数组内部使用系统方法System.arraycopy()。 或者，这里是 JavaRush 上一篇文章中的一个清晰示例： 在完成所有这些检查并在必要时增加数组的大小之后，然后在私有方法中，add()将一个新元素添加到数组的末尾，并将当前参数size增加 1 。旧数组随后将由垃圾收集器处理。这就是动态数组的工作原理：当我们添加元素时，我们检查其中是否还有空间。如果有空间，那么我们只需将元素添加到数组的末尾即可。结束并不意味着数组中的最后一个单元格，而是与值 对应的单元格size。我们将第一个元素添加到数组中；它被放置在索引为 [0] 的单元格中。字段值size增加了 1 并且 = 1。我们添加下一个元素：我们看到size = 1，因此我们将该元素放置在索引为 [1] 的单元格中，依此类推。该方法有一个带有两个参数的重载版本：

public void add(int index, E element)

我们可以指定要添加元素的单元格的位置（索引）。首先，检查指定索引值的正确性，因为有可能指定不正确的索引，该索引将指向不存在或根本不存在的单元格。检查索引：index > size || index < 0– 如果指定的索引大于数组的当前大小或小于 0，则抛出异常IndexOutOfBoundsException。然后，如有必要，增加数组的大小，类似于上面的示例。您可能听说过，在数组中进行添加/删除操作期间，某些内容会移动到某处（向右或向左）。因此，移位是通过复制数组来执行的： System.arraycopy(elementData, index, elementData, index + 1, s - index); 位于指定索引右侧的所有元素将向右移动一位（索引+1）。并且只有在此之后，才会将新元素添加到内部数组的指定索引处。由于我们已将数组的一部分向右移动了一位（未创建新数组），因此我们需要的单元格将可以自由写入。旧数组的链接被删除，将来它将被垃圾收集器接管。将“maserati”粘贴到已被占用的单元格 [3] 中： 因此，当在索引处插入元素并且数组中没有可用空间时，调用System.arraycopy()将发生两次：第一次在 中grow()，第二次在方法本身中add(index, value)，这显然会影响整个添加操作的速度。因此，当需要向内部数组写入另一个元素，但那里没有空间时，ArrayList 内部会发生以下情况：

• 创建一个新数组，其大小是原始数组的 1.5 倍，再加上一个元素。
• 旧数组中的所有元素都将复制到新数组
• 新数组存储在ArrayList对象的内部变量中，旧数组被声明为垃圾。

可以使用以下方法手动增加 ArrayList 类型的对象的容量：

public void ensureCapacity(int minCapacity)

通过提前增加阵列容量，您可以避免以后额外重新分配 RAM。该方法增加内部数组的大小以容纳传递给 的元素数量minCapacity。该方法ensureCapacity()不影响字段size，它影响capacity内部数组（的大小）。我再次强调，size两者是capacity不同的东西，不要混淆它们非常重要！如果要将构建 ArrayList 的基础数组的大小减少到当前实际存储的元素数，则应该调用trimToSize(). 从集合中移除元素后，size()会显示实际存在的元素数量，并且capacity不会减少！假设：我们输入了 100 个元素，删除了前 50 个，size它会变成 50，所以capacity它仍然是 100。为了减少 和capacity，我们需要使用 方法trimToSize()，它将我们的整个容量调整为当前大小。怎么样？复制我们的数组，以便不留任何空单元格（新数组的长度只是等于大小字段）。 您还可以使用 向我们的集合添加元素addAll。

public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);

第一个选项允许您将方法参数中指定的集合（例如另一个工作表）中的所有元素添加到为其进行方法调用的原始集合（在末尾插入）。传递的集合（也可以是集合）使用toArray(). 当然，加法操作也是利用复制来进行的。第二个是将所有元素添加collection到列表中，从索引开始index。在这种情况下，所有元素都将向右移动列表中元素的数量collection。删除元素 首先，让我们看一下从 ArrayList 中删除元素的经典选项。

public E remove(int index)

按索引执行删除，并将所有后续（指定索引处的元素之后）元素向左移动，从而关闭“洞”。它还返回已删除的元素 (E)，该元素在删除之前已写入附加变量，我们通过方法调用获得该变量的值。要理解 E 是什么，您需要熟悉所谓的泛型类型。符号 E 表示该方法返回创建 ArrayList 对象时指定的数据类型（记住：List <String> list因此，在这种情况下，E 将被“替换” String）。为了获得一般性的理解，我强烈建议您熟悉泛型类型。检查输入索引的正确性，然后在方法内部，元素并没有完全删除，而是调用了一个私有方法fastRemove(Object[] es, int i)，其中已经发生了删除。我们将数组和指定的索引作为输入传递给该方法。使用 复制元素System.arraycopy()，减小数组的大小，然后将 null 分配给最后一个元素。值得注意的是，并没有创建一个新数组： System.arraycopy(es, i + 1, es, i, size - 1 - i); 指定索引（i+1）下位置右侧的部分被复制到我们的原始数组（es）中，并且从该位置开始定位(i) 要删除的元素所在的位置。因此，我们向左移动并删除了元素。 让我们尝试从下面的数组中删除索引 3 处的元素： 让我们考虑该方法的第二个版本：

public boolean remove(Object o)

该方法从列表中删除传递的元素o，或更准确地说，从指定链接处的对象中删除。如果列表中存在某个元素，则该元素将被删除，并且所有元素都会向左移动。如果列表中存在该元素并且已成功删除，则该方法返回 true；否则返回 false。与按索引删除的选项类似，调用该方法fastRemove()，其中发生完全相同的操作。不同的是，该方法额外通过Object类的remove(Object o)方法来搜索所需的对象。equals()当按值删除时，循环将遍历列表中的所有元素，直到找到匹配项。只有找到的第一个元素才会被删除。让我们总结一下：从动态数组中删除元素时，不会像常规数组那样留下空洞（删除的单元格不会为空）。所有后续元素（位于索引右侧）均向左移动一位。还有几种附加方法可用于不同程度地从列表中删除元素。让我们简单地看一下它们。清理我们的收藏：

public void clear()

一个简单的循环for迭代数组的所有元素，为每个元素分配 null。您可以从我们的集合中删除包含在另一个传输的集合中的那些元素，如下所示：

public boolean removeAll(Collection< ?> c)

如果您需要删除多个元素，您可能不应该在条件循环中执行此操作：使用该方法更方便、更安全removeAll()。它接受将从列表中删除的元素的集合。该集合必须包含与目标列表存储类型相同的元素。否则就会被扔掉ClassCastException。如果列表因方法调用而更改，则该方法将返回 true。 删除不属于传递集合的元素：

public boolean retainAll(Collection< ?> c)

假设我们有一个集合：

List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");

第二个：

List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");

然后listSecond.retainAll(listFirst)在之后listSecond会留下：

"White"
"Red"

由于“绿色”被删除，它不在listFirst. 但之后listSecond.removeAll(listFirst)它将listSecond保持：

"Green"
Удалorсь все элементы, которые есть в listFirst.

不属于传递的集合 - 意味着如果有元素不在传递的集合中，那么您需要从第一个（应用该方法的）元素中删除它们。属于转移的集合 - 因此，如果第一个和第二个（转移的）集合中都有一个元素，则第一个集合中的重复项将被销毁。

protected void removeRange(int fromIndex, int toIndex)

从列表中删除起始指定索引（包含）和结束指定索引（不包含）之间的所有元素。值得注意的是，该方法不能直接在 ArrayList 对象上调用。要使用它，您需要继承自AbstractList/ArrayList. 该方法还被另一个方法（subList，稍后讨论）使用。

public boolean removeIf(Predicate< ? super E> filter)

根据给定谓词从集合中删除元素。谓词本身是某种函数/算法/条件，根据该函数/算法/条件将删除与给定条件相对应的一个或多个元素。Predicate— 函数式接口（仅包含一个方法，因此可以用作 lambda），其工作原理是“接收一个参数 - 返回布尔值”。本质上，该方法重写了接口的实现Collection并实现了以下“策略”：它迭代元素并标记那些与我们的Predicate;匹配的元素。然后第二次运行以删除（并移动）在第一次迭代中标记的元素。让我们实现一个接口Predicate，如果两个对象相等则返回 true：

class SamplePredicate< T> implements Predicate< T>{
  T varc1;
  public boolean test(T varc){
     if(varc1.equals(varc)){
       return true;
  }
  return false;
  }
}

在另一个类中，让我们创建一个 ArrayListString和我们的类的一个对象，该对象实现Predicate：

ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();

varc1让我们将值“White” 写入 变量：

filter.varc1 = "White";

让我们在列表中添加几行：

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

让我们执行 list 上的方法removeIf，我们将带有条件的对象传递给该方法：

color_list.removeIf(filter);

结果，所有值为“White”的行都将从列表中删除，因为我们的“谓词”比较它们是否相等。最终列表：[黑、红、黄]。 更换元件

public E set(int index, E element)

将指定位置的元素替换index为传递的元素element。索引还必须大于零且小于最后一个元素的索引，否则会抛出异常IndexOutOfBoundsException。不会出现内部数组的副本。简单地说，插入一个新元素，而不是指定索引处的元素，即 覆盖该值。

public void replaceAll(UnaryOperator<e> operator)

更改集合的所有元素（可能有条件）。主要与lambda或匿名类结合使用（但为了清楚起见，在示例中我们将简单地使用实现接口的类）来实现接口UnaryOperator并定义其方法。我们来实现一下这个接口：

class MyOperator< T> implements UnaryOperator< T>{
   T varc1;
   public T apply(T varc){
     return varc1;
  }
}

在另一个类中，让我们创建一个 ArrayListString和我们的类的一个对象，该对象实现UnaryOperator：

ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();

varc1让我们将值“White” 写入 变量：

operator.varc1 = "White";

让我们在列表中添加几行：

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

让我们在列表上执行一个方法，replaceAll我们将向其传递对象operator：

color_list.replaceAll(operator);

结果，列表中的所有值都被替换为“白色”：[白色，白色，白色，白色，白色，白色]。例如，您可以通过以下方式从集合中的字符串中删除所有空格：

ArrayList< String> list = new ArrayList<>(Arrays.asList("A   ", "  B  ", "C"));
list.replaceAll(String::trim);

其他方法：您可以使用以下方法将 ArrayList 转换为常规数组：

public Object[] toArray()

或者

public < T> T[] toArray(T[] a)

- 这里返回数组的类型是在runtime 该方法中确定的，将允许：

1. 加快某些操作的速度；
2. 将数组作为参数传递给未重载的方法以直接接受集合；
3. 将新的基于集合的代码与无法识别集合的旧代码集成。

返回数组的副本对象：

public Object clone()

请注意，该方法clone()返回 Object 类型，因此调用它后您需要转换为所需的类。克隆创建一个新的独立对象。检查集合中是否存在对象：

public boolean contains(Object o)

检查列表中是否存在对象（内部使用 Object 类的 equals 方法，即比较引用），根据结果返回 true/false。除了通常的循环之外，您还可以使用以下方法迭代（访问每个元素，以及执行某些操作）集合：

public void forEach(Consumer< ? super E> action)

这是我们显示列表的方式：

List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));

如果不使用 lambda，您需要使用匿名类并重写accept接口方法Consumer：

numbers.forEach(new Consumer< Integer>() {
  @Override
   public void accept(Integer integer) {
      System.out.println(integer);
          }
});

通过索引获取元素：

public E get(int index)

用于随机访问集合元素。返回位于列表中指定索引处的元素。如果index < 0or 是index >=列表中元素的最大数量，则会抛出异常IndexOutOfBoundsException。这是从列表中检索元素的基本方法，并且无论 ArrayList 的大小如何，通过索引检索元素的时间将始终相同，因为它正在访问特定的数组单元格。查找指定对象的索引：

public int indexOf(Object o);
public int lastIndexOf(Object o);

这些方法返回列表中第一个（第一次遇到给定对象时）或最后一次出现（最后一次遇到给定对象时）元素的索引。如果列表中不存在该元素，该方法将返回 -1。 检查集合中的元素：

public boolean isEmpty();

如果列表为空（查看字段是否相等size 0），该方法返回 true，否则返回 false。如果列表仅包含 null 元素，该方法将返回 false。换句话说，此方法也考虑了 null 元素。找出列表中元素的数量：

public int size();

返回列表中的元素数量（大小字段值）。元素的数量可能与列表容量（capacity）不同。获取列表的迭代器：

public Iterator< E> iterator();

返回列表的迭代器，以便稍后在循环或任何其他处理中使用。迭代器实现快速失败行为。如果它运行整个集合并注意到对其进行了一些修改（不是使用迭代器方法获得的），它会立即抛出异常ConcurrentModificationException。迭代器有一个叫做 的东西modification count。当迭代器在每个之后迭代集合时next/hasNext/remove，它会检查此计数器。如果它与迭代器期望看到的不匹配，则会抛出异常。我不会在这里详细讨论迭代器。

public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)

返回列表的列表迭代器，以便稍后在循环或任何其他处理中使用。该接口扩展了列表的双向遍历和其元素修改的ListIterator接口。Iterator在重载版本中，您可以传递“遍历”开始的索引。本例中的索引表示该方法将开始其工作的第一个元素next()，并且当调用该方法时，previous()将从索引“passed index - 1”下的元素开始遍历。

public Spliterator <E> spliterator()

Java 8 引入了一种新型的后期绑定和快速失败迭代器，称为分隔符迭代器。分隔符迭代器允许您迭代元素序列，但它们的使用方式不同。Spliterator接口最重要的特性是它能够支持元素序列的各个部分的并行迭代，从而支持并行编程。