Где быстрее выполнится операция получения элемента по индексу: в ArrayList или LinkedList?

Где быстрее: ArrayList или LinkedList при получении элемента по индексу

Ответ: ArrayList значительно быстрее. Различие в производительности огромное — в среднем 1000+ раз быстрее на больших коллекциях.

Причина: структура данных

Эти две коллекции используют совершенно разные структуры данных, которые влияют на время доступа.

ArrayList: массив (O(1) доступ)

public class ArrayList<E> {
    private Object[] elementData;  // Обычный массив
    private int size;
    
    @Override
    public E get(int index) {
        // Прямой доступ по адресу — O(1)
        return (E) elementData[index];
    }
}

// Использование
List<Integer> list = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
int element = list.get(3);  // O(1): 40
// elementData[3] = 40 (прямой доступ за одну операцию)

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

Массив в памяти: [10] [20] [30] [40] [50]
Индекс:           0    1    2    3    4

Адрес памяти:
  Base address: 0x1000
  Element[0]:   0x1000
  Element[1]:   0x1000 + 4 bytes
  Element[2]:   0x1000 + 8 bytes
  Element[3]:   0x1000 + 12 bytes  <- Прямой доступ!
  Element[4]:   0x1000 + 16 bytes

get(3) = Base + (3 * elementSize) = одна операция!

LinkedList: цепь узлов (O(n) доступ)

public class LinkedList<E> {
    private Node<E> first;  // Первый узел
    private Node<E> last;   // Последний узел
    private int size;
    
    private static class Node<E> {
        E item;
        Node<E> next;  // Указатель на следующий
        Node<E> prev;  // Указатель на предыдущий
    }
    
    @Override
    public E get(int index) {
        // Нужно пройти по цепи — O(n)
        return getNode(index).item;
    }
    
    private Node<E> getNode(int index) {
        // Начинаем с начала и идём по цепи
        if (index < size >> 1) {  // Оптимизация: если ближе к началу
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;  // Переходим к следующему узлу
            return x;
        } else {  // Если ближе к концу
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;  // Переходим к предыдущему узлу
            return x;
        }
    }
}

// Использование
List<Integer> list = new LinkedList<>(Arrays.asList(10, 20, 30, 40, 50));
int element = list.get(3);  // O(n): нужно пройти 3 узла!

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

Цепь узлов в памяти:       Разные адреса!
  [10|next]──> [20|next]──> [30|next]──> [40|next]──> [50|next]

get(3):
  1. Start at first: [10|next]
  2. Follow: x = first.next  → [20|next]
  3. Follow: x = x.next      → [30|next]
  4. Follow: x = x.next      → [40|next]  <- Нашли!

Чтобы получить элемент [3], нужно N операций следования!

Сложность времени выполнения

*Может быть O(1) амортизированно если не нужно расширять массив
**Если добавляем в конец, O(n) если где-то в середине
***Плюс O(n) для поиска нужного узла

Бенчмарк: реальные цифры

public class CollectionBenchmark {
    public static void main(String[] args) {
        int size = 100_000;
        int iterations = 1_000_000;
        
        // ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        
        long start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            arrayList.get(50_000);  // Получаем элемент из середины
        }
        long arrayListTime = System.nanoTime() - start;
        
        // LinkedList
        List<Integer> linkedList = new LinkedList<>(arrayList);
        
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            linkedList.get(50_000);  // Получаем элемент из середины
        }
        long linkedListTime = System.nanoTime() - start;
        
        System.out.println("ArrayList:  " + arrayListTime + " ns");
        System.out.println("LinkedList: " + linkedListTime + " ns");
        System.out.println("Ratio: " + (linkedListTime / (double) arrayListTime) + "x");
    }
}

// Примерный вывод:
// ArrayList:  50_000_000 ns
// LinkedList: 45_000_000_000 ns
// Ratio: 900x

Детальный анализ

ArrayList get(50_000) из 100_000 элементов

Элемент находится на половине массива.

Операции:
1. Вычисление адреса: address = baseAddress + (index * elementSize)
2. Доступ в памяь: load value from memory

Время: ~10-50 наносекунд (зависит от CPU и кеша)

Это ОЧЕНЬ быстро потому что:
- CPU кеширует эту операцию
- Компилятор может оптимизировать
- JVM может использовать процессорные инструкции

LinkedList get(50_000) из 100_000 элементов

Нужно пройти половину цепи:

Операции:
1. Start at first node
2. Loop 50,000 times:
   3. Load next pointer from current node
   4. Follow to next node
   5. Check if we reached target

Время: ~45 миллисекунд

Это МЕДЛЕННО потому что:
- 50,000 итераций цикла
- Узлы разбросаны по памяти (плохая локальность кеша)
- CPU не может предсказать доступ к памяти
- Много инструкций CPU за операцию

Визуализация разницы

GET операция в цикле 1,000,000 раз:

ArrayList (O(1)):
█▄▄▄▄ (0.05 сек)

LinkedList (O(n)):
████████████████████████████████ (45 сек)

Разница: 900x медленнее!

Когда использовать каждую коллекцию

ArrayList лучше для:

// 1. Частый доступ по индексу
List<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));  // ArrayList в 1000x раз быстрее
}

// 2. Итерация
for (String name : names) {  // for-each это get() внутри
    process(name);
}

// 3. Поиск элемента
if (names.contains("Alice")) {  // O(n) в обоих, но ArrayList скорее найдёт
    // ...
}

LinkedList лучше для:

// 1. Частое добавление/удаление с начало и конца
Queue<Task> queue = new LinkedList<>();
queue.add(task);        // O(1) — добавить в конец
task = queue.poll();    // O(1) — удалить с начала

// 2. Использование как Deque
Deque<String> deque = new LinkedList<>();
deque.addFirst("first");   // O(1)
deque.addLast("last");     // O(1)

// 3. Очень редкий случай: частое добавление/удаление в СЕРЕДИНУ
// (на практике это редко используется)

Оптимизация LinkedList

Заметьте, что LinkedList имеет оптимизацию:

private Node<E> getNode(int index) {
    if (index < size >> 1) {  // Если ближе к началу
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {  // Если ближе к концу
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // Идём с конца
        return x;
    }
}

// Пример:
LinkedList<Integer> list = new LinkedList<>(1 до 100_000);

list.get(10);         // Идём с начала: 10 операций
list.get(99_990);     // Идём с конца: 10 операций
list.get(50_000);     // Идём с начала: 50_000 операций

Это немного помогает, но не кардинально.

Итоговый ответ

ArrayList в 1000+ раз быстрее LinkedList при получении элемента по индексу.

Причины:

• ArrayList использует прямой доступ O(1) по адресу памяти
• LinkedList требует прохождения цепи O(n) с множественными операциями
• На 100,000 элементов: ArrayList ~10 наносекунд, LinkedList ~1 миллисекунду

Рекомендация: Используй ArrayList как коллекцию по умолчанию, LinkedList только если нужно часто добавлять/удалять с начала или конца.