Перейти к основному содержимому

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

· 5 мин. чтения

Задача: Медиана двух отсортированных массивов

Даны два отсортированных массива размерами n и m. Найдите медиану слияния этих двух массивов.
Временная сложность решения должна быть O(log(m + n)) ...

ANDROMEDA

1. Обзор

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

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

import java.util.ArrayList;

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

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

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

2. Создайте список массивов

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

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

Во-вторых, хорошей практикой является использование универсального интерфейса 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));

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

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. Поиск в списке массивов

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

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 .