Singly Linked List and Nodes

In a singly linked list, each node has a value and a reference next to its successor. The list head head points to the first node; the end has next == null.

Inserting at the beginning is $O(1)$: the new node points to the old head, and the head is updated. Searching for the k-th element is O(k) because it must be traversed from the front.

Example: head -> [A] -> [B] -> null. After inserting C at the beginning: head -> [C] -> [A] -> [B] -> null.

Edge case: empty list (head == null) and one-element list must be handled separately when deleting.

Reverse the pointers: Reverse Linked List [1].

Where used

Basic form for hash chaining, adjacency lists, undo chains, and many lock-free structures. Rarely used as a public API in the JDK, but constantly used internally and in system code. Understanding pointer logic applies to graphs and trees.

Depth

A singly linked structure consists of nodes with useful values and references to their successors. The invariant requires that exactly the contained nodes are reachable from the head and that the chain ultimately ends at null.

Appending at the beginning of the list only changes one reference and is independent of the list length. Accessing position i, on the other hand, requires following i references. The structure trades direct index access for local structural changes.

Node identity and stored value are different. Two nodes can have the same values yet possess different positions and successors. This distinction is important for deleting, splitting, and merging.

Difficulty levels

1. Draw nodes and references of a short list.
2. Analyze head insertion and linear positional access.
3. Formulate reachability as a representation invariant.

Pitfalls

When replacing the head, the old chain is lost if the old head is not stored as a successor beforehand. Value equality should also not be confused with node identity.