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

Скорость доступа к последнему значению в LinkedList

Время доступа к последнему элементу в LinkedList - это один из важных вопросов при выборе между структурами данных. Ответ зависит от того, как реализована LinkedList в Java.

Времяннаяная сложность

// ТЕОРИЯ: LinkedList.get(lastIndex)
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

// Доступ к последнему элементу
String last = list.get(list.size() - 1); // O(n) - МЕДЛЕННО!

// Это эквивалентно:
String last = list.get(2); // get(2) требует проход через все элементы

Почему O(n)?

// LinkedList - это двусвязный список (doubly-linked list)
public class LinkedListStructure {
    private class Node {
        E item;
        Node next;
        Node prev; // Двусвязный список имеет prev
    }
    
    private Node first;  // Ссылка на первый узел
    private Node last;   // Ссылка на последний узел
    private int size;
}

// Однако, при вызове get(index):
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

private Node node(int index) {
    // Оптимизация: начинаем со стороны, которая ближе
    if (index < (size >> 1)) {  // index < size/2
        Node x = first;          // Начинаем с начала
        for (int i = 0; i < index; i++)
            x = x.next;          // Проходим шаг за шагом - O(index)
        return x;
    } else {
        Node x = last;           // Начинаем с конца
        for (int i = size - 1; i > index; i--)
            x = x.prev;          // Проходим назад - O(size - index)
        return x;
    }
}

// Для ПОСЛЕДНЕГО элемента (index = size-1):
// - Если size = 10 и index = 9
// - index > (size >> 1) => 9 > 5 => true
// - Начинаем с last и проходим 0 шагов (i = 9, условие i > 9 false)
// - РЕЗУЛЬТАТ: O(1) - БЫСТРО!

На практике: получение последнего элемента

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

// СПОСОБ 1: Использование get() с последним индексом
long start = System.nanoTime();
Integer last = list.get(list.size() - 1);
long duration1 = System.nanoTime() - start;
System.out.println("get(size-1): " + duration1 + " ns"); // ~100-200 ns (O(1))

// СПОСОБ 2: Использование getLast() - специальный метод
start = System.nanoTime();
Integer last2 = list.getLast();
long duration2 = System.nanoTime() - start;
System.out.println("getLast(): " + duration2 + " ns"); // ~50 ns (O(1))

// СПОСОБ 3: Использование peek() - из Deque интерфейса
start = System.nanoTime();
Integer last3 = list.peekLast();
long duration3 = System.nanoTime() - start;
System.out.println("peekLast(): " + duration3 + " ns"); // ~50 ns (O(1))

// СПОСОБ 4: Использование stream (МЕДЛЕННО!)
start = System.nanoTime();
Optional<Integer> last4 = list.stream().reduce((a, b) -> b);
long duration4 = System.nanoTime() - start;
System.out.println("stream: " + duration4 + " ns"); // ~1,000,000 ns (O(n))

Сравнение разных индексов

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

// Тестирование доступа к разным позициям
int[] indices = {0, 100, 500, 5000, 9999};

for (int idx : indices) {
    long start = System.nanoTime();
    Integer value = list.get(idx);
    long duration = System.nanoTime() - start;
    System.out.printf("get(%d): %d ns%n", idx, duration);
}

// Результат (примерный):
// get(0):     10 ns (начало, минимум)
// get(100):   100 ns
// get(500):   300 ns
// get(5000):  150 ns (оптимизация: начинаем с конца)
// get(9999):  10 ns (конец, практически минимум)

Оптимальные методы доступа

LinkedList<String> list = new LinkedList<>();
list.add("first");
list.add("middle");
list.add("last");

// РЕКОМЕНДУЕМЫЕ способы (все O(1)):

// 1. getLast() - явный метод
String last = list.getLast(); // O(1)

// 2. peekLast() - из Deque (более безопасно, возвращает null если пусто)
String last = list.peekLast(); // O(1)

// 3. getFirst() для первого
String first = list.getFirst(); // O(1)

// 4. peekFirst() для первого
String first = list.peekFirst(); // O(1)

// НЕ РЕКОМЕНДУЕМЫЕ способы для конца:

// get(size()-1) - работает, но неинтуитивно
String last = list.get(list.size() - 1); // O(1) в конце, но может быть O(n) в начале

// stream().findLast() - ОЧЕНЬ МЕДЛЕННО
String last = list.stream()
    .reduce((a, b) -> b)
    .orElse(null); // O(n) - НЕ ИСПОЛЬЗУЙ!

Сравнение с ArrayList

// ArrayList - случайный доступ O(1) ВСЕГДА
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10_000; i++) {
    arrayList.add(i);
}

long start = System.nanoTime();
Integer last = arrayList.get(9999);
long arrayDuration = System.nanoTime() - start;
System.out.println("ArrayList.get(last): " + arrayDuration + " ns"); // ~10 ns (O(1))

// LinkedList - последний элемент O(1), но тоже ~10 ns
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10_000; i++) {
    linkedList.add(i);
}

start = System.nanoTime();
last = linkedList.getLast();
long linkedDuration = System.nanoTime() - start;
System.out.println("LinkedList.getLast(): " + linkedDuration + " ns"); // ~10 ns (O(1))

// Но для ПЕРВОГО элемента в ArrayList vs LinkedList ОЧЕНЬ отличается
start = System.nanoTime();
last = arrayList.get(0);
long arrayFirstDuration = System.nanoTime() - start;
System.out.println("ArrayList.get(0): " + arrayFirstDuration + " ns"); // ~10 ns (O(1))

start = System.nanoTime();
last = linkedList.getFirst();
long linkedFirstDuration = System.nanoTime() - start;
System.out.println("LinkedList.getFirst(): " + linkedFirstDuration + " ns"); // ~10 ns (O(1))

// Для СЕРЕДИНЫ:
int mid = 5000;
start = System.nanoTime();
last = arrayList.get(mid);
arrayDuration = System.nanoTime() - start;
System.out.println("ArrayList.get(mid): " + arrayDuration + " ns"); // ~10 ns (O(1))

start = System.nanoTime();
last = linkedList.get(mid);
linkedDuration = System.nanoTime() - start;
System.out.println("LinkedList.get(mid): " + linkedDuration + " ns"); // ~5000 ns (O(n))

Таблица сравнения операций

Операция              | ArrayList | LinkedList
---------------------|-----------|------------
get(first)           | O(1)      | O(1)
get(last)            | O(1)      | O(1)
get(middle)          | O(1)      | O(n)
add(first)           | O(n)      | O(1)
add(last)            | O(1)      | O(1)
add(middle)          | O(n)      | O(n)
remove(first)        | O(n)      | O(1)
remove(last)         | O(1)      | O(1)
remove(middle)       | O(n)      | O(n)
iterator             | O(1)      | O(1)
reverse iteration    | O(1)      | O(1)

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

// ХОРОШО для LinkedList:
LinkedList<Task> queue = new LinkedList<>();
queue.addFirst(highPriorityTask);  // O(1)
queue.addLast(lowPriorityTask);    // O(1)
Task next = queue.removeFirst();   // O(1)

// Очередь (FIFO): LinkedList эффективнее ArrayList
Queue<String> tasks = new LinkedList<>();
tasks.offer("task1");     // add O(1)
String task = tasks.poll(); // remove O(1)

// Стек (LIFO): LinkedList эффективнее ArrayList для push/pop в начало
Deque<String> stack = new LinkedList<>();
stack.push("item1");        // addFirst O(1)
String item = stack.pop();  // removeFirst O(1)

// ПЛОХО для LinkedList:
// - Random access в середину: list.get(i) O(n)
// - Необходим индексный доступ
for (int i = 0; i < list.size(); i++) {
    String item = list.get(i); // Избегай! Это O(n) для каждого элемента!
    // Результат: O(n²)
}

// ПРАВИЛЬНО:
for (String item : list) { // Iterator использует next() O(1)
    // Это O(n)
}

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

Скорость доступа к последнему элементу LinkedList: O(1)

Это возможно благодаря:

1. Оптимизации в методе node() - начинаем со стороны, которая ближе (с конца для последнего элемента)
2. Двусвязной структуре - есть ссылка last на последний узел
3. Специальным методам - getLast(), peekLast() работают за O(1)

Однако для произвольного индекса в середине это O(n). Используй LinkedList для операций с началом/концом, а ArrayList для случайного доступа.