Что выберешь для вставки элемента в конец миллионного списка: ArrayList или LinkedList

# Что выбрать для вставки элемента в конец миллионного списка: ArrayList или LinkedList

Это классический вопрос на интервью, который проверяет понимание внутреннего устройства коллекций. Парадоксально, но правильный ответ — ArrayList, хотя многие интуитивно выбирают LinkedList.

Теория: почему LinkedList кажется логичным выбором

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

// LinkedList: вставка в конец O(1)
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1000000);

// ArrayList: вставка в конец O(1) амортизированная
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1000000);

Практика: ArrayList выигрывает

Несмотря на теорию, на практике ArrayList намного быстрее для этого сценария:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListPerformanceTest {
    public static void main(String[] args) {
        // Тест ArrayList
        long startTime = System.nanoTime();
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 1_000_000; i++) {
            arrayList.add(i);
        }
        long arrayListTime = System.nanoTime() - startTime;
        System.out.println("ArrayList: " + arrayListTime / 1_000_000 + " ms");
        
        // Тест LinkedList
        startTime = System.nanoTime();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 1_000_000; i++) {
            linkedList.add(i);
        }
        long linkedListTime = System.nanoTime() - startTime;
        System.out.println("LinkedList: " + linkedListTime / 1_000_000 + " ms");
    }
}

Типичный результат:

• ArrayList: 10 ms
• LinkedList: 150 ms
• ArrayList быстрее в 15 раз!

Причина 1: Cache Locality

ArrayList хранит элементы в смежных блоках памяти, что очень эффективно для CPU кэша. LinkedList разбросан по памяти, поэтому CPU кэш не может помочь.

Причина 2: Memory Overhead

Структура LinkedList требует дополнительной памяти на каждый элемент:

// ArrayList: просто значение в массиве
Object[] items;

// LinkedList: значение + две ссылки
class Node<E> {
    E item;
    Node<E> next;      // +8 байт
    Node<E> previous;  // +8 байт
}

Для миллиона элементов LinkedList требует на 16 МБ больше памяти!

Причина 3: Garbage Collection

LinkedList создает миллион объектов Node, что нагружает GC:

• ArrayList: примерно 2 объекта
• LinkedList: 1 миллион объектов

Сравнение разных операций

Правильный ответ

Для вставки элемента в конец миллионного списка выберешь ArrayList потому что:

• Лучше cache locality — элементы находятся рядом в памяти
• Меньше memory overhead — не нужны ссылки на соседей
• Меньше нагрузка на GC — меньше объектов создается
• На практике в 10-20 раз быстрее

List<Integer> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);  // Это будет быстро
}

Когда выбрать LinkedList

LinkedList имеет смысл только если:

• Частые вставки и удаления с НАЧАЛА списка
• Реализация очереди (Queue) или стека (Stack)
• Нужна вставка в СЕРЕДИНУ из итератора

Queue<String> queue = new LinkedList<>();
Deque<String> deque = new LinkedList<>();

Итоговый совет

Используй ArrayList по умолчанию. Это оптимальный выбор для большинства случаев. Выбирай LinkedList только если явно нужны операции с началом списка в большом количестве.