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

«1. Обзор

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

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

import java.util.ArrayList;

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

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

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

2. Создайте ArrayList

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

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

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

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

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

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

2.2. Конструктор, принимающий начальную емкость

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

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

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

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

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

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

3. Добавление элементов в 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));

~ ~~ 4. Итерация по 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));

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

5. Поиск в 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);

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

Чтобы найти элемент, вы можете использовать методы 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);
    }
}

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

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

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

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

6. Удаление элементов из 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();
    }
}

7. Резюме

В этой быстрой статье мы рассмотрели ArrayList в Java.

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

Как обычно, вы можете найти все примеры кода на GitHub.