COMP5112 Chap.4 Linked Lists and Pointer Updates
Linked Lists and Pointer Updates
Local changes require global reachability
Linked lists store nodes through references instead of contiguous positions. The chapter traces search, insertion and removal in doubly and singly linked representations, with special attention to update order, head and tail cases and dummy nodes.
Complexity claims name whether the target node is already supplied, because local rewiring is constant time only after any required linear search has finished.
A node combines a data value with one or more references. In a singly linked list, following next from head must eventually visit every stored node and finish at the empty reference.
A doubly linked list adds previous links and often keeps tail, enabling movement in both directions. These advantages cost storage and additional invariants: whenever x.next is y, the backward link y.previous should return to x, except at defined boundaries.
Insertion order matters because an early assignment can destroy the only route to the remainder.
When inserting between left and right, first connect the new node to both neighbours, then redirect the neighbours toward it. Draw the old edge before writing assignments and cross it out only when replacement routes exist. In a singly linked list, preserving the successor reference is especially important because there is no backward link that can recover a lost suffix.
Removal reconnects neighbours around the target.
For a doubly linked interior node, left.next becomes right and right.previous becomes left. Head or tail removal additionally changes an external reference, and a one-node list changes both. The detached node must no longer be reachable from the list.
Language-specific storage release is separate from the abstract algorithm, but clearing stale links can make the postcondition easier to inspect in a trace.
Complexity depends on what the operation receives. Given a direct reference to a node and, where needed, its predecessor, a fixed number of link assignments is constant time. Finding the node by key or position still requires traversal and can take linear time.
A doubly linked representation may start from the nearer endpoint when size and position are known, but it does not provide constant-time arbitrary indexing like an array.
Boundary design can simplify code. Dummy head and tail nodes ensure that every data insertion occurs between existing nodes, reducing separate empty and endpoint cases.
A circular sentinel can represent emptiness when its next and previous links return to itself. Sentinels do not eliminate invariants: they must never be returned as data or detached accidentally, and the size field must specify whether it counts only real nodes.
Audit a finished update by traversing forward from head and backward from tail.
The sequences should contain the same data nodes in reverse order, without cycles unless the representation intentionally uses a sentinel cycle. Check that head has no data predecessor, tail has no data successor, size changed exactly once, and a failed operation changed nothing. These checks expose self-loops, lost suffixes, ghost references and inconsistent endpoints.
What this chapter covers
- 01
Doubly linked structure
- 02
Forward and backward reachability
- 03
Search by key
- 04
Insertion update order
- 05
Removal update order
- 06
Head, tail and sentinel cases
Worked example · free
Insert without losing a neighbour
- 2Save both neighbour references.
- 3Connect fresh to the neighbours.
- 3Redirect both neighbour links.
Key terms
- Node
- A stored item together with one or more link references.
- Head
- The external reference to the first list position.
- Tail
- The external reference to the final list position.
- Sentinel Node
- A dummy boundary node used to reduce special cases.
Linked Lists and Pointer Updates FAQ
Is linked-list insertion always constant time?
Only when the insertion position and necessary neighbour references are already known. Searching from head for a key or position adds linear time before the fixed local rewiring begins.
Why can update order break an otherwise correct idea?
Assigning a link overwrites the old route. If the node needed later was not saved, it can become unreachable before the remaining assignments use it to finish reconnection.
How do I test pointer pseudocode?
Use an empty list, one node, two nodes and a middle case. Mark the first assignment that breaks head or tail reachability or leaves forward and backward links mutually inconsistent.
Exam move
For every update, write the neighbourhood before and after, then traverse it in both directions. Practise finding the smallest counterexample to faulty pseudocode. Rotate through empty, one-node, endpoint and interior cases, listing assignments in execution order. Track head, tail and size separately from node links.
After each exercise, state whether locating the target was included in the complexity and identify the first assignment that would lose reachability if the order were changed.
Working through Linked Lists and Pointer Updates in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Linked Lists and Pointer Updates question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
