B4.1.2 · Abstract data types (ADTs)
Linked lists
By the end you can
Construct and trace singly and doubly linked lists with dynamic node pointers, head references, insertion, and deletion.
While traditional arrays allocate a single contiguous block of memory, a is a dynamic collection composed of independent scattered across heap memory, stitched together by pointers.
The anatomy of a linked list#
In a singly linked list, each node is an object containing two fields:
- Data field: Holds the stored value (e.g. an integer, string, or student object).
- Next pointer: Holds the memory reference (address) of the successor node in the sequence.
The list maintains an external pointer called head that points to the first node. The final node’s next pointer is set to null, signifying the end of the list.
Linked list with 3 nodes. Each node contains data and a pointer to the next node.
Insertion and deletion mechanics#
- Inserting at Head ($O(1)$): Create a new node, point its
nextto the currenthead, then updateheadto point to the new node. Takes constant time because no existing nodes need to be shifted! - Deleting a node ($O(n)$): Traverse until the predecessor node is found. Set
curr.next = curr.next.next, bypassing the target node. The abandoned node is subsequently collected by automatic garbage collection. - Doubly Linked Lists: Each node carries two pointers:
nextandprev. This allows bidirectional traversal (stepping backwards from tail to head), useful for browser history and music playlists, but requires 50% more pointer memory per node.
Check yourself
Linked lists
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 9 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare a singly linked list and a static array in terms of memory layout, resizing flexibility, insertion at the head, and element access by index.
[4]Compare: Similarities and differences, about both things, point by point.
2.Distinguish between a singly linked list and a doubly linked list in terms of pointer references and traversal capabilities.
[2]Distinguish: Make the differences between two things clear.
3.Construct the pointer reassignment steps in pseudocode to insert a new node at the head of a singly linked list.
[3]Construct: Draw or write it out (a table, a diagram, a program).
In a nutshell
- A linked list is a dynamic linear data structure composed of nodes linked by memory pointers.
- Each node stores user data and a pointer reference to the next node; the final node points to null.
- Inserting or deleting at the head of a linked list takes O(1) constant time, avoiding expensive array shifting.
- Doubly linked lists store both next and prev pointers, enabling bidirectional traversal with slightly higher memory overhead.