Чем отличаются LinkedList и ArrayList

LinkedList и ArrayList — две реализации интерфейса List в Java, различающиеся внутренней структурой данных и, как следствие, производительностью операций. ArrayList основан на динамическом массиве, а LinkedList — на двусвязном списке. Выбор между ними зависит от того, какие операции преобладают в приложении: доступ по индексу или вставка/удаление элементов.

Как это работает

ArrayList хранит элементы в обычном массиве, размер которого автоматически увеличивается при добавлении новых элементов. Когда массив заполняется, создается новый массив большего размера (обычно в 1.5 раза), и все элементы копируются в него. Это обеспечивает быстрый доступ по индексу за O(1), но вставка или удаление элемента в середине списка требует сдвига всех последующих элементов, что занимает O(n) времени.

LinkedList состоит из узлов, каждый из которых содержит данные и ссылки на предыдущий и следующий узлы. Это позволяет вставлять и удалять элементы за O(1) при условии, что у вас есть ссылка на нужный узел. Однако доступ по индексу требует прохода по списку от начала или конца, что в худшем случае занимает O(n).

Сравнение производительности

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

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

ArrayList — лучший выбор, если:

• Основная операция — доступ к элементам по индексу.
• Вставка и удаление происходят преимущественно в конце списка.
• Список редко изменяется, и важна экономия памяти.

LinkedList — лучший выбор, если:

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

Подводные камни

• Не используйте LinkedList для частого доступа по индексу — это приведет к значительному снижению производительности.
• LinkedList потребляет больше памяти из-за хранения ссылок на соседние узлы.
• При вставке в середину LinkedList все равно требуется найти нужную позицию, что занимает O(n), если у вас нет ссылки на узел.
• В Java LinkedList также реализует интерфейсы Deque и Queue, что расширяет его функциональность, но не всегда оправдано.

Коротко

• ArrayList — динамический массив, быстрый доступ по индексу, медленные вставки/удаления в середине.
• LinkedList — двусвязный список, быстрые вставки/удаления в начале и середине, медленный доступ по индексу.
• Выбирайте ArrayList для большинства случаев, особенно если нужен доступ по индексу.
• Используйте LinkedList, когда критичны частые вставки/удаления в начале списка или нужны возможности дека.