Чем отличается ArrayList от LinkedList в Java и когда что выбирать?

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

ArrayList

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

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

LinkedList

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

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

Когда что выбирать

• ArrayList: Используйте, когда требуется частый доступ к элементам по индексу и операции добавления/удаления в середине списка редки. Пример: реализация списка студентов, где часто требуется доступ по индексу.

• LinkedList: Используйте, когда требуется частое добавление и удаление элементов, особенно в середине списка, и доступ по индексу не является частой операцией. Пример: реализация очереди задач, где элементы часто добавляются и удаляются.

Пример кода

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
​
public class ListExample {
    public static void main(String[] args) {
        // Создание ArrayList
        List<String> arrayList = new ArrayList<>();
        arrayList.add("A"); // Добавление элемента в конец
        arrayList.add("B");
        arrayList.add("C");
        System.out.println("ArrayList: " + arrayList);
​
        // Доступ по индексу
        String element = arrayList.get(1); // Получение элемента по индексу 1
        System.out.println("Element at index 1 in ArrayList: " + element);
​
        // Создание LinkedList
        List<String> linkedList = new LinkedList<>();
        linkedList.add("X"); // Добавление элемента в конец
        linkedList.add("Y");
        linkedList.add("Z");
        System.out.println("LinkedList: " + linkedList);
​
        // Добавление элемента в начало
        linkedList.add(0, "W");
        System.out.println("LinkedList after adding 'W' at index 0: " + linkedList);
    }
}

• ArrayList<String> arrayList = new ArrayList<>(); — создается экземпляр ArrayList, который будет хранить строки.
• arrayList.add("A"); — добавление элемента "A" в конец ArrayList.
• arrayList.get(1); — получение элемента по индексу 1 из ArrayList.
• LinkedList<String> linkedList = new LinkedList<>(); — создается экземпляр LinkedList, который будет хранить строки.
• linkedList.add(0, "W"); — добавление элемента "W" в начало LinkedList.

Этот код демонстрирует основные операции с ArrayList и LinkedList, показывая их различия в добавлении и доступе к элементам.