Как работает ArrayList? - PullRequest
       6

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

30 голосов
/ 12 августа 2010

Какую структуру данных использует ArrayList для внутреннего использования?

Ответы [ 9 ]

60 голосов
/ 12 августа 2010

Внутренне ArrayList использует Object[].

Когда вы добавляете элементы в ArrayList, список проверяет, осталось ли место в резервном массиве. Если есть место, новый элемент просто добавляется в следующем пустом месте. Если места нет, создается новый, более крупный массив, и старый массив копируется в новый.

Теперь осталось больше места, и новый элемент добавляется в следующее пустое место.

Поскольку людям действительно нравится исходный код:

/**
 * 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;

Прямо из JDK.

19 голосов
/ 12 августа 2010

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

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

9 голосов
/ 15 ноября 2012

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

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

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

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

1 голос
/ 25 августа 2015

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

private transient Object[] elementData;

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

 this.elementData = new Object[initial capacity];

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

  1. List list = new ArrayList();

Вызывается конструктор по умолчанию, который внутренне создает массив Object с размером по умолчанию 10.

List list = new ArrayList(5);

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

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

0 голосов
/ 03 марта 2017

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

0 голосов
/ 12 августа 2010

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

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

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

0 голосов
/ 12 августа 2010

Исходный код платформы 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;
  .
  .
  .
}
0 голосов
/ 12 августа 2010

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

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

0 голосов
/ 12 августа 2010

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

private transient int firstIndex;

private transient int lastIndex;

private transient E[] array;

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...