Руководство по Java ArrayList

В этой статье рассмотрим класс ArrayList из Java Collections Framework. Обсудим его свойства, распространенные варианты использования, а также преимущества и недостатки.

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

import java.util.ArrayList;

List представляет собой упорядоченную последовательность значений, в которой некоторое значение может встречаться более одного раза.

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

  • Произвольный доступ занимает время O(1)
  • Добавление элемента занимает амортизированное постоянное время O(1)
  • Вставка/удаление занимает O(n) времени
  • Поиск занимает O(n) времени для неотсортированного массива и O(log n) для отсортированного.

Создание ArrayList

ArrayList имеет несколько конструкторов, и все они будут представлены в этом разделе.

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

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

Конструктор по умолчанию без аргументов

List<String> list = new ArrayList<>();
assertTrue(list.isEmpty());

Создаем пустой экземпляр ArrayList.

Конструктор принимает начальную емкость

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

Здесь указываем начальную длину базового массива. Это может помочь избежать ненужного изменения размера при добавлении новых элементов.

Конструктор, принимающий коллекцию

Collection<Integer> number 
  = IntStream.range(0, 10).boxed().collect(toSet());

List<Integer> list = new ArrayList<>(numbers);
assertEquals(10, list.size());
assertTrue(numbers.containsAll(list));

Обратите внимание, что этот элемент экземпляра Collection используется для заполнения базового массива.

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

Можно вставить элемент либо в конец, либо в определенной позиции:

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

list.add(1L);
list.add(2L);
list.add(1, 3L);

assertThat(Arrays.asList(1L, 3L, 2L), equalTo(list));

Можно вставить коллекцию или несколько элементов одновременно:

List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L));
LongStream.range(4, 10).boxed()
  .collect(collectingAndThen(toCollection(ArrayList::new), ys -> list.addAll(0, ys)));
assertThat(Arrays.asList(4L, 5L, 6L, 7L, 8L, 9L, 1L, 2L, 3L), equalTo(list));

Итерация по ArrayList

Доступны два типа итераторов: Iterator и ListIterator.

Первый дает возможность перемещаться по списку в одном направлении, второй позволяет перемещаться по нему в обоих направлениях. Здесь будет показан только ListIterator:

List<Integer> list = new ArrayList<>(
  IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);
ListIterator<Integer> it = list.listIterator(list.size());
List<Integer> result = new ArrayList<>(list.size());
while (it.hasPrevious()) {
    result.add(it.previous());
}

Collections.reverse(list);
assertThat(result, equalTo(list));

Можно искать, добавлять или удалять элементы с помощью итераторов.

Поиск в ArrayList

Посмотрим, как работает поиск с использованием коллекции:

List<String> list = LongStream.range(0, 16)
  .boxed()
  .map(Long::toHexString)
  .collect(toCollection(ArrayList::new));
List<String> stringsToSearch = new ArrayList<>(list);
stringsToSearch.addAll(list);

Поиск в неотсортированном списке

Чтобы найти элемент, можно использовать методы indexOf() или lastIndexOf(). Они оба принимают объект и возвращают значение int:

assertEquals(10, stringsToSearch.indexOf("a"));
assertEquals(26, stringsToSearch.lastIndexOf("a"));

Если хотите найти все элементы, удовлетворяющие предикату, можно отфильтровать коллекцию с помощью Java 8 Stream API (подробнее об этом здесь), используя Predicate следующим образом:

Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));

List<String> result = stringsToSearch
  .stream()
  .filter(matchingStrings::contains)
  .collect(toCollection(ArrayList::new));

assertEquals(6, result.size());

Можно использовать цикл for или итератор:

Iterator<String> it = stringsToSearch.iterator();
Set<String> matchingStrings = new HashSet<>(Arrays.asList("a", "c", "9"));

List<String> result = new ArrayList<>();
while (it.hasNext()) {
    String s = it.next();
    if (matchingStrings.contains(s)) {
        result.add(s);
    }
}

Поиск в отсортированном списке

Если есть отсортированный массив, можно использовать алгоритм двоичного поиска, который работает быстрее, чем линейный поиск:

List<String> copy = new ArrayList<>(stringsToSearch);
Collections.sort(copy);
int index = Collections.binarySearch(copy, "f");
assertThat(index, not(equalTo(-1)));

Обратите внимание, что, если элемент не найден, будет возвращено -1.

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

Для того, чтобы удалить элемент, нужно найти его индекс и только потом выполнять удаление методом remove(). Перегруженная версия этого метода, которая принимает объект, ищет его и выполняет удаление первого вхождения равного элемента:

List<Integer> list = new ArrayList<>(
  IntStream.range(0, 10).boxed().collect(toCollection(ArrayList::new))
);
Collections.reverse(list);

list.remove(0);
assertThat(list.get(0), equalTo(8));

list.remove(Integer.valueOf(0));
assertFalse(list.contains(0));

Но будьте осторожны при работе с оберточными типами, такими как Integer. Чтобы удалить конкретный элемент, необходимо сначала указать значение int, иначе элемент будет удален по его индексу. Можно использовать вышеупомянутый Stream API для удаления нескольких элементов, но здесь он не будет показан. Для этого будем использовать итератор:

Set<String> matchingStrings
 = HashSet<>(Arrays.asList("a", "b", "c", "d", "e", "f"));

Iterator<String> it = stringsToSearch.iterator();
while (it.hasNext()) {
    if (matchingStrings.contains(it.next())) {
        it.remove();
    }
}

Заключение

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

Можно найти все примеры кода на GitHub.

Оригинал

➜