How does ArrayList work?

Question

What data structure does an ArrayList use internally?

Answer 1

Internally an ArrayList uses an 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.

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.

Answer 2

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

You can read the source code here.

Answer 3

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's an example implementation.

Answer 4

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

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).

Answer 5

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

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;
  .
  .
  .
}

Answer 6

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.

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.Collection and and java.util.list, and it's is therefore possible to get the element at a specified index, and iterable (just like an array).