Какая временная сложность операции доступа по индексу в LinkedList?

Временная сложность доступа по индексу в LinkedList

Временная сложность операции доступа по индексу в LinkedList составляет O(n), где n — размер списка. Это одна из основных причин, почему ArrayList предпочтителен для операций случайного доступа.

Почему O(n)?

LinkedList хранит элементы в виде цепочки связанных узлов. Для доступа к элементу по индексу нужно пройти от начала (или конца) списка, переходя от одного узла к другому через ссылки.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // Если индекс ближе к началу, начинаем с head
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // Переходим к следующему узлу
        return x;
    } else {
        // Если индекс ближе к концу, начинаем с tail
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // Переходим к предыдущему узлу
        return x;
    }
}

Практический пример

LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1000; i++) {
    list.add(i);
}

// Доступ к элементу с индексом 0: O(1) — это first
int first = list.get(0);  // Находится сразу

// Доступ к элементу с индексом 500: O(500)
int middle = list.get(500);  // Нужно пройти через 500 узлов

// Доступ к элементу с индексом 999: O(1) — это last
int last = list.get(999);  // LinkedList оптимизирует, начиная с конца

Сравнение с ArrayList

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 1000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// ArrayList: get() это O(1) — прямой доступ к массиву
int val = arrayList.get(500);  // Мгновенно

// LinkedList: get() это O(n) — нужно обойти узлы
int val = linkedList.get(500);  // Проходит через 500 узлов

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

Java реализует небольшую оптимизацию: если индекс ближе к концу списка, начинает с конца:

LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 100; i++) {
    list.add("item " + i);
}

// Начинает с head (индекс < 50)
list.get(10);   // O(10) операций

// Начинает с tail (индекс >= 50)
list.get(99);   // O(1) операция (это last)
list.get(98);   // O(2) операции
list.get(90);   // O(10) операций

Временная сложность других операций LinkedList

LinkedList<E> list = new LinkedList<>();

list.add(element);              // O(1) — добавление в конец
list.addFirst(element);         // O(1) — добавление в начало
list.addLast(element);          // O(1) — добавление в конец
list.add(index, element);       // O(n) — вставка в произвольное место
list.get(index);                // O(n) — доступ по индексу
list.set(index, element);       // O(n) — замена по индексу
list.remove(index);             // O(n) — удаление по индексу
list.removeFirst();             // O(1) — удаление с начала
list.removeLast();              // O(1) — удаление с конца
list.contains(element);         // O(n) — поиск элемента

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

// Хорошо для LinkedList:
LinkedList<Task> queue = new LinkedList<>();
queue.addFirst(task);       // O(1)
Task first = queue.removeFirst();  // O(1)

// Плохо для LinkedList:
for (int i = 0; i < list.size(); i++) {
    list.get(i);            // O(n²) общая сложность!
}

// Хорошо для LinkedList (итерация):
for (Integer num : list) {  // O(n)
    System.out.println(num);
}

Почему ArrayList лучше для доступа по индексу

public E get(int index) {
    // ArrayList: прямой доступ к элементу массива за O(1)
    return elementData[index];  // Математический расчёт адреса памяти
}

Вывод

• LinkedList.get(index) — O(n) в худшем случае
• ArrayList.get(index) — O(1) всегда
• Если часто нужен доступ по индексу — используй ArrayList
• Если часто добавляют/удаляют в начало/конец — используй LinkedList
• Для итерации оба работают одинаково хорошо через foreach