В чем разница между ArrayList и LinkedList?

Основные различия между ArrayList и LinkedList в Java

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

Внутренняя структура данных

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

// Внутренняя реализация ArrayList (упрощенно)
transient Object[] elementData; // Хранение элементов в массиве

При добавлении элементов, когда массив заполняется, создается новый массив большего размера (обычно в 1.5 раза) и копируются все элементы.

LinkedList реализован как двусвязный список:

// Внутренняя структура узла LinkedList
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    // конструктор и методы
}

Каждый элемент хранится в отдельном узле, который содержит ссылки на предыдущий и следующий узлы.

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

1. Доступ по индексу (get/set)

• ArrayList: O(1) — постоянное время, так как используется прямое обращение к элементу массива

// Быстрый доступ в ArrayList
public E get(int index) {
    rangeCheck(index);
    return elementData(index); // Простое обращение к массиву
}

• LinkedList: O(n) — линейное время, так как нужно пройти по цепочке ссылок от начала или конца списка

// Медленный доступ в LinkedList (требуется итерация)
public E get(int index) {
    checkElementIndex(index);
    return node(index).item; // Требуется поиск узла
}

2. Вставка и удаление в середине списка

• ArrayList: O(n) — требуется сдвиг всех последующих элементов

// Вставка в ArrayList может быть медленной
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

• LinkedList: O(1) — если есть ссылка на узел,只需要 изменить ссылки соседних узлов

// Быстрая вставка в LinkedList при известном узле
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
}

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

• ArrayList: O(1) амортизированное время — если не требуется расширение массива
• LinkedList: O(1) — всегда постоянное время

Практические рекомендации по выбору

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

• Частые операции чтения по индексу
• Минимальные вставки/удаления в середине списка
• Предсказуемый размер коллекции
• Требуется меньший расход памяти (только для данных, без хранения ссылок)

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

• Частые вставки/удаления в начале или середине списка
• Реализация очереди или стека (хотя лучше использовать ArrayDeque)
• Итерация с одновременной модификацией через ListIterator
• Когда важнее предсказуемое время вставки, чем время доступа

Потребление памяти

• ArrayList: хранит только данные в непрерывном блоке памяти, более эффективно использует кэш процессора
• LinkedList: для каждого элемента требуется дополнительная память для хранения двух ссылок (next и prev), плюс overhead на объект Node

Особенности использования в многопоточности

Обе реализации не являются потокобезопасными. Для работы в многопоточной среде необходимо использовать:

• Collections.synchronizedList()
• CopyOnWriteArrayList (для частого чтения и редкой записи)
• ConcurrentLinkedQueue (для linked-структур)

Пример сравнения на практике

public class ListComparison {
    public static void main(String[] args) {
        // Тест доступа по индексу
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        // Заполняем обе коллекции
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        
        // ArrayList будет значительно быстрее
        long start = System.nanoTime();
        arrayList.get(50000);
        long arrayTime = System.nanoTime() - start;
        
        // LinkedList будет медленнее
        start = System.nanoTime();
        linkedList.get(50000);
        long linkedTime = System.nanoTime() - start;
        
        System.out.println("ArrayList access time: " + arrayTime + " ns");
        System.out.println("LinkedList access time: " + linkedTime + " ns");
    }
}

В автоматизированном тестировании понимание этих различий особенно важно при:

• Тестировании производительности приложений
• Оптимизации тестовых сценариев, работающих с коллекциями
• Анализе сложности алгоритмов в тестируемом коде
• Выборе подходящих структур данных для тестовых утилит и фреймворков

Для большинства случаев ArrayList является предпочтительным выбором из-за лучшей локальности данных и эффективности операций чтения, которые встречаются чаще, чем операции вставки/удаления в середине коллекции.