Какая разница между LinkedList и ArrayList?

Какая разница между LinkedList и ArrayList?

Это один из самых частых вопросов на интервью, и ответ демонстрирует понимание структур данных. Обе являются реализациями интерфейса List, но работают совершенно по-разному.

Внутренняя структура

ArrayList — динамический массив

// Внутри ArrayList лежит обычный массив
ArrayList<String> list = new ArrayList<>();
list.add("A");  // Индекс 0
list.add("B");  // Индекс 1
list.add("C");  // Индекс 2

// В памяти:
// [A][B][C][пусто][пусто]...
//  0  1  2

Когда массив переполняется, создаётся новый массив большего размера (обычно 1.5x):

// После добавления 4-го элемента
// Старый массив: [A][B][C]
// Новый массив: [A][B][C][D][пусто][пусто]...

LinkedList — двусвязный список

// Внутри LinkedList — цепочка узлов
LinkedList<String> list = new LinkedList<>();
list.add("A");  // Node1: prev=null, value="A", next=Node2
list.add("B");  // Node2: prev=Node1, value="B", next=Node3
list.add("C");  // Node3: prev=Node2, value="C", next=null

// В памяти:
// null <- [A] <-> [B] <-> [C] -> null

Сравнение операций

1. Доступ к элементу по индексу

ArrayList<String> al = new ArrayList<>();
// ... добавить 1000000 элементов

String elem = al.get(999999);  // O(1) — быстро
// Просто обращаемся к массиву по индексу

LinkedList<String> ll = new LinkedList<>();
// ... добавить 1000000 элементов

String elem = ll.get(999999);  // O(n) — медленно
// Нужно пройти по цепочке от начала или конца

2. Добавление в начало списка

ArrayList<String> al = new ArrayList<>();
al.add("B");
al.add("C");

al.add(0, "A");  // O(n) — медленно
// Нужно сдвинуть все элементы на одну позицию
// [A][B][C][пусто] -> сдвигаем -> [A][B][C]

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

ll.addFirst("A");  // O(1) — быстро
// Просто создаём новый узел в начале:
// null <- [A] <-> [B] <-> [C] -> null

3. Добавление в конец

ArrayList<String> al = new ArrayList<>();
al.add("A");  // O(1) в среднем (иногда O(n) при расширении)
al.add("B");  // Просто добавляем в конец массива

LinkedList<String> ll = new LinkedList<>();
ll.add("A");  // O(1)
ll.add("B");  // Просто добавляем в конец цепочки

4. Удаление элемента

ArrayList<String> al = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
al.remove(1);  // O(n) — медленно
// Удаляем B: [A][B][C][D] -> [A][C][D]
// Нужно сдвинуть все элементы после удаляемого

LinkedList<String> ll = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));
Iterator<String> it = ll.iterator();
it.next();  // A
it.remove();  // O(1) — быстро если использовать Iterator
// Просто переставляем ссылки:
// null <- [B] <-> [C] <-> [D] -> null

Таблица сравнения

Операция              ArrayList    LinkedList
─────────────────────────────────────────────
Доступ по индексу     O(1)        O(n)
Добавление в конец    O(1)*       O(1)
Добавление в начало   O(n)        O(1)
Добавление в середину O(n)        O(n)** 
Удаление из конца     O(1)        O(1)
Удаление из начала    O(n)        O(1)
Удаление из середины  O(n)        O(1)** (с Iterator)
Использование памяти  Меньше      Больше (указатели)

* Может быть O(n) при расширении массива
** При наличии Iterator

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

@Test
void performanceComparison() {
    int iterations = 100_000;
    
    // ArrayList - добавление в конец быстро
    ArrayList<Integer> al = new ArrayList<>();
    long start = System.nanoTime();
    for (int i = 0; i < iterations; i++) {
        al.add(i);  // O(1) в среднем
    }
    long alTime = System.nanoTime() - start;
    System.out.println("ArrayList add: " + alTime + "ms");
    
    // LinkedList - добавление в конец тоже O(1), но медленнее из-за overhead
    LinkedList<Integer> ll = new LinkedList<>();
    start = System.nanoTime();
    for (int i = 0; i < iterations; i++) {
        ll.add(i);  // O(1) но с overhead выделения памяти
    }
    long llTime = System.nanoTime() - start;
    System.out.println("LinkedList add: " + llTime + "ms");
    
    // ArrayList - доступ по индексу очень быстро
    start = System.nanoTime();
    for (int i = 0; i < iterations; i++) {
        al.get(i);  // O(1)
    }
    long alGetTime = System.nanoTime() - start;
    System.nanoTime();
    
    // LinkedList - доступ по индексу медленно
    start = System.nanoTime();
    for (int i = 0; i < iterations; i++) {
        ll.get(i);  // O(n)
    }
    long llGetTime = System.nanoTime() - start;
    System.out.println("LinkedList get: " + llGetTime + "ms");
    
    // Типичный результат:
    // ArrayList get: 1ms
    // LinkedList get: 1000ms (в 1000 раз медленнее!)
}

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

ArrayList

• Частый доступ по индексу — get(i), set(i, value)
• Основные операции в конце списка — add(), remove()
• Нужна память компактнее — LinkedList использует больше памяти
• Когда не уверен — ArrayList по умолчанию лучше выбор

Примеры:

List<User> users = new ArrayList<>();  // Обычный случай
List<Integer> numbers = new ArrayList<>();  // Частый get() и set()

LinkedList

• Часто добавляешь/удаляешь в начало — addFirst(), removeFirst()
• Используешь Deque операции — push(), pop(), poll()
• Обработка с Iterator и remove() через итератор
• Не нужен random access — только итерация

Примеры:

Deque<String> stack = new LinkedList<>();  // Стек/очередь
LinkedList<Task> queue = new LinkedList<>();  // Очередь
// queue.removeFirst(), queue.addLast()

Best Practices

• По умолчанию используй ArrayList — для 90% случаев это оптимальный выбор
• Избегай LinkedList без веских причин — много разработчиков ошибочно думают, что LinkedList лучше
• Если нужна Deque (двусторонняя очередь), используй LinkedList или ArrayDeque
• Помни про память — каждый узел LinkedList использует ~24-40 байт для хранения ссылок

Интересный факт

В Java 6+ есть ArrayDeque — это лучше для очередей (Deque), чем LinkedList:

• Двусторонняя очередь
• Работает как динамический массив, а не список
• Быстрее чем LinkedList для push/pop операций
• Использует меньше памяти

// Вместо LinkedList для очередей
Deque<String> deque = new ArrayDeque<>();  // Лучше!
deque.push("A");
deque.pop();

Главное помнить: ArrayList — скорый доступ, LinkedList — быстрые вставки/удаления в начало.