You add an element by creating a node and updating references, remove one by redirecting references around its node, and traverse the list by following references from the first node until the end. These operations allow a dynamic list to change size during program execution.
A dynamic linked list consists of nodes. Each node stores data and a reference to the next node; the list maintains a head reference to its first node. A null reference indicates the end.
| Operation | Core mechanism | Typical time complexity |
|---|---|---|
| Add at the head | Set the new node's next reference to head, then make head reference the new node | |
| Add after a known node | Link the new node to the following node, then link the known node to the new node | |
| Remove the head | Set head to the second node | |
| Remove another node | Find its predecessor, then redirect the predecessor's reference past the removed node | if searching is required |
| Traverse | Visit each node by repeatedly following its next reference |
For example, insertion at the head can be represented as:
newNode = Node(value)
newNode.next = head
head = newNode
To remove the node after current:
IF current.next ≠ null THEN
current.next = current.next.next
END IF
Traversal uses a temporary reference so that head is not changed:
current = head
WHILE current ≠ null
OUTPUT current.data
current = current.next
END WHILE
A common misconception is that linked-list elements occupy consecutive memory locations. They do not: references connect nodes that may be stored separately. Another error is updating references in the wrong order, which can make the remaining list inaccessible.
For an IB B2.2 response, trace each reference update precisely and handle edge cases such as an empty list, removal of the head, or a missing target. If asked to compare structures, explain that linked lists support dynamic resizing but do not provide the direct indexed access associated with arrays.
