Как работает ArrayList?

Он использует Object[] и создает больший массив, когда массив заполняется.

Вы можете прочитать исходный код здесь .

ArrayList использует массив объектов для внутреннего хранения данных.

Когда вы инициализируете ArrayList, создается массив размером 10 ( емкость по умолчанию ), и элемент, добавленный в ArrayList, фактически добавляется в этот массив. 10 является размером по умолчанию, и его можно передать в качестве параметра при инициализации ArrayList.

При добавлении нового элемента, если массив заполнен, то создается новый массив на 50% больше первоначального размера, и последний массив копируется в этот новый массив, так что теперь для нового элемента есть пустые места для быть добавленным.

Поскольку используемая базовая структура данных является массивом, довольно просто добавить новый элемент в ArrayList, так как он добавляется в конец списка. Когда элемент должен быть добавлен где-либо еще, скажем, в начале, тогда все элементы должны переместиться на одну позицию вправо, чтобы создать пустое место в начале для нового элемента, который будет добавлен. Этот процесс занимает много времени (линейное время) . Но преимущество ArrayList заключается в том, что извлечение элемента в любой позиции очень быстро (с постоянным временем) , поскольку в основе его лежит просто использование массива объектов.

ArrayList имеет базовую структуру данных:

private transient Object[] elementData;

Когда мы фактически создаем ArrayList, выполняется следующий фрагмент кода:

 this.elementData = new Object[initial capacity];

ArrayList может быть созданным двумя способами, упомянутыми ниже:

1. List list = new ArrayList();

Конструктор по умолчанию вызывается и внутренне создает массив Object с размером по умолчанию 10. [+1121]

2. List list = new ArrayList(5);

Когда мы создаем ArrayList таким способом, вызывается конструктор с целочисленным аргументом и создаем массив Object с размером по умолчанию 5.

Внутри метода add проверяется, больше или равен ли текущий размер заполненных элементов максимальный размер ArrayList, затем он создаст новый ArrayList с размером new arraylist = (current arraylist*3/2)+1 и скопирует данные из старого в новый список массивов.

Он использует массив и пару целых чисел для указания первого значения - индекса последнего значения

private transient int firstIndex;

private transient int lastIndex;

private transient E[] array;

Вот пример реализации.

ArrayLists используют массивы для хранения данных. Когда количество элементов превышает выделенный массив, он копирует данные в другой массив, возможно, в два раза больше.

При копировании массива (незначительное) снижение производительности происходит, поэтому можно установить размер внутреннего массива в конструкторе списка массивов.

Кроме того, он реализует java.util.Collection и и java.util.list, и поэтому возможно получить элемент по указанному индексу, и итеративный (как массив).

Как правило, структуры, подобные ArrayLists, реализуются старым добрым массивом, определенным внутри класса и не доступным напрямую за пределами класса.

Определенный объем пространства первоначально выделяется для списка, и когда вы добавляете элемент, размер которого превышает размер массива, массив будет повторно инициализирован с новой емкостью (которая обычно несколько кратна текущей размер, поэтому каркас не постоянно перераспределяет массивы с каждой новой добавленной записью).

Он использует объект []. Когда массив заполнен, он создает новый массив, размер которого на 50% больше, и копирует текущие элементы в новый массив. Это происходит автоматически.

Исходный код платформы 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;
  .
  .
  .
}