Почему LinkedlList хранит ссылки на первый и последний элемент?

Почему LinkedList хранит ссылки на first и last?

Отличный вопрос, который показывает понимание структур данных. Ответ касается оптимизации производительности и показывает, как небольшой выбор дизайна может кардинально изменить сложность алгоритмов.

Краткий ответ

LinkedList хранит ссылки на first (голова) и last (хвост) потому что это позволяет выполнять операции в конце списка за O(1) вместо O(n).

// Вот как устроен LinkedList в Java
public class LinkedList<E> extends AbstractSequentialList<E> {
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        // Двусвязный список
    }
    
    transient int size = 0;
    transient Node<E> first;  // Ссылка на первый элемент
    transient Node<E> last;   // Ссылка на последний элемент
}

Проблема без ссылки на last

Представь LinkedList, который знает только о first:

// Плохой дизайн: только first
public class BadLinkedList<E> {
    private Node<E> first;
    
    public void add(E element) {
        // Чтобы добавить в конец, нужно дойти до последнего элемента
        if (first == null) {
            first = new Node<>(element);
            return;
        }
        
        Node<E> current = first;
        while (current.next != null) {  // Проходим весь список!
            current = current.next;
        }
        current.next = new Node<>(element); // O(n) операция!
    }
}

// Проблема: каждое добавление в конец требует O(n) времени
BadLinkedList<Integer> list = new BadLinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i); // i-я итерация требует i операций! O(n²) всего!
}
// Это будет работать ОЧЕНЬ медленно!

Решение: ссылка на last

// Хороший дизайн: first И last
public class GoodLinkedList<E> {
    private Node<E> first;
    private Node<E> last;  // Прямой доступ к концу!
    
    public void add(E element) {
        Node<E> newNode = new Node<>(element);
        
        if (last == null) {
            // Пустой список
            first = last = newNode;
        } else {
            // Добавляем в конец — O(1)!
            last.next = newNode;
            newNode.prev = last;
            last = newNode;
        }
    }
}

// Результат: каждое добавление O(1), всего O(n)
GoodLinkedList<Integer> list = new GoodLinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i); // Всегда O(1), независимо от размера!
}
// Это будет очень быстро!

Сравнение сложности

Реальный пример производительности

import java.util.*;

public class LinkedListPerformance {
    public static void main(String[] args) {
        int n = 100_000;
        
        // Используем реальный LinkedList
        LinkedList<Integer> list = new LinkedList<>();
        
        // Добавление в конец — быстро (O(1) каждый раз)
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        long timeAdd = System.nanoTime() - start;
        System.out.println("Добавление в конец: " + (timeAdd / 1_000_000) + " мс");
        // Результат: ~50 мс для 100k элементов
        
        // Добавление в начало — тоже быстро благодаря first
        start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            list.addFirst(i);
        }
        long timeAddFirst = System.nanoTime() - start;
        System.out.println("Добавление в начало: " + (timeAddFirst / 1_000_000) + " мс");
        // Результат: ~50 мс для 100k элементов (благодаря first!)
        
        // Удаление из конца — быстро
        start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            list.removeLast();
        }
        long timeRemove = System.nanoTime() - start;
        System.out.println("Удаление из конца: " + (timeRemove / 1_000_000) + " мс");
        // Результат: ~20 мс (благодаря last!)
    }
}

Двусвязный список (doubly-linked list)

Вот полная реализация Java LinkedList:

public class LinkedList<E> {
    private static class Node<E> {
        E item;
        Node<E> next;   // Ссылка на следующий
        Node<E> prev;   // Ссылка на предыдущий (важно для двусвязности!)
        
        Node(E element, Node<E> next, Node<E> prev) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    transient Node<E> first;  // Голова списка
    transient Node<E> last;   // Хвост списка
    
    // Добавление в конец — быстро
    public void add(E e) {
        linkLast(e);
    }
    
    private void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(e, null, l); // O(1)!
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }
    
    // Удаление из конца — быстро
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l); // O(1)!
    }
    
    private E unlinkLast(Node<E> l) {
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null;
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        return element;
    }
}

Почему именно LinkedList это делает?

1. Оптимизация для операций в конце

LinkedList часто используется как Queue (очередь) или Stack (стек):

// Queue: добавляем в конец, удаляем из начала
Queue<Integer> queue = new LinkedList<>();
queue.add(1);      // O(1) благодаря last!
queue.add(2);      // O(1)
queue.poll();      // O(1) благодаря first!

// Deque: добавляем/удаляем с обоих концов
Deque<Integer> deque = new LinkedList<>();
deque.addLast(1);   // O(1)
deque.addFirst(2);  // O(1)
deque.removeLast(); // O(1) благодаря last!

2. Минимальные затраты памяти

// first и last — это всего две ссылки (16 байт на 64-битной JVM)
// Это очень мало по сравнению с преимуществами производительности
private Node<E> first;  // 8 байт
private Node<E> last;   // 8 байт
// Всего: 16 байт!

Практическое применение

// Очередь задач (Queue)
public class TaskQueue {
    private Queue<Task> tasks = new LinkedList<>();
    
    public void enqueue(Task task) {
        tasks.add(task); // O(1) благодаря last
    }
    
    public Task dequeue() {
        return tasks.poll(); // O(1) благодаря first
    }
}

// Двусторонняя очередь (Deque)
public class Browser {
    private Deque<String> history = new LinkedList<>();
    
    public void visitPage(String url) {
        history.addLast(url); // O(1)
    }
    
    public String goBack() {
        return history.removeLast(); // O(1) благодаря last!
    }
    
    public String goForward() {
        return history.removeFirst(); // O(1) благодаря first!
    }
}

Сравнение со структурами без last

// Singly-linked list без last
class SimpleLinkList<E> {
    private Node<E> first;
    // При добавлении в конец нужно O(n) операций
}

// Doubly-linked list с last (Java LinkedList)
class ProperLinkedList<E> {
    private Node<E> first;
    private Node<E> last;  // Операции в конце — O(1)!
}

Итог

LinkedList хранит ссылки на first и last потому что:

1. Производительность — операции в начале и конце становятся O(1) вместо O(n)
2. Природное использование — LinkedList часто используется как Queue/Deque, где нужны быстрые операции с обоих концов
3. Минимальные затраты — всего 16 байт памяти для огромного прироста производительности
4. Правильный дизайн — это хороший пример того, как небольшой выбор архитектуры может спасти программу от O(n²) сложности

Это хороший пример проектирования структур данных с учётом использования!