Односвязный список

Одна ссылка определяет направление

В односвязном списке каждый узел знает только о следующем узле. Из head можно двигаться вперёд по next, но вернуться к предыдущему узлу напрямую нельзя — такой ссылки просто нет.

Это делает структуру компактной и хорошо подходящей для операций у начала списка. Например, добавление нового первого элемента не требует прохода по существующим узлам.

Добавление в начало

Node added = new Node(5);
added.next = head;
head = added;

Сначала новый узел начинает указывать на старую голову, затем сам становится новой головой. Обе операции выполняются за O(1) независимо от длины списка. Порядок присваиваний важен: если сначала потерять ссылку на старый head, оставшаяся цепочка станет недоступной через список.

Удаление первого узла

Удаление с начала устроено ещё проще: достаточно перенести head на второй узел.

if (head != null) {
    head = head.next;
}

После этого старый первый узел больше не достижим из списка. Если на него нет других ссылок, Java сможет освободить занятую им память во время сборки мусора.

Цена движения только вперёд

Получить последний элемент или элемент с известным номером без дополнительной ссылки нельзя мгновенно: нужно пройти цепочку от головы. Удалить узел по его значению тоже обычно означает сначала найти его и помнить предыдущий узел, чтобы соединить цепочку после удаления.