LinkedList или ArrayList в Java: что выбрать и почему это важно

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

LinkedList или ArrayList: битва титанов коллекций Java

Если вы когда-нибудь писали на Java код, который работает со списками данных, вы наверняка сталкивались с дилеммой: LinkedList или ArrayList? Этот вопрос — настоящий хит на Stack Overflow, его обсуждают тысячи разработчиков. И не зря. Выбор неправильной структуры данных может превратить ваш быстрый код в черепаху, которая ползёт по болоту. А правильный выбор — сделать приложение отзывчивым и эффективным.

Сегодня мы не просто перечислим сухие факты. Мы заглянем под капот Java, разберёмся, как работают эти коллекции на уровне памяти и процессора, и дадим чёткий ответ: когда же всё-таки стоит использовать LinkedList, а когда — ArrayList. Поехали!

Коротко о главном: что говорят джентльмены из документации

Начнём с основ. Оба класса реализуют интерфейс List, но делают это по-разному.

ArrayList — это динамический массив. Он хранит элементы в непрерывном блоке памяти. Когда массив заполняется, он создаёт новый, большего размера, и копирует туда все элементы.
LinkedList — это двусвязный список. Каждый элемент (узел) хранит ссылки на предыдущий и следующий элементы. Память выделяется для каждого узла отдельно.

Звучит просто. Но дьявол, как всегда, в деталях. Давайте посмотрим на код.

Под капотом: как это работает на практике

ArrayList: скорость доступа, но медленная вставка в середину

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

public class ArrayListDemo {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        
        // Добавление в конец — быстро (O(1) амортизированно)
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            arrayList.add("Element " + i);
        }
        long end = System.nanoTime();
        System.out.println("ArrayList add (в конец): " + (end - start) / 1e6 + " ms");
        
        // Доступ по индексу — мгновенно (O(1))
        start = System.nanoTime();
        String element = arrayList.get(50000);
        end = System.nanoTime();
        System.out.println("ArrayList get: " + (end - start) + " ns");
        
        // Вставка в середину — медленно (O(n))
        start = System.nanoTime();
        arrayList.add(25000, "INSERTED");
        end = System.nanoTime();
        System.out.println("ArrayList insert (середина): " + (end - start) / 1e6 + " ms");
    }
}

Что здесь происходит? Когда вы вставляете элемент в середину ArrayList, все элементы справа от точки вставки сдвигаются на одну позицию. Это операция O(n). Если у вас миллион элементов, это будет миллион операций копирования. Больно.

LinkedList: вставка — король, но доступ — изгой

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

public class LinkedListDemo {
    public static void main(String[] args) {
        List<String> linkedList = new LinkedList<>();
        
        // Добавление в конец — быстро (O(1))
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            linkedList.add("Element " + i);
        }
        long end = System.nanoTime();
        System.out.println("LinkedList add (в конец): " + (end - start) / 1e6 + " ms");
        
        // Доступ по индексу — медленно (O(n))
        start = System.nanoTime();
        String element = linkedList.get(50000);
        end = System.nanoTime();
        System.out.println("LinkedList get: " + (end - start) / 1e6 + " ms");
        
        // Вставка в середину — быстро (O(1) после поиска позиции)
        start = System.nanoTime();
        // ВНИМАНИЕ: сам метод add(index, element) всё равно делает поиск (O(n))
        linkedList.add(25000, "INSERTED");
        end = System.nanoTime();
        System.out.println("LinkedList insert (середина): " + (end - start) / 1e6 + " ms");
    }
}

Заметили подвох? Да, вставка в LinkedList формально O(1), но только если у вас уже есть ссылка на узел. Метод add(index, element) сначала проходит по списку до нужного индекса (O(n)), а потом вставляет. Поэтому на больших списках выигрыш может быть не таким очевидным.

Когда использовать LinkedList (реальные сценарии)

Итак, давайте разберём ситуации, где LinkedList действительно выигрывает.

1. Частые вставки и удаления в начале списка

Это классический случай. Если вы пишете очередь, стек или буфер, где элементы постоянно добавляются и удаляются с начала, LinkedList — ваш выбор.

// LinkedList как очередь (FIFO)
LinkedList<Task> taskQueue = new LinkedList<>();
taskQueue.addLast(new Task("Задача 1")); // O(1)
taskQueue.addLast(new Task("Задача 2")); // O(1)
Task nextTask = taskQueue.removeFirst(); // O(1)

Для ArrayList удаление первого элемента — это O(n), потому что все остальные элементы сдвигаются. Разница колоссальная.

2. Когда размер списка неизвестен и часто меняется

LinkedList не требует перераспределения памяти. Каждый новый узел выделяется отдельно. ArrayList же периодически создаёт новый массив большего размера и копирует все элементы. Если вы добавляете миллионы элементов, эти копирования могут стать узким местом.

3. Итерация с удалением элементов

Если вам нужно пройти по списку и удалить некоторые элементы, LinkedList работает эффективнее через Iterator.remove().

LinkedList<Integer> numbers = new LinkedList<>();
// ... заполнение списка ...

Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
    Integer num = iterator.next();
    if (num % 2 == 0) { // удаляем чётные
        iterator.remove(); // O(1) для LinkedList
    }
}

Для ArrayList удаление через итератор всё равно вызывает сдвиг элементов (O(n)).

Когда ArrayList — бесспорный победитель

Честно говоря, в 90% случаев ArrayList будет лучшим выбором. Вот почему.

1. Доступ по индексу — мгновенный

Если вы часто обращаетесь к элементам по индексу (а в реальных проектах это происходит постоянно), ArrayList даёт O(1). LinkedList — O(n). Для списка из 100 000 элементов разница будет в 100 000 раз.

2. Экономия памяти

ArrayList хранит только данные. LinkedList хранит для каждого элемента два дополнительных указателя (на предыдущий и следующий узел) + сам объект узла. Это примерно в 2-3 раза больше памяти.