Constructing and Applying Linked Lists: Singly, Doubly, and Circular (HL Only)
Singly Linked Lists
A singly linked list is a collection of nodes, where each node contains:
- Data: The value or information stored in the node.
- Pointer: A reference to the next node in the sequence.
Note
The head is the first node in the list, and the tail is the last node, which points to null, indicating the end of the list.
Common Mistake
- Forgetting to update the head pointer when inserting or deleting at the beginning.
- Thinking insertion at the end is always O(1): it’s O(n) unless a tail pointer is maintained.
- Losing access to the rest of the list when deleting a node (not updating pointers correctly).
- Confusing traversal with direct access (linked lists don’t support O(1) random access like arrays).
Operations on a Singly Linked List
- Insertion
- At the Beginning: O(1) time complexity.
- At the End: O(n) time complexity, unless a tail pointer is maintained, which allows O(1) insertion.
- Deletion
- Head Node: O(1) time complexity.
- Other Nodes: O(n) time complexity, as it requires finding the preceding node.
- Traversal
- Visiting all nodes from head to tail: O(n) time complexity.
- Search
- Finding a node by value: O(n) time complexity in the worst case.
Tip
When inserting at the end of a singly linked list, maintaining a tail pointer can significantly improve efficiency by reducing the time complexity from O(n) to O(1).
Doubly Linked Lists
A doubly linked list extends the functionality of a singly linked list by allowing each node to have references to both the next and previous nodes.
Characteristics of a Doubly Linked List
- Bidirectional Traversal: Nodes have pointers to both the next and previous nodes.
- Head and Tail: The head's previous pointer and the tail's next pointer are null, indicating the boundaries of the list.
Operations on a Doubly Linked List
- Insertion
- At the Beginning or End: O(1) time complexity.
- Between Nodes: O(1) if the position is known, otherwise, O(n) due to traversal.
- Deletion
- Head or Tail: O(1) time complexity.
- Middle Nodes: O(1) if the node is known, otherwise, O(n) to find the node.
- Traversal
- Forward and Backward: O(n) time complexity.
- Search
- O(n) time complexity in the worst case.
Common Mistake
- Forgetting to update both pointers (next and previous) when inserting or deleting a node.
- Assuming deletion is always O(1): it’s only O(1) if the node reference is already known.
- Not recognising the extra memory overhead of storing two pointers per node.
- Forgetting that the head’s prev and the tail’s next must be null.
Note
Doubly linked lists are particularly useful when you need to traverse the list in both directions or perform frequent insertions and deletions at both ends.
Circular Linked Lists
- A circular linked list is a variation where the last node points back to the first node, forming a loop.
- This structure can be implemented as either a singly or doubly linked list.
Characteristics of a Circular Linked List
- Circular Structure: The last node's next pointer points to the head, creating a loop.
- Variations: Can be singly or doubly linked.
Operations on a Circular Linked List
- Insertion
- Before the Head: O(1) time complexity.
- After the Tail: O(1) time complexity.
- Between Nodes: O(1) if the position is known, otherwise, O(n) due to traversal.
- Deletion
- Head or Tail: O(1) time complexity with proper pointer adjustments.
- Middle Nodes: O(1) if the node is known, otherwise, O(n) to find the node.
- Traversal
- O(n) time complexity, stopping when the head is reached again.
- Search
- O(n) time complexity in the worst case.
Common Mistake
- Forgetting to re-point the last node to the head after insertion/deletion.
- Accidentally creating an infinite loop during traversal by not checking for return to the head.
- Assuming circular lists automatically improve performance: complexity is still O(n) for traversal and search.
- Confusing circular singly and circular doubly lists (both exist, but operations differ slightly).
Note
Circular linked lists are ideal for applications requiring cyclic traversals, such as round-robin scheduling.
Comparing Linked List Types
| Type | Advantages | Disadvantages | Typical use case |
|---|---|---|---|
| Singly Linked | Simple structure, efficient insertions/deletions at the head | No backward traversal, O(n) insertion/deletion at the tail without a tail pointer | Implementing basic stacks. Dynamic memory where only forward traversal is needed |
| Doubly Linked | Bidirectional traversal, efficient insertions/deletions at both ends | Higher memory overhead due to additional pointers | Deques (double-ended queues). Navigation systems (e.g., back/forward buttons in browsers) |
| Circular Linked | Continuous traversal, efficient for cyclic operations | More complex pointer management | Round-robin scheduling (CPU tasks) - Multiplayer games (cycling turns). Buffer management |
Common Mistake
General exam mistakes across all lists:
- Mixing up Big-O complexities (e.g., saying search in a linked list is O(1) instead of O(n)).
- Describing linked lists like arrays (forgetting they use pointers/references, not indices).
- Forgetting to explain why linked lists are better than arrays in certain cases (dynamic size, O(1) insertion/deletion if node known).
- Drawing diagrams without clearly updating pointers (a common cause of lost marks).
Self review
- What are the key differences between singly, doubly, and circular linked lists?
- How does maintaining a tail pointer improve the efficiency of certain operations?
- In what scenarios would you choose a circular linked list over a doubly linked list?
