JavaNotes

List

3 min read

List

Определение и контракт

List<E> — упорядоченная коллекция. Элемент имеет позицию от 0 до size() - 1; дубликаты обычно разрешены. Контракт списка включает как последовательный обход, так и операции по индексу.

List<String> steps = new ArrayList<>();
steps.add("validate");
steps.add("save");
steps.add("save");
 
String second = steps.get(1); // "save"

Самые употребимые операции:

ОперацияМетоды
Доступget, set, indexOf, lastIndexOf
Вставкаadd(value), add(index, value), addAll
Удалениеremove(index), remove(object), removeIf
Обходiterator, listIterator, forEach
ДиапазонsubList(fromInclusive, toExclusive)
Сортировкаsort

ArrayList и LinkedList

ArrayList хранит ссылки в расширяемом массиве:

  • get и set — O(1);
  • добавление в конец — амортизированное O(1);
  • вставка или удаление в середине — O(n) из-за сдвига;
  • компактное размещение обычно хорошо использует кэш процессора.

LinkedList хранит двусвязную цепочку узлов:

  • доступ по индексу и поиск — O(n);
  • добавление с известных концов — O(1);
  • удаление через уже установленный итератор — O(1);
  • на каждый элемент нужны дополнительные ссылки.

На практике ArrayList — исходный выбор для большинства списков. Фраза «LinkedList быстрее вставляет в середину» неполна: сначала позицию обычно приходится искать за O(n).

subList — представление, а не копия

subList возвращает вид на диапазон исходного списка:

List<String> source = new ArrayList<>(
        List.of("A", "B", "C", "D")
);
List<String> middle = source.subList(1, 3);
 
middle.set(0, "X");
System.out.println(source); // [A, X, C, D]

Изменение через подсписок отражается в исходном списке. Структурное изменение исходника в обход subList делает дальнейшую работу представления неопределённой контрактом и обычно приводит к ConcurrentModificationException.

Для независимого результата нужна копия:

List<String> snapshot = new ArrayList<>(source.subList(1, 3));

Эта особенность однажды проявилась в реальной задаче: Кейс subList изменил исходный список.

Изменяемость

List<String> mutable = new ArrayList<>();
List<String> fixedSize = Arrays.asList("a", "b");
List<String> immutable = List.of("a", "b");
List<String> copy = List.copyOf(mutable);
  • ArrayList можно структурно менять.
  • Arrays.asList — представление фиксированного размера над массивом: set разрешён, add и remove — нет.
  • List.of и List.copyOf создают немодифицируемые списки и не допускают null.

Перегрузка remove

У List<Integer> выражение remove(1) выбирает перегрузку по индексу:

List<Integer> values = new ArrayList<>(List.of(1, 2, 3));
values.remove(Integer.valueOf(1)); // удалить значение 1

ListIterator

ListIterator умеет двигаться в обе стороны, узнавать соседние индексы и безопасно изменять список через сам итератор:

ListIterator<String> it = steps.listIterator();
while (it.hasNext()) {
    if (it.next().isBlank()) {
        it.remove();
    }
}

Ловушки

  • Путать индекс и значение в remove.
  • Хранить subList дольше исходного списка или считать его копией.
  • Выбирать LinkedList по одной только асимптотике вставки.
  • Изменять обычный список внутри enhanced for.
  • Возвращать внутренний mutable-список из объекта и тем самым отдавать наружу его состояние.

Вопросы на собеседовании

  1. Какие гарантии добавляет List к контракту Collection?
  2. Почему добавление в конец ArrayList амортизированно O(1)?
  3. Когда LinkedList действительно может быть уместен?
  4. Чем отличаются List.of, Arrays.asList и new ArrayList<>()?
  5. Как устроен subList и почему с ним легко получить неожиданный побочный эффект?
  6. Как удалить число 1 из List<Integer>, а не элемент с индексом 1?

Связанные заметки

Collection · Иерархия коллекций · Big O оценка сложности операций с коллекциями · Queue and Deque · Comparator Java · Кейс subList изменил исходный список

Graph View

Backlinks