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

В данной статье будет детально рассмотрен класс ArrayList из каркаса коллекций Collections Framework, который пожалуй является наиболее простым для понимания, ввиду того что он основан на базе обычного массива. Практически наверняка на собеседовании Вам зададут вопрос про этот класс и его реализацию в Java. Во второй части мы разберем оставшиеся методы и напишем свою реализацию динамического массива для чисел. Класс ArrayList наследуется от класса AbstractList и реализует следующие интерфейсы: List, RandomAccess, Cloneable, Serializable. Подробный разбор класса ArrayList [Часть 2] В классе ArrayList поддерживаются динамические массивы, которые могут наращиваться по мере надобности. Его необходимость и эффективность объясняется тем, что обычный массив имеет фиксированную длину: после того как он создан, он не может увеличиваться или уменьшаться, что накладывает ограничения в том случае, если неизвестно, насколько большой массив потребуется. По существу, класс ArrayList представляет собой списочный массив объектных ссылок переменной длины. Важно понимать, что автоматического уменьшения размера (количество ячеек) внутреннего массива при удалении элементов из него не происходит. На самом деле уменьшается значение переменной size, которая указывает на количество действительно имеющихся в массиве элементов. Допустим, мы создаём новый объект класса ArrayList и добавляем туда 5 элементов. По умолчанию создаётся массив на 10 элементов. В данном случае, так называемый capacity (размер/объем) нашего объекта будет равен 10, но вот значение переменной size будет равняться пяти. И при удалении элементов мы видим изменения значения переменной size, так как получить доступ к внутреннему массиву класса ArrayList и узнать его длину .length мы не можем. Размер можно уменьшить с помощью дополнительного метода trimToSize(), речь о котором пойдет далее. Рассмотрим поля класса.

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

  
  private static final int DEFAULT_CAPACITY = 10
  

  При создании нового объекта new ArrayList<>() (конструктор без параметров) внутри создается массив на 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 (с приведением к типу, разумеется). Добавление элементов Классическое добавление элементов в списочный массив осуществляется с помощью перегруженных вариантов метода 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, но так как мы добавляем 11 элемент, то 15+1 = 16. Вернемся к нашему списку и предположим, что мы уже добавили в него 10 элементов и пробуем добавить 11. Проверка покажет, что места в массиве нет. Соответственно создается новый массив и вызывается Arrays.copyOf, который внутри себя использует системный метод System.arraycopy(). Или вот такой наглядный пример из одной статьи на 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)

Удаляет элементы из коллекции по заданному предикату. Cобственно предикат — эта некая функция/алгоритм/условие, на основании которой будут удалены один или несколько элементов, соответствующих заданному условию. 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. Индекс также должен быть больше нуля и меньше индекса последнего элемента, иначе будет выброшено исключение 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);

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

public Object[] toArray()

или

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

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

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

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

public Object clone() 

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

public boolean contains(Object o)

Осуществляет проверку наличия объекта в списке (внутри с помощью метода equals класса Object, т.е. сравнивает ссылки), возвращает true/false в зависимости от результата. Перебрать (обратиться к каждому элементу, а также выполнить какое-то действие) коллекцию помимо привычных циклов можно с помощью:

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

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

public E get(int index)

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

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

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

public boolean isEmpty();

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

public int size();

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

public Iterator< E> iterator();

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

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

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

public Spliterator <E> spliterator()

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