Linked List
A linear data structure where elements (nodes) are stored in non-contiguous memory locations and connected using pointers.
Types of Linked Lists
Each node contains data and a pointer to the next node, forming a one-way chain.
Key idea: Can move only forward.
Each node has two pointers—one to the next node and one to the previous—allowing movement in both directions.
Key idea: Can move forward and backward.
The last node points back to the first node, forming a loop instead of ending with null.
Key idea: No end—forms a circle.
Traversal
Time Complexity: O(n). Must visit each node sequentially starting from the head.
Access
Time Complexity: O(n). To access an element at index 'i', you must traverse 'i' nodes from the head.
Insertion
Find insertion point (after node 10).
Deletion
Find the node before the one to delete (node 10).
Search
Time Complexity: O(n). Must check each node sequentially from the head.
Time Complexity
| Operation | Time Complexity | Notes |
|---|---|---|
| Access | O(n) | Requires traversal from head |
| Search | O(n) | Requires traversal from head |
| Traversal | O(n) | Visit all nodes |
| Insertion | O(1) / O(n) | O(1) for head, O(n) otherwise |
| Deletion | O(1) / O(n) | O(1) for head, O(n) otherwise |
When to Use Linked Lists
- When you need efficient insertions and deletions (O(1)) at the beginning or end (with a tail pointer), without reallocating or shifting elements.
- For data that can grow or shrink dynamically, where you don't know the size beforehand.
- When memory is fragmented, as nodes can be stored anywhere in memory, unlike the contiguous requirement for arrays.
- Implementing other data structures like stacks and queues.