Singly Linked List

One reference defines the direction

In a singly linked list, each node knows only about the next node. Starting from head, we can move forward through next, but we cannot directly return to the previous node because no such reference exists.

This keeps the structure compact and makes it well suited to operations at the beginning of the list. For example, adding a new first element does not require traversing the existing nodes.

Adding at the beginning

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

First, the new node points to the old head, and then it becomes the new head itself. Both operations take O(1) regardless of the list length. The assignment order matters: if we lose the reference to the old head first, the remaining chain becomes unreachable through the list.

Removing the first node

Removing from the beginning is even simpler: move head to the second node.

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

After that, the old first node is no longer reachable from the list. If no other references point to it, Java can reclaim its memory during garbage collection.

The cost of moving only forward

Getting the last element or an element at a known position cannot be done instantly without an additional reference: we must traverse the chain from the head. Removing a node by value also usually means first finding it and remembering the previous node so the chain can be reconnected after removal.