Перейти на PRO

Будет ли LinkedList менее производительным, чем ArrayList, при вставке большого количества элементов в конец в Java?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 10% Категория: Java Разработчик

Ответ

Нет, для операции добавления в конец (addLast/add) их асимптотическая сложность одинакова — O(1). Однако на практике ArrayList часто оказывается быстрее.

Сравнение:

  • LinkedList: Добавление в конец — O(1), так как структура хранит прямые ссылки на голову (head) и хвост (tail). Каждая операция требует создания нового узла (Node), что приводит к накладным расходам на выделение памяти.
  • ArrayList: Добавление в конец — амортизированное O(1). При заполнении внутреннего массива происходит его увеличение (обычно в 1.5-2 раза) и копирование элементов — операция O(n), но она случается редко, что даёт амортизированную константную сложность.

Почему ArrayList часто быстрее на практике:

  1. Локальность данных: Элементы ArrayList хранятся в непрерывном блоке памяти, что эффективно для кэша процессора.
  2. Меньше накладных расходов: ArrayList не создаёт объекты-узлы для каждого элемента.

Пример (псевдотест):

// ArrayList
List<Integer> arrayList = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i); // Амортизированное O(1)
}
System.out.println("ArrayList time: " + (System.nanoTime() - start));

// LinkedList
List<Integer> linkedList = new LinkedList<>();
start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    linkedList.add(i); // O(1)
}
System.out.println("LinkedList time: " + (System.nanoTime() - start));

Вывод: Для сценария только добавления в конец ArrayList обычно предпочтительнее из-за лучшей производительности в реальных условиях.

Ответ 18+ 🔞

Да ты посмотри, какая история интересная вырисовывается, блядь! Все думают, что раз LinkedList — это типа список, то он должен быть быстрее для добавления в конец. А нихуя подобного, ёпта!

Смотри, по бумажке-то у них сложность одинаковая — O(1), константная. Но это ж только на бумаге, сука! В жизни-то ArrayList чаще всего обгоняет эту мартышлюшку с узлами.

В чём подвох, блядь?

  • LinkedList: Да, O(1). У него есть прямая ссылка на хвост (tail), подбежал — прицепил новый узелок (Node). Но на каждый этот узел, блядь, память выделять надо, объект создавать. Это не бесплатные печеньки, нахуй!
  • ArrayList: Тоже O(1), но амортизированное. Это как кредит, блядь. Он в своём массиве жирует, места много. А как заполнится — БАЦ! — расширяется в полтора-два раза и всё копирует. Операция, конечно, O(n), пиздецкая, но она редкая. В среднем-то выходит тоже O(1), только выгоднее.

А на практике почему ArrayList рвёт?

  1. Локальность, ёбана! Элементы ArrayList лежат в памяти друг за дружкой, как солдаты в строю. Процессорный кэш это обожает, всё быстро подгружает. А LinkedList — это как пьяные мужики по всему кварталу раскиданы, к каждому бегать надо.
  2. Меньше телодвижений. ArrayList просто число в ячейку пихнул, а LinkedList для каждого числа целый объект-узел с ссылками плодит. Нахуй столько мусора?

Глянь, какой прикол (пример кода):

// ArrayList
List<Integer> arrayList = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i); // Вроде O(1), но по факту — овердохуища быстрее
}
System.out.println("ArrayList time: " + (System.nanoTime() - start));

// LinkedList
List<Integer> linkedList = new LinkedList<>();
start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    linkedList.add(i); // Тоже O(1), но с прицепом в виде узла
}
System.out.println("LinkedList time: " + (System.nanoTime() - start));

Уверен на 146%, что ArrayList оторвёт жопу этому связному списку. Так что если тебе просто в конец пихать — бери ArrayList и не еби мозг. LinkedList — он для других, более извращённых сценариев, где в середину часто вставляешь. А так — доверия к нему в этом деле ноль, блядь.

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