Java ArrayList 是如何工作的？

How does ArrayList work?

提问by AutoMEta

What data structure does an ArrayList use internally?

ArrayList 内部使用什么数据结构？

采纳答案by jjnguy

Internally an ArrayListuses an Object[].

在内部ArrayList使用一个Object[].

As you add items to an ArrayList, the list checks to see if the backing array has room left. If there is room, the new item is just added at the next empty space. If there is not room, a new, larger, array is created, and the old array is copied into the new one.

当您向 中添加项目时ArrayList，该列表会检查后备数组是否还有剩余空间。如果有空间，则新项目将添加到下一个空白空间。如果没有空间，则会创建一个新的更大的数组，并将旧数组复制到新数组中。

Now, there is more room left, and the new element is added in the next empty space.

现在，剩下更多的空间，新元素被添加到下一个空白空间。

Since people really like the source code:

由于人们真的很喜欢源代码：

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

Straight out of the JDK.

直接从JDK中出来。

回答by SLaks

It uses an Object[], and makes a bigger array when the array gets full.

它使用Object[], 并在数组变满时创建一个更大的数组。

You can read the source code here.

您可以在此处阅读源代码。

回答by Tom

It uses an array, and a couple of integers to indicate the first value - last value index

它使用一个数组和几个整数来表示第一个值 - 最后一个值索引

private transient int firstIndex;

private transient int lastIndex;

private transient E[] array;

Here'san example implementation.

这是一个示例实现。

回答by Ryan Brunner

Typically, structures like ArrayListsare implemented by a good old fashioned array defined within the class and not directly accessible outside the class.

通常，类似ArrayLists的结构由类内定义的老式数组实现，并且不能在类外直接访问。

A certain amount of space is initially allocated for the list, and when you add an element that exceeds the size of the array, the array will be reinitialized with a new capacity (which is typically some multiple of the current size, so the framework isn't constantly re-allocating arrays with each new entry added).

最初为列表分配了一定量的空间，当您添加超过数组大小的元素时，数组将重新初始化为新容量（通常是当前大小的一些倍数，因此框架是'不要在添加每个新条目时不断重新分配数组）。

回答by John Topley

The Java platform source codeis freely available. Here's an extract:

在Java平台的源代码是免费提供的。这是一个摘录：

public class ArrayList<E> extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
  /**
   * The array buffer into which the elements of the ArrayList are stored.
   * The capacity of the ArrayList is the length of this array buffer.
   */
  private transient E[] elementData;
  .
  .
  .
}

回答by Jes

ArrayLists use arrays to hold the data. Once the number of elements exceeds the allocated array it copies the data to another array, probably double the size.

ArrayLists 使用数组来保存数据。一旦元素数量超过分配的数组，它会将数据复制到另一个数组，大小可能翻倍。

A (minor) performance hit is taken when copying the array, it's therefore possible to set the size of the internal array in the constructor of the array list.

复制数组时（次要）性能受到影响，因此可以在数组列表的构造函数中设置内部数组的大小。

Furthermore it implements java.util.Collectionand and java.util.list, and it's is therefore possible to get the element at a specified index, and iterable (just like an array).

此外，它实现了java.util.Collectionand java.util.list，因此可以获取指定索引处的元素，并且是可迭代的（就像数组一样）。

回答by kapil

ArrayList uses an Array of Object to store the data internally.

ArrayList 使用对象数组在内部存储数据。

When you initialize an ArrayList, an array of size 10(default capacity) is created and an element added to the ArrayList is actually added to this array. 10 is the default size and it can be passed as a parameter while initializing the ArrayList.

初始化 ArrayList 时，会创建一个大小为10（默认容量）的数组，并将添加到 ArrayList 的元素实际添加到该数组中。10 是默认大小，可以在初始化 ArrayList 时作为参数传递。

When adding a new element, if the array is full, then a new array of 50% more the initial size is created and the last array is copied to this new array so that now there are empty spaces for the new element to be added.

添加新元素时，如果数组已满，则会创建一个比初始大小多 50% 的新数组，并将最后一个数组复制到这个新数组中，以便现在有空白空间可以添加新元素。

Since the underlying data-structure used is an array, it is fairly easy to add a new element to the ArrayList as it is added to the end of the list. When an element is to be added anywhere else, say the beginning, then all the elements shall have to move one position to the right to create an empty space at the beginning for the new element to be added. This process is time-consuming (linear-time). But the Advantage of ArrayList is that retrieving an elementat any position is very fast (constant-time), as underlying it is simply using an array of objects.

由于所使用的底层数据结构是一个数组，因此在将新元素添加到列表末尾时将新元素添加到 ArrayList 是相当容易的。当一个元素要添加到其他任何地方时，比如开头，那么所有元素都必须向右移动一个位置，以在开头创建一个空白空间来添加新元素。这个过程很耗时（线性时间）。但是 ArrayList 的优点是在任何位置检索元素都非常快（恒定时间），因为它的底层只是使用对象数组。

回答by Manikandan Rajaminor

ArrayListhas the basic data structure:

ArrayList有基本的数据结构：

private transient Object[] elementData;

When we actually create an ArrayListthe following piece of code is executed:

当我们实际创建时ArrayList，会执行以下代码：

 this.elementData = new Object[initial capacity];

ArrayListcan be created in the two ways mentioned below:

ArrayList可以通过下面提到的两种方式创建：

1. List list = new ArrayList();

1. List list = new ArrayList();

The default constructor is invoked and will internally create an array of Objectwith default size 10.

调用默认构造函数并将在内部创建一个Object默认大小为 10的数组。

1. List list = new ArrayList(5);

2. List list = new ArrayList(5);

When we create an ArrayListin this way, constructor with an integer argument is invoked and create an array of Objectwith default size 5.

当我们ArrayList以这种方式创建 an时，会调用带有整数参数的构造函数并创建一个Object默认大小为 5的数组。

Inside the addmethod there is check whether the current size of filled elements is greater/equal to the maximum size of the ArrayListthen it will create new ArrayListwith the size new arraylist = (current arraylist*3/2)+1and copy the data from old to new array list.

在该add方法内部，检查填充元素的当前大小是否大于/等于的最大大小， ArrayList然后它将创建新ArrayList的大小为 newarraylist = (current arraylist*3/2)+1并将数据从旧数组列表复制到新数组列表。

回答by Krishna

It uses an Object[]. When the array is full it creates a new array which is 50% bigger in size and copies current elements to new array. It happens automatically.

它使用一个对象[]。当数组已满时，它会创建一个大小增加 50% 的新数组，并将当前元素复制到新数组中。它会自动发生。

回答by Mani Manu

as i understand is that

我的理解是

ArrayList class implements List interface and (as interface only extends other interface)List interface extends Collection interface. while talking about arraylist when we initialize in memory it reserve by default space 10> and create array of Integer which you normally use. when this this array is full then the another array of interger is created which is greater then default size.

ArrayList 类实现了 List 接口并且 （因为该接口只扩展了其他接口）List 接口扩展了 Collection 接口。在谈论 arraylist 时，当我们在内存中初始化时，它默认保留空间10> 并创建您通常使用的 Integer 数组。当此数组已满时，将创建另一个大于默认大小的整数数组。

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

now in memory as => Integer[] list = new Integer[10];

now suppose that you enter 1,2,3,4,5,6,7,8,9,10 array is full now and what happen when you enter 11in the memory another array of Integer is created which is greater then by default and all element in old array is copied in new array. Internally arraylist user Object[] array.

现在在内存中 => Integer[] list = new Integer[10];

现在假设您输入 1,2,3,4,5,6,7,8,9,10 数组现在已满，当您在内存中输入11时会发生什么情况会创建另一个整数数组，默认情况下该数组更大并将旧数组中的所有元素复制到新数组中。内部arraylist user Object[] 数组。

thats how arrayList work

这就是 arrayList 的工作方式