Когда использовать LinkedList вместо ArrayList в Java?

Понимание внутреннего устройства: почему ваши тесты не показывают преимуществ LinkedList

Ваш тест корректен, но он демонстрирует распространённое заблуждение. Давайте разберёмся, как работают обе реализации.

ArrayList: массив с динамическим расширением

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

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

• Каждый элемент — отдельный объект Node с ссылками на предыдущий и следующий
• Добавление в конец — O(1) (есть ссылка на последний элемент)
• Доступ по индексу — O(n) (нужно пройти от начала или конца)
• Вставка/удаление в середине — O(n) (поиск позиции + O(1) на перестановку ссылок)

Вот почему ваш тест на вставку в середину показал одинаковую сложность O(n) для обоих — LinkedList тоже должен сначала найти позицию 50000, проходя по ссылкам!

Когда LinkedList действительно выигрывает

LinkedList становится эффективнее, когда вы уже имеете итератор на нужную позицию. Например, при удалении во время итерации:

// LinkedList — O(1)
Iterator<String> iter = linkedList.iterator();
while (iter.hasNext()) {
    String s = iter.next();
    if (s.length() < 3) {
        iter.remove(); // Удаление через итератор — O(1)
    }
}

// ArrayList — O(n) из-за сдвига
for (int i = 0; i < arrayList.size(); i++) {
    if (arrayList.get(i).length() < 3) {
        arrayList.remove(i); // Каждое удаление сдвигает элементы
        i--; // Нужно корректировать индекс
    }
}

Практические сценарии использования

Используйте ArrayList, когда:

• Нужен быстрый доступ по индексу (95% случаев)
• Элементы добавляются преимущественно в конец
• Важна компактность памяти (нет накладных расходов на Node-объекты)
• Работа с большими объёмами данных (локальность кэша процессора)

Используйте LinkedList, когда:

• Часто удаляете/добавляете элементы через итератор (например, реализация очереди или дека)
• Реализуете структуру, где элементы удаляются с обоих концов (Deque операции)
• Неизвестен размер коллекции и требуется минимизировать затраты на расширение (хотя ArrayList справляется хорошо)

Реальный пример: очередь задач

// LinkedList как Queue/Deque — идеально
Queue<Task> taskQueue = new LinkedList<>();
taskQueue.offer(new Task("Задача 1"));
taskQueue.offer(new Task("Задача 2"));
Task next = taskQueue.poll(); // O(1) — удаление из начала

// ArrayList для этого не подходит:
// queue.remove(0) — O(n) сдвиг всех элементов

Итоговые рекомендации

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

Если сомневаетесь — профилируйте свой конкретный случай. Но для большинства приложений ArrayList — правильный выбор по умолчанию.

class LRUCache<K, V> {
    private final int capacity;
    private final LinkedHashMap<K, V> cache;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }
}