0Pricing
Java Academy · Урок

Компромиссы LinkedList и ArrayList

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

«Компромиссы LinkedList и ArrayList» — бесплатный урок Java Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Главный вопрос

И ArrayList, и LinkedList реализуют List, поэтому у них одинаковый API. Различие заключается во внутренних структурах данных и операциях, которые каждый из них выполняет эффективно.

Внутреннее устройство ArrayList

ArrayList хранит элементы в непрерывном массиве. Когда массив заполняется, его заменяет новый массив размером в 1,5 раза больше, и все элементы копируются.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Внутреннее устройство LinkedList: повторение

Каждый элемент находится в отдельном объекте Node с указателями prev/next. Непрерывной области памяти нет — узлы могут располагаться в разных местах кучи.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Произвольный доступ: преимущество ArrayList

ArrayList.get(i) выполняется за O(1) — используется прямой индекс массива. LinkedList.get(i) выполняется за O(n) — просматривается до n/2 узлов.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Вставка в начало: преимущество LinkedList

Добавление по индексу 0 в ArrayList требует сдвига всех элементов — O(n). LinkedList просто обновляет два указателя — O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Вставка в конец: примерно одинаковая производительность

И ArrayList, и LinkedList обеспечивают амортизированное добавление элементов в конец за O(1). ArrayList иногда запускает копирование при изменении размера, но амортизированная сложность все равно составляет O(1). LinkedList выделяет новый узел — изменение размера не требуется.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Использование памяти

ArrayList: около 8 байт на элемент (одна ссылка в массиве). LinkedList: около 48 байт на элемент (объект Node с данными, prev, next и заголовком объекта). Для больших наборов данных ArrayList использует значительно меньше памяти.

Производительность итерации

Последовательная итерация (цикл for-each или итератор) выполняется за O(n) в обоих случаях. Но ArrayList получает преимущество благодаря предварительной загрузке данных в кэш CPU: элементы расположены в памяти непрерывно. Узлы LinkedList разбросаны по куче, что приводит к промахам кэша.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Вставка и удаление в середине

В обоих случаях для поиска позиции требуется O(n). После ее нахождения ArrayList сдвигает элементы за O(n), а LinkedList просто отсоединяет узел за O(1). Поэтому при частых изменениях в середине если у вас уже есть итератор LinkedList эффективнее; в остальных случаях разница невелика.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Руководство по выбору

Выбирайте структуру с учетом основной операции:

  • ArrayList: произвольный доступ, итерация, добавление в конец — подходит для 90% сценариев
  • LinkedList: частые добавления и удаления в начале или конце, реализация очереди, двусторонней очереди или стека
  • ArrayDeque: если нужен только стек или очередь (лучше, чем LinkedList)

Итоги сравнения производительности

Ментальная модель производительности:

  • get(i): ArrayList O(1) против LinkedList O(n)
  • add(0,x): ArrayList O(n) против LinkedList O(1)
  • add(x): в обоих случаях амортизированно O(1)
  • Удаление через итератор: в обоих случаях O(1) после перехода к нужной позиции
  • Память на элемент: ArrayList около 8 Б против LinkedList около 48 Б

Быстрая проверка

Вы создаете очередь задач, в которую задачи добавляются в конец и удаляются из начала миллионы раз в секунду. Какая структура данных наиболее уместна?

Повторение: LinkedList и ArrayList

Основные выводы:

  • ArrayList эффективен при произвольном доступе (O(1)) и последовательном обходе с хорошим использованием кэша
  • LinkedList эффективен для операций с началом и концом списка за O(1)
  • Память: ArrayList — около 8 байт на элемент; LinkedList — около 48 байт на элемент
  • Для очередей и стеков предпочитайте ArrayDeque, а не LinkedList
  • В большинстве случаев ArrayList — правильный выбор по умолчанию

Часто задаваемые вопросы

Урок «Компромиссы LinkedList и ArrayList» бесплатный?

Да — полный текст урока «Компромиссы LinkedList и ArrayList» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Компромиссы LinkedList и ArrayList»?

Сравните производительность вставки, удаления и произвольного доступа, чтобы выбрать подходящий тип списка. Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Компромиссы LinkedList и ArrayList»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Внутреннее устройство LinkedList
  2. Операции Deque: стек и очередь
  3. Компромиссы LinkedList и ArrayList
  4. PriorityQueue для упорядоченной обработки
← Назад к Java Academy