Подробный разбор класса ArrayList [Часть 1]

В данной статье будет детально рассмотрен класс ArrayList из каркаса коллекций Collections Framework, который пожалуй является наиболее простым для понимания, ввиду того что он основан на базе обычного массива. Практически наверняка на собеседовании Вам зададут вопрос про этот класс и его реализацию в Java. Во второй части мы разберем оставшиеся методы и напишем свою реализацию динамического массива для чисел. Если коротко: ArrayList это список на основе обычного массива, который умеет расти сам. Внутри он хранит два поля: массив elementData с элементами и счетчик size с их реальным количеством. Пока в массиве есть свободные ячейки, добавление сводится к записи в следующую ячейку. Когда места нет, создается новый массив в полтора раза больше, туда копируется все содержимое, а старый уходит сборщику мусора. Отсюда и все свойства класса: мгновенный доступ по индексу и медленные вставки с удалениями в середине.

Кратко

• ArrayList это динамический массив: обычный массив внутри плюс счетчик заполненности size.
• size и capacity это разные вещи: первое это сколько элементов реально лежит в списке, второе это длина внутреннего массива. Второе само по себе не уменьшается никогда.
• Когда массив заполнен, grow() создает новый в полтора раза длиннее и копирует туда все элементы через System.arraycopy().
• Вставка и удаление по индексу это сдвиг всего хвоста списка тем же System.arraycopy(), поэтому они тем дороже, чем ближе к началу списка вы работаете.
• Доступ по индексу через get() и set() идет напрямую в ячейку массива и не зависит от размера списка.
• Емкостью можно управлять вручную: ensureCapacity() резервирует место заранее, trimToSize() обрезает массив до текущего size.

Класс ArrayList наследуется от класса AbstractList и реализует следующие интерфейсы: List, RandomAccess, Cloneable, Serializable. Подробный разбор класса ArrayList [Часть 2]

Зачем нужен ArrayList

В классе ArrayList поддерживаются динамические массивы, которые могут наращиваться по мере надобности. Его необходимость и эффективность объясняется тем, что обычный массив имеет фиксированную длину: после того как он создан, он не может увеличиваться или уменьшаться, что накладывает ограничения в том случае, если неизвестно, насколько большой массив потребуется. По существу, класс ArrayList представляет собой списочный массив объектных ссылок переменной длины.

size и capacity: в чем разница

Важно понимать, что автоматического уменьшения размера (количество ячеек) внутреннего массива при удалении элементов из него не происходит. На самом деле уменьшается значение переменной size, которая указывает на количество действительно имеющихся в массиве элементов. Допустим, мы создаем новый объект класса ArrayList и добавляем туда 5 элементов. При первом же добавлении внутри появляется массив на 10 элементов. В данном случае, так называемый capacity (размер/объем) нашего объекта будет равен 10, но вот значение переменной size будет равняться пяти. И при удалении элементов мы видим изменения значения переменной size, так как получить доступ к внутреннему массиву класса ArrayList и узнать его длину .length мы не можем. Размер можно уменьшить с помощью дополнительного метода trimToSize(), речь о котором пойдет далее.

Поля класса

Рассмотрим поля класса.

• Поле, отвечающее за объем динамического массива по умолчанию:

  private static final int DEFAULT_CAPACITY = 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 присваивается ссылка на новый массив типа Object размером initialCapacity). Если параметр равен 0, то в таком случае создается пустой массив. Если же заданный параметр меньше 0, то генерируется исключение IllegalArgumentException.

Создание объекта

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

Только что созданный объект list, содержит свойства (поля) elementData и size. Хранилище значений elementData есть не что иное, как массив определенного типа (указанного в generic, то есть в <>), в нашем случае String[]. Если вызывается конструктор без параметров, то массив для 10 элементов типа Object (с приведением к типу, разумеется) появится при первом добавлении элемента. Небольшая оговорка про версии, важная для собеседования. До Java 7 конструктор без параметров действительно сразу заводил массив на десять ячеек, в исходниках это было написано как public ArrayList() { this(10); }. Начиная с Java 8 он кладет в elementData пустой массив нулевой длины, а десять ячеек выделяются уже внутри первого вызова add(), прямо перед тем как в них ляжет первый элемент. Схема ниже показывает именно этот момент.

Добавление элементов

Классическое добавление элементов в списочный массив осуществляется с помощью перегруженных вариантов метода 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: одиннадцатый элемент в нее спокойно помещается, и до следующего расширения остается еще четыре свободные ячейки. Вернемся к нашему списку и предположим, что мы уже добавили в него 10 элементов и пробуем добавить 11. Проверка покажет, что места в массиве нет. Соответственно создается новый массив и вызывается Arrays.copyOf, который внутри себя использует системный метод System.arraycopy(). Тут нужны две оговорки про версии. Первая: метода newCapacity() в свежих JDK уже нет, его убрали в Java 15, и теперь grow() сразу вызывает ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1). Считает он ровно то же самое, так что формула выше остается в силе. Вторая: на схемах ниже новый массив состоит из шестнадцати ячеек, и это не ошибка художника, а результат формулы, которая работала до Java 7: (oldCapacity * 3) / 2 + 1 для десятки давала как раз 16. Потом единицу из формулы убрали, поэтому на любой современной версии в этом месте получится массив на 15 ячеек. Сама механика при этом не изменилась ни на шаг. Или вот такой наглядный пример из одной статьи на JavaRush: После всех этих проверок и увеличения размера массива при необходимости далее в закрытом методе add() в конец массив добавляется новый элемент, а текущий параметр size увеличивается на единицу. Старый массив в дальнейшем будет обработан сборщиком мусора. Таким образом и работает динамический массив: при добавлении элементов мы проверяем, есть ли в нем еще место. Если место есть, то мы просто добавляем элемент в конец массива. Под концом подразумевается не последняя ячейка в массиве, а та ячейка, которая соответствует значению size. Добавили первый элемент в массив, он помещается в ячейку с индексом [0]. Значение поля size выросло на единицу и = 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); Все элементы, находящиеся справа от указанного индекса, будут сдвигаться на одну позицию вправо (index+1). И только после этого во внутренний массив под указанным индексом добавляется новый элемент. Так как мы сдвинули часть массива вправо на единицу (новый массив не создается), то нужная нам ячейка освободится для записи. Ссылка на старый массив стирается и в дальнейшем ей займется garbage collector. Вставляем "maserati" в ячейку [3], которая уже занята: Таким образом, когда происходит вставка элемента по индексу и при этом в массиве нет свободных мест, то вызов System.arraycopy() случится дважды: первый в grow(), второй в самом методе add(index, value), что явно скажется на скорости всей операции добавления. В итоге, когда необходимо записать во внутренний массив еще один элемент, а места там нет, то внутри ArrayList происходит вот что:

• Создается новый массив размером в 1.5 раза больше исходного.
• Все элементы из старого массива копируются в новый массив
• Новый массив сохраняется во внутренней переменной объекта ArrayList, а старый массив объявляется мусором.

Емкость объектов типа ArrayList можно увеличивать вручную с помощью метода:

public void ensureCapacity(int minCapacity)

Увеличив емкость массива заранее, можно избежать дополнительного перераспределения оперативной памяти впоследствии. Метод увеличивает размер внутреннего массива, чтобы в него поместилось количество элементов, переданных в minCapacity. Метод ensureCapacity() не влияет на поле size, он влияет на capacity (размер) внутреннего массива. В очередной раз подчеркиваю, что size и capacity разные вещи и очень важно их не путать! Если требуется уменьшить размер базового массива, на основе которого строится объект типа ArrayList, до текущего количества действительно хранимых элементов, следует вызвать метод trimToSize(). После удаления элементов из коллекции size() покажет количество действительно существующих элементов, а capacity при этом не уменьшится! Предположим: мы ввели 100 элементов, удалили первые 50, size станет равным 50, а вот capacity так и останется 100. Чтобы уменьшить и capacity, необходимо использовать метод trimToSize(), который подгоняет весь наш capacity до текущего size. Как подгоняет? Копирует наш массив так, что там не остается пустых ячеек (длина нового массива просто равна полю size). Также добавлять элементы в нашу коллекцию можно с помощью методов 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, необходимо будет познакомиться с так называемыми обобщенными типами (generics). Обозначение 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); В наш же исходный массив (es) копируется та часть, которая находится правее позиции под указанным индексом (i+1), и располагается она, начиная с той самой позиции (i), где находился элемент, подлежащий удалению. Таким образом, мы осуществили сдвиг влево и затерли наш элемент. Попробуем удалить элемент под индексом 3 из массива ниже: Рассмотрим второй вариант метода:

public boolean remove(Object o)

Метод удаляет из списка переданный элемент o, а если точнее, то объект по указанной ссылке. Если элемент присутствует в списке, он удаляется, а все элементы смещаются влево. Если элемент существует в списке и успешно удален, метод возвращает true, в обратном случае false. Аналогично варианту с удалением по индексу, вызывается метода fastRemove(), где происходят точно такие же действия. Разница в том, что в методе remove(Object o) предварительно дополнительно осуществляется поиск нужного объекта через метод equals() класса Object. При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент. Подытожим: при удалении элементов из динамического массива, дырок как в обычном массиве не остается (удаленная ячейка не будет пустовать). Все последующие элементы (которые были правее от индекса) сдвигаются на одну позицию влево. Есть еще несколько дополнительных методов, с помощью которых можно в той или иной степени удалять элементы из списка. Рассмотрим их вкратце. Очищаем нашу коллекцию:

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"

Так как удалился "Green", которого нет в listFirst. Но после listSecond.removeAll(listFirst) в listSecond останется:

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

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

protected void removeRange(int fromIndex, int toIndex)

Удаляет из списка все элементы, которые находятся между начальным указанным индексом (включительно) и конечным указанным индексом (не включительно). Стоит отметить, что метод нельзя вызвать напрямую на объекте класса ArrayList. Чтобы его использовать необходимо унаследоваться от AbstractList/ArrayList. Метод также используется другим методом (subList, о котором пойдет речь далее).

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

Удаляет элементы из коллекции по заданному предикату. Собственно предикат это некая функция/алгоритм/условие, на основании которой будут удалены один или несколько элементов, соответствующих заданному условию. Predicate это функциональный интерфейс (содержит всего один метод, поэтому может использоваться в виде лямбды), работает по принципу "принял один параметр, вернул boolean". По сути метод переопределяет реализацию из интерфейса 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;
  }
}

В другом классе создадим ArrayList из String и объект нашего класса, который реализует 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");

Выполним на списке метод removeIf, которому передадим наш объект с условием:

color_list.removeIf(filter);

В результате из списка будут удалены все строки со значением "White", так как наш "предикат" сравнивает их на равенство. Итоговый список: [Black, Red, Yellow].

Замена элементов

public E set(int index, E element)

Осуществляет замену элемента в указанной позиции index на переданный element. Индекс должен быть не меньше нуля и строго меньше size, то есть от нуля до индекса последнего элемента включительно, иначе будет выброшено исключение IndexOutOfBoundsException. Никаких копирований внутреннего массива не происходит. Просто вместо элемента по указанному индексу вставляется новый элемент, т.е. перезаписываем значение.

public void replaceAll(UnaryOperator<E> operator)

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

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

В другом классе создадим ArrayList из String и объект нашего класса, который реализует 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);

В результате все значения в списке были заменены на "White": [White, White, White, White, White, White]. А вот так например можно убрать все пробелы из строк, которые есть в коллекции:

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

Прочие методы

toArray(): список в обычный массив

Преобразовать списочный массив ArrayList в обычный массив можно с помощью метода:

public Object[] toArray()

или

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

Здесь тип возвращаемого массива определяется в runtime. Этот метод позволит:

1. ускорить выполнение некоторых операций;
2. передавать массив в качестве параметра методу, который не перегружается, чтобы принимать непосредственно коллекцию;
3. интеграция нового кода, основанного на коллекциях, с унаследованным кодом, который не распознает коллекции.

clone(): копия списка

Вернуть объект-копию массива:

public Object clone()

Следует обратить внимание, что метод clone() возвращает тип Object, так что после его вызова потребуется сделать приведение к необходимому классу. Копия получается поверхностной: новым будет сам список и его внутренний массив, а вот элементы не копируются, оба списка ссылаются на одни и те же объекты.

contains(): есть ли объект в списке

Проверить коллекцию на наличие в ней объекта:

public boolean contains(Object o)

Осуществляет проверку наличия объекта в списке. Внутри в цикле вызывается o.equals(elementData[i]), то есть работает та реализация equals(), которая есть у самого объекта. Для String и других классов с переопределенным equals() сравнение идет по значению, и только если класс метод не переопределял, сработает вариант из Object и сравнятся ссылки. Возвращает true или false в зависимости от результата.

forEach(): перебрать все элементы

Перебрать (обратиться к каждому элементу, а также выполнить какое-то действие) коллекцию помимо привычных циклов можно с помощью:

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

Без использования лямбд необходимо использовать анонимный класс и переопределять метод accept интерфейса Consumer:

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

get(): элемент по индексу

Получить элемент по его индексу:

public E get(int index)

Используется для произвольного доступа к элементам коллекции. Возвращает элемент, находящийся в списке под указанным индексом. Если index < 0 или index >= максимального количества элементов списка, будет выброшено исключение IndexOutOfBoundsException. Это основной метод получения элемента из списка, и время извлечения элемента по индексу всегда будет одинаковым, независимо от размера ArrayList, так как происходит обращение к конкретной ячейке массива.

indexOf() и lastIndexOf(): поиск индекса

Поиск индексов для указанных объектов:

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

Методы возвращают индекс первого (когда первый раз встречается заданный объект) или последнего вхождения (когда последний раз встречается заданный объект) элемента в списке. Если элемента не существует в списке, методы вернут -1.

isEmpty(): пуст ли список

Проверить коллекцию на наличие в ней элементов:

public boolean isEmpty();

Метод возвращает true, если список пустой (смотрит, равно ли поле size нулю), иначе false. Если в списке содержатся только элементы null, метод вернет false. Иными словами, null элементы также учитываются этим методом.

size(): сколько элементов в списке

Узнать количество элементов в списке:

public int size();

Возвращает количество элементов в списке (значения поля size). Количество элементов может отличаться от объема списка (capacity).

iterator(): обход списка

Получить итератор для списка:

public Iterator< E> iterator();

Возвращает итератор для списка для последующего использования в цикле или при любой другой обработке. Итератор реализует fail-fast поведение. Если он бежит по коллекции и замечает какие-то модификации в ней (которые были получены не с помощью методов итератора), он сразу выбрасывает исключение ConcurrentModificationException. У итератора есть так называемый modification count. Когда итератор пробегает по коллекции после каждого next/hasNext/remove, он проверяет этот счетчик. Если он не совпал с тем, что ожидал увидеть итератор, он бросает исключение. Подробно рассматривать итераторы здесь я не буду.

listIterator(): обход в обе стороны

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

Возвращает list-итератор для списка для последующего использования в цикле или при любой другой обработке. Интерфейс ListIterator расширяет интерфейс Iterator для двустороннего обхода списка и видоизменения его элементов. В перегруженном варианте можно передать индекс, с которого начнется «обход». Индекс в данном случае обозначает первый элемент, с которого начнет свою работу метод next(), а при вызове метода previous() обход начнется с элемента под индексом «переданный индекс минус 1».

spliterator(): обход для параллельной обработки

public Spliterator <E> spliterator()

В Java 8 внедрен новый тип итератора late binding (позднее связывание) и fail-fast, который называется итератором-разделителем. Итераторы-разделители позволяют перебирать последовательность элементов, но применяются они иным способом. Наиболее важной особенностью интерфейса Spliterator является его способность поддерживать параллельную итерацию отдельных частей последовательности элементов, а следовательно и параллельное программирование.

Сложность операций

Все, что разобрано выше, складывается в короткую таблицу. Она же обычно и нужна на собеседовании. Оценки взяты не с потолка: они прописаны в документации самого класса, где сказано, что операции size, isEmpty, get, set, iterator и listIterator выполняются за постоянное время, add за амортизированное постоянное, а все остальные линейно.

Вопросы и ответы

Чем ArrayList отличается от обычного массива?

Длиной, которую не надо знать заранее. У массива размер задается один раз при создании и больше не меняется, а ArrayList сам заводит массив побольше, когда старый заполнился. Платой за это идет лишняя память под запас пустых ячеек и копирование всего содержимого в момент расширения. Плюс ArrayList хранит только объекты, так что примитивы в нем лежат в обертках: Integer вместо int.

В чем разница между size и capacity в ArrayList?

size это количество элементов, которые вы реально положили в список, его возвращает метод size(). capacity это длина внутреннего массива, то есть сколько элементов туда влезет без расширения. Узнать ее снаружи штатными средствами нельзя. При удалении элементов уменьшается только size: если положить 100 элементов и удалить 50, size станет 50, а capacity останется 100, пока не вызвать trimToSize().

Как ArrayList увеличивается при добавлении элементов?

В методе add() сначала проверяется, равен ли size длине внутреннего массива. Если да, вызывается grow(): он считает новую емкость по формуле oldCapacity + (oldCapacity >> 1), то есть в полтора раза больше прежней, создает массив такой длины через Arrays.copyOf() и переносит туда все элементы. Старый массив становится мусором. Само добавление после этого это одна запись в ячейку и увеличение size на единицу.

Чем remove(int index) отличается от remove(Object o)?

Первый удаляет элемент по позиции и возвращает удаленное значение, второй ищет элемент по equals() и возвращает boolean. Ловушка ждет у списка чисел: у List<Integer> вызов list.remove(1) уберет элемент с индексом 1, а не число 1, потому что компилятор выберет перегрузку с int. Чтобы удалить именно значение, надо писать list.remove(Integer.valueOf(1)).

Почему вставка и удаление в начале ArrayList работают медленно?

Потому что элементы лежат в массиве подряд и дырок в нем не бывает. Чтобы вставить элемент в начало, надо сдвинуть вправо весь остальной список, чтобы удалить, надо сдвинуть все влево. Делает это System.arraycopy(), и чем ближе к началу вы работаете, тем больше элементов он перекладывает. В конце списка сдвигать нечего, поэтому добавление в конец остается дешевым.

Что такое fail-fast итератор и когда бросается ConcurrentModificationException?

Итератор ArrayList запоминает счетчик изменений списка modCount и сверяет его при каждом шаге. Если список изменили в обход итератора, например вызвали list.remove() прямо внутри цикла for-each, счетчики разойдутся и полетит ConcurrentModificationException. Это и называется поведением fail-fast: упасть сразу, а не отдавать испорченные данные. Удалять во время обхода нужно методом самого итератора iterator.remove().

Читайте также

• Подробный разбор класса ArrayList [Часть 2]
• LinkedList в Java
• Java Generics
• Сказ о двух итераторах: стратегии конкурентной модификации в Java