You manipulate a linked list by changing or following references between nodes. In a singly linked list, each node stores data and a reference to the next node, while head refers to the first node.
| Operation | Mechanism | Typical time complexity |
|---|---|---|
| Insert at head | Set new.next to head, then set head to new | |
| Insert after a known node | Set new.next to current.next, then set current.next to new | |
| Delete the head | Set to |
headhead.next| Delete another node | Find its predecessor, then set previous.next to current.next | if searching is required |
| Traverse | Follow each next reference until null |
| Search | Traverse while comparing each node's data with the target |
The order of reference updates matters during insertion. If current.next is overwritten before it is saved in new.next, the remainder of the list may become inaccessible.
A traversal can be expressed as:
current = head
while current != null
process(current.data)
current = current.next
end while
A linear search uses the same structure but stops when current.data equals the target. It returns the node or its position; if null is reached, the target is absent.
For deletion, maintain both previous and current. When the target is found, assign previous.next = current.next. The head requires a separate case because it has no predecessor. An empty list must also be checked before accessing head.next.
A common misconception is that linked lists provide constant-time access to any position. They do not: unlike arrays, linked lists require sequential traversal, so accessing the node at a specified index is .
For a trace or pseudocode question, show every reference update in the correct order and handle the empty-list and head cases. When asked to compare structures, explain that linked lists support efficient insertion or deletion at a known node but require linear-time traversal and searching.