Linked Lists
Linked Lists: Types & Problem Solving
A Linked List is a linear data structure, but unlike arrays, its elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. While less common than dynamic arrays in competitive programming (due to cache performance and lack of random access), they are a foundational concept.
Anatomy of a Linked List
A linked list consists of nodes where each node contains:
- A data field.
- A reference (or pointer) to the next node in the sequence.
The first node is called the HEAD. The last node's pointer points to NULL, indicating the end of the list.
Types of Linked Lists
- Singly Linked List: Traversal is forward-only. Each node has a pointer to the next node.
- Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows for forward and backward traversal.
- Circular Linked List: The last node's pointer points back to the first node instead of NULL, forming a circle.
Basic Operations
- Traversal: Accessing each element of the list.
- Insertion: Adding a new node. This can be at the beginning, end, or a specific position. It's an O(1) operation if inserting at the head, and O(n) otherwise for a singly linked list.
- Deletion: Removing a node. Like insertion, complexity varies based on the position.
- Search: Finding a node with a given value. This is an O(n) operation.
Linked Lists vs. Arrays
| Feature | Array | Linked List |
|---|---|---|
| Size | Fixed (or Amortized for Dynamic) | Dynamic |
| Memory | Contiguous | Non-contiguous (can cause cache misses) |
| Insertion/Deletion | Expensive (O(n)) | Efficient (O(1) if at head/tail) |
| Random Access | O(1) | O(n) |
Common Problems
- Reverse a Linked List.
- Detect a cycle in a Linked List (Floyd's Cycle-Finding Algorithm).
- Merge two sorted Linked Lists.
- Find the middle of a Linked List (fast and slow pointer approach).
Interactive Demo
To see these operations in action, check out the interactive simulation below. Notice how adding or removing from the head is instant (O(1)), while operations at the tail require traversing the whole list (O(n)), visually demonstrating the trade-offs compared to arrays.
Interactive Linked List Simulation
Click the buttons below to see linked list operations in action and their time complexities.
List is empty