Java ArrayList представляет собой массив объектов с изменяемым размером, который позволяет нам добавлять, удалять, находить, сортировать и заменять элементы. ArrayList является частью фреймворка Collection и реализуется в интерфейсе List.
1. Введение в Java ArrayList
1.1 Что такое ArrayList?
ArrayList обладает следующими особенностями:
- Упорядоченный — элементы в ArrayList сохраняют свой порядок, который по умолчанию соответствует порядку, в котором они были добавлены в список.
- На основе индекса – Элементы могут быть доступны случайным образом с использованием позиций индекса. Индекс начинается с «0».
- Динамическое изменение размера — ArrayList динамически увеличивается, когда требуется добавить больше элементов, чем его текущий размер.
- Несинхронизированный – ArrayList не синхронизирован по умолчанию. Программисту необходимо использовать ключевое слово synchronized соответствующим образом или просто использовать класс Vector.
- Позволяет дублировать элементы – Мы можем добавлять дублирующие элементы в ArrayList. Это невозможно в наборах.
Класс java.util.ArrayList расширяет AbstractList, который реализует интерфейс List. List расширяет интерфейсы Collection и Iterable в иерархическом порядке.
1.2 Внутренняя реализация
Внутренне класс ArrayList реализован с использованием массива(также называемого резервным массивом). Элементы, которые добавляются или удаляются из ArrayList, фактически изменяются в резервном массиве. Все методы ArrayList получают доступ к этому резервному массиву и получают/устанавливают элементы в нем.
public class ArrayList<E> ... {transient Object[] elementData; //backing arrayprivate int size; //array or list size//...}Когда мы создаем пустой ArrayList, массив инициализируется с емкостью по умолчанию 10. Мы продолжаем добавлять элементы в arraylist, и они сохраняются в резервном массиве.
Когда массив заполняется и мы добавляем новый элемент, происходит операция изменения размера. При изменении размера размер массива увеличивается, так что он никогда не должен превышать предел JVM. Элементы копируются из предыдущего массива в этот новый массив. Затем предыдущий резервный массив освобождается для сборки мусора.
1.3 Когда использовать ArrayList?
Как упоминалось ранее, ArrayList — это реализация массива с изменяемым размером. При работе с массивами одной из основных проблем является постоянная проверка допустимых индексов, в противном случае программа выдает исключение IndexOutOfBoundsException. ArrayList никогда не выдает исключение IndexOutOfBoundsException, и мы можем свободно добавлять/удалять элементы, а ArrayList автоматически обрабатывает изменение размера при добавлении или удалении элементов.
ArrayList является частью Java Collections Framework, поэтому arraylist можно использовать с другими типами коллекций и Stream API бесшовным образом, обеспечивая большую гибкость в обработке данных.
При использовании с дженериками ArrayList обеспечивает безопасность типов во время компиляции и гарантирует, что он будет содержать элементы только определенного типа, тем самым снижая вероятность возникновения ClassCastException во время выполнения.
2. Создание ArrayList
Мы можем создать arraylist разными способами в разных сценариях. Давайте рассмотрим их:
2.1 Использование конструкторов
Самый простой способ создать ArrayList — использовать его конструкторы. Его конструктор без аргументов по умолчанию создает пустой ArrayList с начальной емкостью по умолчанию 10.
ArrayList<String> arrayList = new ArrayList<>();
При желании мы можем указать initialCapacity в конструкторе, чтобы избежать частых операций по изменению размера, если мы уже знаем, сколько элементов мы собираемся в нем хранить.
ArrayList<String> arrayList = new ArrayList<>(128);
Также можно инициализировать arraylist элементами из другого списка или коллекции, передав коллекцию конструктору.
Set<String> set = ...;//Initializes the list with items from the SetArrayList<String> arrayList = new ArrayList<>(set);
2.2 Использование фабричных методов
Начиная с Java 9, мы можем использовать методы-фабрики для инициализации ArrayList с элементами. Например, List.of() — это метод, который создает неизменяемый List с указанными элементами. Он часто используется для создания и инициализации List в одной строке. Мы можем использовать его с конструктором ArrayList для создания ArrayList и заполнения его элементами в одной строке.
ArrayList<String> arrayList = new ArrayList<>(List.of("a", "b", "c"));Таким же образом мы можем использовать и фабричный метод Arrays.asList() :
ArrayList<String> arrayList = new ArrayList<>(Arrays.asList("a", "b", "c"));2.3 Создание ArrayList пользовательских объектов
Хотя хранение пользовательских объектов в ArrayList кажется довольно простым, мы все равно должны убедиться, что пользовательский объект правильно реализует метод equals() и удовлетворяет требованиям.
Рассмотрим следующий класс Item с двумя полями id и name. Он не определяет метод equals.
class Item {long id;String name;public Item(long id, String name) {this.id = id;this.name = name;}}Когда мы добавляем несколько элементов в список, а затем пытаемся проверить элемент, мы не получаем желаемого результата. Элемент не найден.
ArrayList<Item> listOfItems = new ArrayList<>(List.of(new Item(1, "Item1"), new Item(2, "Item2")));System.out.println( listOfItems.contains(new Item(1, "Item1")) ); //prints 'false'
В нашем примере предполагается, что если два элемента имеют одинаковый идентификатор, то они должны быть равны. Давайте напишем пользовательский метод equals():
class Item {//...@Overridepublic boolean equals(Object o) {if(this == o) {return true;}if(o == null || getClass() != o.getClass()) {return false;}Item item =(Item) o;return id == item.id;}}Теперь, когда мы снова запустим пример кода, мы получим правильный результат, и элемент будет найден в списке.
System.out.println( listOfItems.contains(new Item(1, "Item1")) ); //prints 'true'
3. Общие операции
Теперь, когда у нас есть базовое понимание класса ArrayList, давайте рассмотрим его методы, используемые в обычных операциях CRUD:
3.1 Добавление элементов в ArrayList
Мы можем добавлять элементы в существующий ArrayList двумя способами:
- add(e): добавляет указанный элемент в конец списка и возвращает true, в противном случае false.
- addAll(): добавляет все элементы указанной коллекции в конец списка в том порядке, в котором они возвращаются итератором указанной коллекции.
ArrayList<String> arrayList = new ArrayList<>();arrayList.add("a"); // [a]arrayList.addAll(List.of("b", "c", "d")); // [a, b, c, d]Чтобы добавить элемент в указанную позицию, мы можем использовать метод add(index, element).
- Вставляет указанный элемент в указанную позицию списка.
- Он также сдвигает элемент, находящийся в текущей позиции(если таковой имеется), и все последующие элементы вправо(добавляет единицу к их индексам).
ArrayList<String> arrayList = new ArrayList<>(List.of("a", "b", "c", "d"));arrayList.add(2, "temp"); //[a, b, temp, c, d]3.2. Замена элементов в ArrayList
Чтобы заменить существующий элемент новым, мы можем использовать метод set(index, element).
ArrayList<String> listWithItems = new ArrayList<>(List.of("a", "b", "c", "d"));System.out.println(listWithItems); //[a, b, c, d]listWithItems.set(2, "T");System.out.println(listWithItems); //[a, b, T, d]3.3 Удаление элементов из ArrayList
Класс ArrayList предоставляет два метода для удаления элементов:
- remove(e): удаляет первое вхождение указанного элемента из этого списка, если оно присутствует, и возвращает true. В противном случае возвращает false.
- removeAll(collection): удаляет все элементы, содержащиеся в указанной коллекции. Возвращает true, даже если в результате этой операции удаляется один элемент, в противном случае возвращает false, если список не изменился.
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));list.remove("c"); // [a, b, d]list.removeAll(List.of("b", "d")); // [a]Мы можем использовать метод clear() для удаления всех элементов из списка за один вызов метода. Это сделает список пустым, с нулевыми элементами в нем.
list.clear(); // []
3.4 Проверка размера ArrayList
Чтобы получить размер массива или подсчитать количество элементов в списке, мы можем использовать метод size().
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));int size = list.size(); // 43.5 Проверка ArrayList на пустоту
Метод isEmpty() возвращает true, если список не содержит элементов. В противном случае возвращает false.
ArrayList<String> list = new ArrayList<>();boolean isEmpty = list.isEmpty(); // truelist.add("a");isEmpty = list.isEmpty(); // false4. Итерация по ArrayList
Являясь частью фреймворка Collection, мы можем использовать довольно много способов для перебора элементов ArrayList.
4.1 Использование ListIterator
Метод listIterator() класса ArrayList возвращает итератор типа ListIterator. Он позволяет перемещаться по списку в любом направлении, изменять список во время итерации и получать текущую позицию итератора в списке.
ListIterator<String> listIterator = list.listIterator();while(listIterator.hasNext()) {System.out.println(listIterator.next());}Стоит отметить, что методы remove() и set() в ListIterator не определены с точки зрения позиции курсора; они определены для работы с последним элементом, возвращенным вызовом next() или previous().
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));ListIterator<String> listIterator = list.listIterator();while(listIterator.hasNext()) {if(listIterator.next().equalsIgnoreCase("c")){listIterator.remove();}}System.out.println(list); // [a, b, d]4.2 Использование расширенного цикла for(for-each)
Мы также можем использовать цикл for-each с ArrayList.
ArrayList<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));list.forEach(e -> {System.out.println(e);});5. ArrayList и потоки Java
5.1 Итерация по элементам
Помимо цикла forEach() и ListIterator, мы можем использовать API Stream для итерации по элементам в ArrayList. Потоки позволяют нам выполнять больше операций над каждым элементом по мере их обработки.
arraylist.stream().forEach(e -> {System.out.println(e);});5.2 Фильтрующие элементы
Фильтрация потока помогает найти подсписок элементов из списка, соответствующих определенным критериям. Например, мы можем найти все четные числа из списка чисел следующим образом:
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));numbersList.stream().filter(n -> n % 2 == 0).forEach(System.out::println); // 2 4
5.3 Сокращение элементов с помощью reduce()
Операция сокращения чрезвычайно полезна при обработке каждого элемента в списке с использованием потоков и сборе результатов в другом списке. Обратите внимание, что исходный поток может исходить из любой структуры данных/типа коллекции, метод toList() всегда возвращает список результатов после обработки потока.
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));List<Integer> evenNumList = numbersList.stream().filter(n -> n % 2 == 0).toList();
В приведенном выше примере evenNumList является изменяемыми и имеет тип List. Если мы хотим собрать элементы в экземпляре ArrayList, мы можем использовать Collectors.toCollection(ArrayList::new) для создания нового ArrayList и сбора элементов в него.
ArrayList<Integer> numbersList = new ArrayList<>(List.of(1, 2, 3, 4, 5));ArrayList<Integer> evenNumList = numbersList.stream().filter(n -> n % 2 == 0).collect(Collectors.toCollection(ArrayList::new));
5.4 Отображение элементов с помощью map()
Операция Stream.map() может помочь в применении определенной логики к каждому элементу потока в сжатой форме. Например, в потоке чисел мы можем возвести каждое число в квадрат и собрать в новый список.
List<Integer> squareList = numbersList.stream().map(n -> n * n).toList();System.out.println(squareList); // [1, 4, 9, 16, 25]
6. Сортировка ArrayList
Сортировка является важной задачей при обработке данных, полученных из других источников. Чтобы отсортировать ArrayList, мы можем воспользоваться либо Collections.sort() для естественного порядка сортировки, либо реализовать пользовательский порядок сортировки, реализовав интерфейсы Comparable или Comparator.
6.1.Естественный порядок с помощью Collections.sort()
Collections.sort() сортирует указанный список в порядке возрастания, в соответствии с естественным порядком его элементов. Все элементы в списке должны реализовывать интерфейс Comparable.
ArrayList<Integer> arrayList = new ArrayList<>(List.of(2, 1, 4, 5, 3));Collections.sort(arrayList);System.out.println(arrayList); // [1, 2, 3, 4, 5]
Для пользовательских объектов мы можем определить естественный порядок в пользовательских объектах, реализовав интерфейс Comparable.
class Item implements Comparable <Item>{long id;String name;//...@Overridepublic int compareTo(Item item) {if(item.getName() == null || this.getName() == null){return -1;}return item.getName().compareTo(this.getName());}}6.2 Интерфейс компаратора пользовательского заказа
Мы можем применить пользовательский порядок сортировки, используя экземпляр Comparator. Мы можем либо использовать встроенные Comparators, такие как Comparator.reverseOrder(), либо создать собственную реализацию.
Collections.sort(arrayList, Comparator.reverseOrder());System.out.println(arrayList); // [5, 4, 3, 2, 1]
Чтобы создать пользовательский Comparator, мы можем создать экземпляр, сравнивая соответствующие поля на основе требований, и передать comparator методу sort(). Следующий пример сравнивает имена элементов в их естественном порядке.
ArrayList<Integer> itemList = ...;Comparator<Item> customOrder = Comparator.comparing(Item::getName);Collections.sort(itemList, customOrder);
7. Поиск элементов в ArrayList
7.1 Линейный поиск с использованием contains(), indexOf() и lastIndexOf()
Методы поиска в ArrayList выполняют линейный поиск, перебирая элементы один за другим, пока не будет найден нужный элемент или пока не будет достигнут конец списка.
Обычно для поиска элемента в ArrayList используются следующие 3 метода:
- contains(e): возвращает true, если список содержит хотя бы один указанный элемент, в противном случае возвращает false.
- indexOf(e): возвращает индекс первого вхождения указанного элемента в список или -1, если этот список не содержит элемента.
- lastIndexOf(e): возвращает индекс последнего вхождения указанного элемента в список или -1, если этот список не содержит элемента.
ArrayList<Integer> numList = new ArrayList<>(List.of(1, 2, 2, 3, 4, 4, 4, 5));System.out.println( numList.contains(2) ); //trueSystem.out.println( numList.contains(8) ); //falseSystem.out.println( numList.indexOf(4) ); //4System.out.println( numList.lastIndexOf(4) ); //6
7.2 Двоичный поиск с использованием Collections.binarySearch()
В больших массивах мы можем воспользоваться алгоритмом бинарного поиска для повышения производительности с помощью метода Collections.binarySearch().
Обратите внимание, что для корректной работы бинарного поиска список должен быть отсортирован.
Также, если список содержит несколько элементов, равных указанному объекту, нет гарантии, что один из них будет найден. Например, в numList элемент 4 появляется 3 раза. Этот метод может возвращать индекс любого из 3 элементов.
ArrayList<Integer> numList = new ArrayList<>(List.of(1, 2, 2, 3, 4, 4, 4, 5));Collections.sort(numList);int foundIndex = Collections.binarySearch(numList, 4); //5
8. Синхронизация и безопасность потоков
Класс ArrayList не является потокобезопасным. Использование его в параллельной среде может привести к несогласованным результатам. Мы можем использовать следующие методы для создания потокобезопасного arraylist.
8.1. Создание потокобезопасного ArrayList с помощью Collections.synchronizedList()
Метод Collections.synchronizedList() возвращает синхронизированный(потокобезопасный) список, поддерживаемый указанным списком. Все методы будут синхронизированы и могут использоваться для операций добавления/удаления в параллельных средах.
ArrayList<String> arrayList = new ArrayList<>();List<String> synchronizedList = Collections.synchronizedList(arrayList);synchronizedList.add("a"); //thread-safe operationОбратите внимание, что даже несмотря на то, что все методы add/remove/get/set являются потокобезопасными, итератор по-прежнему не является потокобезопасным и должен быть синхронизирован вручную.
List<String> synchronizedList = Collections.synchronizedList(arrayList);...synchronized(synchronizedList) {Iterator i = synchronizedList.iterator(); // Must be in synchronized blockwhile(i.hasNext()) {foo(i.next());}}8.2 Использование CopyOnWriteArrayList для одновременного доступа
CopyOnWriteArrayList — это потокобезопасный вариант ArrayList, в котором все мутационные операции(сложение, установка и т. д.) реализуются путем создания новой копии базового массива.
CopyOnWriteArrayList — хорошая альтернатива, когда итерации значительно превосходят число операций мутации. Это полезно, когда вы не можете или не хотите синхронизировать обходы, но при этом необходимо исключить помехи между параллельными потоками.
ArrayList<String> arrayList = new ArrayList<>();CopyOnWriteArrayList<String> concurrentList = new CopyOnWriteArrayList<>(arrayList);//all operations are thread-safeconcurrentList.add("a");for(String token : concurrentList) {System.out.print(token);}Полезно знать, что поскольку CopyOnWriteArrayList создает новую копию массива при каждой операции мутации, мы не столкнемся с исключением ConcurrentModificationException, даже если другие потоки изменяют список.
9. Подсписок ArrayList
9.1 Использование subList()
Метод subList(fromIndex, toIndex) возвращает представление части этого списка между указанным fromIndex, включительно, и toIndex, не включая. Если fromIndex и toIndex равны, возвращаемый список пуст.
ArrayList<Integer> origList = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));List<Integer> subList = origList.subList(2, 6); // [2, 3, 4, 5]
Обратите внимание, что возвращаемый список подкреплен исходным списком, поэтому все изменения добавления/удаления в подсписке отражаются в исходном списке, и наоборот.
subList.add(10);System.out.println(origList); // [0, 1, 2, 3, 4, 5, 10, 6, 7, 8, 9]
9.2 Использование потоков
List.stream().filter(…).toList(…) также можно использовать, если нам нужен подсписок только из элементов, соответствующих определенным критериям. Он не требует передачи индексов from и to.
ArrayList<Integer> origList = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));List<Integer> subListWithStream = origList.stream().filter(n -> n % 2 == 0).toList();
10. Производительность и временная сложность операций ArrayList
Производительность операций ArrayList варьируется от метода к методу. Методы, не требующие перемещения других элементов или изменения размера списка, лучше всего работают с O(1), тогда как другие методы выполняют O(n) в худших случаях, когда им нужно переместить все элементы в массиве.
- add(e): занимает постоянное время O(1), поскольку всегда добавляется в конец списка. Однако в худшем случае, если происходит изменение размера, временная сложность составляет O(n), где n — текущий размер ArrayList.
- add(index, e) и remove(e): имеют временную сложность O(n), поскольку может потребоваться сдвиг существующих элементов.
- get(i) и set(i, e): имеют постоянную временную сложность O(1) из-за прямого доступа к элементу на основе индекса.
- contains(), indexOf() и lastIndexOf(): имеют временную сложность O(n), поскольку они внутри используют линейный поиск.
11. Часто задаваемые вопросы
11.1 Разница между ArrayList и Array
В Java массивы и arraylist используются для хранения коллекций элементов в виде упорядоченной коллекции и предоставления индексного доступа к элементам. Тем не менее, есть несколько различий, как обсуждалось:
- Массивы — это структуры данных фиксированного размера, которые нельзя изменить после создания. Arraylist действует как массив с изменяемым размером, который динамически увеличивается/уменьшается, когда мы добавляем/удаляем из него элементы.
- ArrayList обеспечивает типобезопасность с помощью Generics. Массивы не обеспечивают такую типобезопасность и могут вызывать ClassCastException во время выполнения.
- ArrayList является частью фреймворка Collections и, таким образом, предоставляет встроенные методы утилит, которые прозрачно хранят и извлекают элементы из него. При использовании массивов нам необходимо вручную выполнять итерацию и отслеживать индексы массива и типы элементов.
11.2 Разница между ArrayList и LinkedList
Хотя ArrayList и LinkedList кажутся одинаковыми по функциональности, они сильно различаются в том, как хранят и обрабатывают элементы.
- ArrayList реализован как динамический массив, тогда как LinkedList реализован как двусвязный список, где каждый элемент(узел) содержит как данные, так и ссылки на предыдущий и следующий элементы в списке.
- Во время операций добавления, если достигается предел размера списка, выполняется изменение размера. В LinkedList изменение размера не требуется, поскольку новые элементы всегда добавляются как узлы, а корректируются только следующие и предыдущие ссылки.
- ArrayList требует меньше памяти, так как он сохраняет элементы в массиве и отслеживает их с помощью индекса массива. LinkedList требует больше памяти, так как ему нужно поддерживать ссылки на предыдущие и следующие элементы.
- ArrayList подходит, когда итераций списка больше, чем мутаций. LinkedList работает лучше, когда мутаций больше, чем итераций.
12. Заключение
Класс Java ArrayList — это превосходный служебный класс для хранения элементов в порядке вставки и выполнения различных операций над ними. Будучи частью фреймворка коллекций, он становится еще более привлекательным, поскольку хорошо интегрируется с другими классами и интерфейсами, а также потоками.