Зачем в реализации LinkedList в Java хранятся ссылки на первый (head) и последний (tail) элемент?

Хранение ссылок на оба конца списка (head и tail) — это оптимизация для выполнения операций добавления и удаления в начало и конец списка за константное время O(1).

Почему это важно:

• Добавление в конец (addLast(E e), offer(E e)): Без ссылки tail пришлось бы проходить от head через все элементы, что заняло бы O(n). С tail операция выполняется мгновенно.
• Добавление в начало (addFirst(E e)): Аналогично, ссылка head позволяет сделать это за O(1).
• Удаление с конца (removeLast()): Хотя для двусвязного списка (как LinkedList в Java) это также O(1), наличие tail критически важно для эффективного доступа к последнему элементу.

Практический пример и следствия:

LinkedList<String> deque = new LinkedList<>();
// Эффективные операции с обоих концов благодаря head и tail
deque.addFirst("Front"); // O(1)
deque.addLast("Rear");  // O(1)
String first = deque.pollFirst(); // O(1)
String last = deque.pollLast();   // O(1)

Эта оптимизация делает LinkedList идеальной основой для реализации таких структур данных, как:

• Очередь (FIFO): addLast() + removeFirst().
• Стек (LIFO): addFirst() + removeFirst().
• Двусторонняя очередь (Deque): все операции с концов.