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.
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.
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
