Урок 24. ArrayList Java

На этом уроке из серии бесплатных уроков по Java мы рассмотрим класс Java ArrayList. Сначала узнаем значение размера и емкости ArrayList и разницу между ними. После этого поясним некоторые методы ArrayList. А в конце будет приведено несколько практических примеров программирования, которые, например, покажут вам, как добавлять и удалять элементы из ArrayList.



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

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

Размер и емкость



Есть два разных термина, которые важно понимать в контексте списка массивов – размер и емкость. Размер - это количество элементов, которые в настоящее время содержит список ArrayList. Для каждого элемента, добавленного в список или удаленного из него, размер увеличивается и уменьшается соответственно на единицу. Емкость, с другой стороны, - это количество элементов, которые может содержать базовый массив.

ArrayList начинается с начальной емкости, которая увеличивается с интервалами. Каждый раз, когда вы превышаете емкость массива, ArrayList копирует данные в новый массив, который примерно на 50% больше предыдущего. Допустим, вы хотите добавить 100 элементов в ArrayList с начальной емкостью 10. После добавления всех элементов он создаст еще шесть массивов, которые займут место первого. Более конкретно, первый массив заменяется новым массивом, который может содержать 15 элементов, затем второй, который может содержать 22 элемента, затем массивы емкостью 33, 49, 73 и, наконец, 109 элементов – все это для хранения растущего списка, как показано на рисунке выше. По своей сути, эти механизмы реструктуризации могут негативно повлиять на производительность.

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

public class ArrayList<E> {
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;
    private int size;
 
    public E get(int index) {...}
    public boolean add(E e) {...}
[...]
}

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

DEFAULT_CAPACITY - это начальный размер массива, если вы не указали его, как рекомендовалось ранее. elementData - это массив, используемый для хранения элементов списка массивов. размер - это количество элементов, которые в настоящее время содержит список ArrayList. получить, добавить и удалить-вот некоторые из многих функций, предоставляемых ArrayList, и мы рассмотрим их более подробно.

Методы ArrayList

Для удобства мы разбиваем обзор на методы, принадлежащие java.util.Collection и java.util.List interfaces.



java.util.Collection

Контракт интерфейса сбора не гарантирует какой-либо конкретный заказ, подразумевая, что он не предоставляет никаких методов, связанных с индексом или заказом. Первый набор методов, а именно: boolean add (E e) boolean add All (Collection< ? extends E> c) boolean remove (Object o) boolean removeAll(Collection< ?>c) все реализуют интерфейс коллекции.

Обратите внимание, что многое из того, что здесь сказано об этих методах, относится не только к ArrayList, но и ко всем классам, реализующим интерфейс коллекции. Метод add добавляет элемент в конец коллекции. Для ArrayList конец - это следующая пустая ячейка базового массива. addAll добавляет все заданные элементы в конец коллекции. Материал в угловых скобках относится к дженерикам.

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

Теперь мы рассмотрим второй набор методов, а именно: Iterator iterator(E e) int size() boolean contains(Object o).

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

Наконец, мы рассмотрим наш третий набор методов, а именно: void clear() boolean isEmpty() T[ ] toArray(T[ ] a). clear удаляет все элементы из коллекции. isEmpty возвращает значение true, если коллекция не содержит элементов. toArray возвращает необработанный массив, содержащий все элементы коллекции.

Переопределения Java.Util.List

ArrayList также реализует интерфейс списка. boolean addAll(int index, E element) E remove(int index) E get(int index) int indexOf(E o) int lastIndexOf(Object o) List subList(int fromIndex, int toIndex) int lastIndexOf(Object o. Методы частично похожи на методы сбора, которые мы только что рассмотрели, но отличаются тем, что они требуют упорядочения элементов списка.

Опять же, мы отмечаем, что все, что мы говорим об этих методах, обычно относится не только к ArrayList, но и к большинству классов, реализующих List. Метод add с параметром index фактически действует как метод вставки. Это позволяет вставлять элемент в любую позицию индекса в списке, вместо того, чтобы просто добавлять элемент в конец списка. В процессе элементы резервного массива для ArrayList будут смещены вправо и при необходимости перенесены в массив большего размера. Метод remove позволяет удалить элемент из любой позиции индекса списка. Подобно методу добавления ArrayList, для этого может потребоваться переместить оставшиеся элементы базового массива влево.

Метод get(int index) возвращает элемент из любой заданной позиции списка. Метод indexOf принимает объект и возвращает индекс первого вхождения элемента в списке или -1, если элемент не найден. lastIndexOf возвращает индекс последнего вхождения элемента в списке и, как и раньше, -1, если элемент не найден. subList возвращает подмножество списка, начинающееся с позиции, указанной fromIndex, и заканчивающееся на одну позицию перед позицией toIndex. И последнее, но не менее важное: сортировка сортирует список в соответствии с порядком данного компаратора.

Объявление коллекции при создании экземпляра ArrayList

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

Collection elements = new ArrayList<>(INITIAL_CAPACITY);

Сеанс программирования

Поначалу это может показаться немного нелогичным, поскольку мы ожидаем, что наш экземпляр ArrayList будет назначен переменной ArrayList или, по крайней мере, ссылочной переменной списка. За этим стоит логика, и, цитируя Роберта Мартина, “Хорошая архитектура - это та, которая максимизирует количество не принятых или отложенных решений”. Мы можем сделать вывод, что во многих ситуациях, назначая ссылочную переменную коллекции, мы можем перенаправить ее другим методам и/или другим объектам и в конечном итоге не ограничиваемся, например, передачей списка массивов.

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

Если бы мы использовали List или ArrayList везде в коде, было бы очень трудно изменить наше мнение позже. Нам пришлось бы коснуться большого количества кода, что очень опасно. Конечно, использование коллекции ограничивает количество методов, которые мы можем использовать, поскольку в ней меньше методов, чем в интерфейсе списка, но мы узнаем, что на самом деле лучше иметь доступ только к тем методам, которые нам нужно использовать. Позже мы в конечном итоге переключимся на интерфейс списка, чтобы показать больше методов, которые список выводит в таблицу поверх коллекции.

В качестве отступления обратите внимание на ту же строку кода, в которой используется “<>” или оператор diamond, введенный в Java 7. Поскольку мы объявляем и создаем экземпляры элементов в одном и том же операторе, компилятор делает вывод, что наш список массивов набран в строку. Это делает наш код немного короче и читается лучше.

И последнее, но не менее важное, обратите внимание на начальную емкость, которая является константой, ранее определенной следующим образом: private final int INITIAL_CAPACITY = 5. Мы могли бы легко просто ввести 5 в качестве нашей начальной емкости, но мы бы написали “магическое число”. Это значительно затрудняет для следующего разработчика, читающего наш код (который часто оказывается нами), понимание того, что на самом деле означает 5 в этом контексте. Мы хотим явно указать, что мы установили начальную емкость для нашего списка массивов, поэтому настоятельно рекомендуется использовать именованное значение для документирования наших намерений.

Примеры кода

Методы Collection

Collection elements = new ArrayList<>(INITIAL_CAPACITY);
elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");
elements.add("E");
elements.add("E");
for (String str : elements){
    System.out.print(str + " "); // A B A C E E
}

Мы рассмотрим несколько примеров, чтобы лучше понять, что такое ArrayList. Мы начинаем с добавления метода интерфейса сбора, показанного в коде выше, в строках 3-7. Поскольку элементы представляют собой коллекцию типа String, мы можем добавить строки в наш список массивов.

Хотя наша переменная является коллекцией, обратите внимание, что тот факт, что мы создали экземпляр списка массивов, позволяет нам добавлять повторяющиеся элементы, например, “A” и “E” дважды. Напомним ранее, что константа INITIAL_CAPACITY, равная 5, также устанавливается в качестве начальной емкости для нашего списка массивов. В строке 8 добавление второго “E” приведет к тому, что базовый массив нашего списка создаст новый массив большего размера, перенеся все существующие данные в новый массив вместе со вторым “E”.

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

Вывод ArrayList Java

Вот два разных способа распечатать список массивов. Мы можем использовать его метод toString, который вызывает println, когда мы используем его следующим образом: System.out.println(элементы). Это связано с тем, что мы хотим посмотреть, как мы можем выполнять итерацию по списку массивов в результате реализации коллекции, которая, в свою очередь, реализует итерационный интерфейс.

Поскольку ArrayList в конечном счете реализует итерацию, мы можем написать строку 10, не беспокоясь о деталях, необходимых для итерации по этой коллекции. Все это делается для нас внутренним компилятором. Мы можем использовать список массивов в цикле для каждого и распечатать каждый элемент отдельно, что дает нам большую гибкость. Обратите внимание, что Коллекция распечатана в том же порядке, в каком были добавлены элементы, т. Е. как “A B A C E E ”. Если бы наша коллекция была создана в каком-либо экземпляре Set, нам не был бы гарантирован тот же порядок итераций, что и в случае со списком.

Удаление из ArrayList Java

Мы также можем так же легко удалить элементы из ArrayList. Поскольку у нас есть переменная коллекции, мы не можем удалить ее по индексу. Единственный способ - удалить, указав объект, который внутренне использует метод equals. В нашем примере он просматривает каждый элемент и проверяет соответствие, используя значения строки. Первое найденное совпадение удаляется из коллекции.

Collection elements = new ArrayList<>(INITIAL_CAPACITY);
elements.add("A");
elements.add("B");
elements.add("A");
elements.remove("A");
System.out.println(elements); // [B, A]

Вы также можете заметить, что у нас есть две буквы «A». Интересно отметить, что удаляется только первая буква “А”. Как мы можем быть уверены? Всякий раз, когда вы сталкиваетесь с такими вопросами, хорошей идеей было бы поискать книгу, видеоурок или API. Однако самый быстрый способ убедиться в этом - написать простой тестовый код самостоятельно. Поскольку код не лжет, вы будете уверены, что он ведет себя так, как вы его написали. В нашем примере на рисунке 4 удаляется только первый элемент A, оставляя элементы только с буквами “B” и “A”.

Размер коллекции

Collection elements = new ArrayList<>(INITIAL_CAPACITY);

System.out.println(elements.size()); // 0
elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");
System.out.println(elements.size()); // 4 

Мы также можем узнать текущий размер списка массивов, а также проверить, пуст ли он. В коде выше, строка 3, мы непосредственно распечатываем размер нашей коллекции после ее создания. Как и ожидалось, выводится 0, так как у нас нулевые элементы. Благодаря нашему примеру мы можем исключить возможность того, что строка 3 вызовет исключение. В строке 10, после добавления 4 строк, мы снова распечатываем размер и получаем 4.

Collection elements = new ArrayList<>(INITIAL_CAPACITY);
System.out.println(elements.isEmpty()); // true
elements.add("A");
System.out.println(elements.isEmpty()); // false

Удобно, что мы можем проверить, пуста ли наша коллекция, т. е. ее размер равен 0. Мы получаем значение true на рисунке 6, строка 3 после создания экземпляра в пустом списке массивов и получаем значение false в строке 5 после добавления “A” в список.

Методы интерфейса List

С этого момента мы переключаемся на интерфейс списка в большинстве наших примеров, т. Е. Теперь у нас будет ссылочная переменная типа List, дающая нам доступ ко всем методам интерфейса коллекции и Списку в дополнение к этому.

Вставка элементов List

List elements = new ArrayList<> (INITIAL_CAPACITY);
elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");
elements.add(0, "T");
elements.add(2, "S");
System.out.println(elements); // [T, A, S, B, A, C]

Мы можем вставить элемент, указав, где его разместить, используя индекс. В коде выше, в строках 7-8 показано, как мы можем добавить, скажем, “T” в начало нашего списка с индексом 0 и “S” с индексом 2, который оказывается прямо между “A” и “B” после вставки “T”. Обе вставки сдвигают все остальные элементы вправо от указанного индекса, в то время как удаление элементов по индексу делает обратное, сдвигая все остальные элементы влево. Распечатав его, как показано в строке 10, мы получим результат [T, A, S, B, A, C].

Удаление элементов List

List elements = new ArrayList<>(INITIAL_CAPACITY);
elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");
elements.remove(1);
System.out.println(elements); // [A, A, C] 

Допустим, мы хотим удалить второй элемент из нашего списка. Как показано в коде выше, строка 7, мы делаем это, вызывая remove с индексом 1. Это удаляет “B” из нашего списка, оставляя нас с элементами [A, A, C]. Однако вы обнаружите, что вам редко нужно использовать эти методы на основе индексов, и вместо этого вы можете выбрать использование коллекций.

Размер List Java

int initialCapacity = 100;

// резервный массив начинается с длины 100

List elements = new ArrayList<> (initialCapacity); 

elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");

System.out.println(elements.size());
// размер 4, а не 100!

Наш пример начинается с объявления начальной емкости 100. В примере показана разница между емкостью и размером списка массивов. Напомним, что размер - это текущее количество элементов списка, а емкость - длина резервного массива списка. В нашем примере наш список изначально содержит 100 элементов. После добавления четырех элементов, если вы запустите отладчик и прервете выполнение, войдя в класс ArrayList перед запуском строки 11, вы увидите, что длина внутреннего массива elementData по-прежнему равна 100, в то время как наш размер увеличивается до 4.

Получение индексов элементов из List Java

Иногда вам захочется запросить индекс определенного элемента в списке. Интерфейс списка предоставляет нам два метода для этого – indexOf и lastIndexOf. Поскольку списки допускают дублирование элементов, для получения первого индекса элемента мы будем использовать indexOf. Если мы вызовем indexOf с “A”, мы получим первый индекс 0. Чтобы получить последний индекс “A”, мы вызовем lastIndexOf, который возвращает 2. Вы можете увидеть все это в действии на в коде ниже.

// резервный массив начинается с длины 100

int initialCapacity = 100;
List elements = new ArrayList<>(initialCapacity);

elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");

System.out.println(elements.indexOf("A")); // index: 0
System.out.println(elements.lastIndexOf("A")); // index:2

Очистка коллекции

Collection elements = new ArrayList<> (INITIAL_CAPACITY);
elements.add("A");
elements.add("B");
elements.add("A");
elements.add("C");
System.out.println(elements.isEmpty()); // false
 
elements.clear();
System.out.println(elements.isEmpty()); // true
System.out.println(elements); // []

Чтобы удалить все элементы из коллекции, мы используем метод clear. Он очистит список, так что, если мы вызовем isEmpty в списке с элементами, будет возвращено значение true. Интересно, что в строке 11 мы узнаем, что распечатка пустого списка не создает исключения. Вместо этого он выводит только пару квадратных скобок “[]”.