В чем разница между ArrayList и LinkedList в Java?

Тип вопроса: Java Вероятность: 23% Категория: AQA / Automation

Ответ

ArrayList и LinkedList — две разные реализации интерфейса List<E>, основанные на различных структурах данных, что определяет их производительность в разных сценариях.

ArrayList

  • Внутренняя структура: Динамически расширяемый массив (Object[]).
  • Доступ по индексу: O(1) — мгновенный, так как это обращение к элементу массива.
  • Вставка/удаление:
    • В конец списка (если не требуется расширение) — O(1).
    • В начало или середину — O(n), так как требует сдвига всех последующих элементов.
  • Использование памяти: Меньше накладных расходов, хранит только данные и размер массива.

LinkedList

  • Внутренняя структура: Двусвязный список из узлов (Node<E>), где каждый узел содержит ссылки на предыдущий и следующий элемент.
  • Доступ по индексу: O(n) — требует последовательного перебора узлов от начала или конца списка.
  • Вставка/удаление: O(1), если известна позиция (узел). Изменяются только ссылки у соседних узлов.
  • Использование памяти: Больше накладных расходов на хранение двух ссылок в каждом узле.

Пример сравнения операций:

// ArrayList - быстрый доступ, медленная вставка в середину
List<String> arrayList = new ArrayList<>(Arrays.asList("A", "B", "D"));
arrayList.get(1); // Быстро (O(1))
arrayList.add(2, "C"); // Медленно (O(n)) - сдвигает "D"

// LinkedList - медленный доступ, быстрая вставка
List<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "D"));
linkedList.get(1); // Медленно (O(n)) - перебор узлов
linkedList.add(2, "C"); // Быстро (O(1)) - меняет ссылки у B<->D

Когда что использовать:

  • ArrayList: В большинстве случаев, особенно при частом чтении и случайном доступе. Оптимален по памяти и скорости доступа.
  • LinkedList: Когда преобладают операции вставки/удаления в начале или середине списка, и доступ по индексу используется редко. Также подходит для реализации стеков (Deque) и очередей.

Ответ 18+ 🔞

Давай разберём эту дичь, про которую все так любят говорить, но мало кто реально понимает, что там под капотом творится. ArrayList и LinkedList — это как два брата-близнеца, но один родился с золотой ложкой в жопе (массив), а второй — с кучей верёвочек и узлов в голове (список). И ведут они себя, блядь, по-разному, хоть и оба List<E>.

ArrayList, или "Всё в кучу, по порядку"

  • Что внутри? Обычный, ёбаный, динамический массив (Object[]). Представь себе полку — всё стоит ровненько, пронумеровано.
  • Достать что-то по номеру: O(1). Это просто космос, блядь. Сказал "дай пятый элемент" — и вот он, на блюдечке. Потому что это обращение в массив, там всё мгновенно.
  • Засунуть или выкинуть что-то:
    • В самый конец (если место есть) — O(1). Поставил и забыл.
    • В начало или в середину — O(n). Вот тут начинается пиздец. Представь, ты вставляешь книгу на третью полку. Всё, что после неё, надо сдвинуть, блядь, на одну позицию! Весь этот сдвиг — это и есть O(n). Чем список длиннее, тем дольше.
  • Память: Тратит меньше. Хранит только данные и размер своего массива. Никакой лишней хуйни.

LinkedList, или "Все за ручки держатся"

  • Что внутри? Двусвязный список, ёпта. Каждый элемент (Node<E>) — это такой чувак, который держит свою ценность и двумя руками хватается за соседей: одного спереди, другого сзади.
  • Достать что-то по номеру: O(n). А вот это уже пиздец какой медленный цирк. Хочешь 100-й элемент? Начинай с первого, спроси у него "а где следующий?", доберись до второго, и так, блядь, 100 раз. Либо иди с конца, если он ближе. В общем, перебор.
  • Засунуть или выкинуть что-то: O(1), если ты УЖЕ стоишь на нужном месте. Это его конёк, блядь! Надо вставить C между B и D? Идеально. Сказал B отпустить руку D и взять за руку C, а C — взять за руку D. Всё, ссылки поменялись, никто никого не сдвигал, красота.
  • Память: Жрёт больше. Каждому "чуваку" (узлу) надо хранить не только свою ценность, но и две ссылки-руки на соседей. Накладные расходы, блядь.

Смотри, как это в коде выглядит, на простых примерах:

// ArrayList - быстро достал, но вставка в середину может всё разъебать
List<String> arrayList = new ArrayList<>(Arrays.asList("A", "B", "D"));
arrayList.get(1); // Мгновенно, как удар тока. "B" твоя.
arrayList.add(2, "C"); // Опа, вставляем "C" перед "D". Теперь "D" и всё после него (если бы было) надо сдвигать. Медленно.

// LinkedList - долго искать, но вставить между своими — раз плюнуть
List<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "D"));
linkedList.get(1); // Э, дружок, тут придётся пройтись от "A" до "B". Небыстро.
linkedList.add(2, "C"); // А вот это — его стихия. "B" отпустил "D", обнял "C", "C" обнял "D". Готово, быстро.

Так когда что брать, чтобы не обосраться?

  • ArrayList — твой выбор в 95% случаев. Читаешь часто, обращаешься по индексу, добавляешь в основном в конец? Он твой лучший друг. Памяти мало жрёт, доступ быстрый — красота.
  • LinkedList — для особых извращений. Если у тебя постоянно какая-то хуйня: вставить в начало, удалить из середины, ещё раз вставить, и при этом тебе пофиг на доступ по индексу (или ты итерируешься и всё запоминаешь). Или если ты делаешь очередь (Deque) — он для этого с рождения подходит. Но если начнёшь по индексу лазить — готовься к боли, O(n) это тебе не шутки.

Короче, думай головой, что ты делаешь, а не тыкай наугад. Иначе получишь перформанс в виде разбитого корыта.

© ХакСобесов, 2026
support@hacksobesov.com