Insertion and Deletion at Positions

Inserting after a known node p: the new node takes p.next, and then p.next points to the new node. Deleting the successor of p: p.next = p.next.next.

Without a predecessor, one must search from head. This makes deletion in the middle $O(n)$.

Error source: the order of assignments. If p.next is overwritten too early, the old successor chain is lost.

Example: List A-B-C. Inserting X after A results in A-X-B-C.

Detect a cycle: Linked List Cycle [1].

Where used

When the position is already available as a node reference, inserting and deleting are $O(1)$ pointer updates. This is exactly why hash tables and caches use linked buckets. Without reference, the search remains $O(n)$; in this case, ArrayList wins for random access.

Depth

For a change at position i, a singly linked structure usually requires the predecessor. Inserting first connects the new node to the previous successor and then connects the predecessor to the new node. This order maintains accessibility.

The actual pointer change is local, but finding the position costs a linear number of steps. A known node reference can therefore allow for a constant update, while the same operation over an index remains linear.

Head position and empty lists are special cases because no predecessor exists. A sentinel node can unify these cases, but it adds an internal node that should not appear as a usable value.

Difficulty levels

1. Correctly reorder pointers for insertion and deletion.
2. Separate search costs from modification costs.
3. Use a sentinel node to simplify edge cases.

Pitfalls

If the predecessor is first redirected during insertion without securing the old successor, the rest of the list may become unreachable. Additionally, when dealing with positions, boundaries between node and gap indices must be observed.