Chapter 13: DSA Linked Lists Types
DSA Linked Lists Types – Let’s understand this topic like I’m your senior sitting next to you in the hostel, explaining everything clearly, slowly, with real examples, memory visuals, code snippets, and most importantly — when to use which type in real interviews and projects.
There are mainly three fundamental types of linked lists that you must know very well:
- Singly Linked List
- Doubly Linked List
- Circular Linked List
And then there are some special / hybrid variations that appear frequently in interviews:
- Circular Singly Linked List
- Circular Doubly Linked List
- Skip List (advanced, sometimes asked in top companies)
- Self-adjusting list, XOR linked list, etc. (rare but good to know conceptually)
Let’s go through them one by one in detail.
1. Singly Linked List (Most Basic & Most Asked)
Structure:
Each node has:
- data (the value)
- next (pointer/reference to next node)
Last node’s next = null / None
Visual in memory:
|
0 1 2 3 4 5 6 |
head ──→ [10 | →] ──→ [25 | →] ──→ [7 | →] ──→ [42 | →] ──→ null |
Operations & Time Complexity:
| Operation | Time Complexity | Comment |
|---|---|---|
| Access by index | O(n) | Must traverse from head |
| Insert at beginning | O(1) | Very fast |
| Insert at end | O(n) or O(1)* | O(1) if you maintain tail pointer |
| Insert after given node | O(1) | If you already have pointer to node |
| Delete at beginning | O(1) | Change head |
| Delete at end | O(n) | Need to find second last node |
| Delete by value / position | O(n) | Need to traverse |
| Search | O(n) |
*O(1) insert at end if you keep a tail pointer (very common in good implementations)
When to use Singly Linked List
- You mostly do operations at the beginning (push front, pop front)
- Memory is a concern (uses less space than doubly)
- Most basic interview questions (reverse, middle, cycle detection, merge, etc.)
- You don’t need backward traversal
Real interview example questions:
- Reverse a linked list
- Find middle of linked list (fast & slow pointer)
- Detect cycle (Floyd’s cycle detection)
- Merge two sorted linked lists
- Remove nth node from end
2. Doubly Linked List
Structure:
Each node has:
- data
- next (pointer to next node)
- prev (pointer to previous node)
First node’s prev = null Last node’s next = null
Visual:
|
0 1 2 3 4 5 6 7 |
null ← [null | 10 | →] ↔ [← | 25 | →] ↔ [← | 7 | →] ↔ [← | 42 | null] → null ↑head |
Operations & Time Complexity:
| Operation | Time Complexity | Comment |
|---|---|---|
| Access by index | O(n) | |
| Insert at beginning | O(1) | |
| Insert at end | O(1) | (if tail pointer is maintained) |
| Insert before/after node | O(1) | Very convenient |
| Delete any node | O(1) | If you have direct pointer to the node |
| Delete at beginning/end | O(1) | |
| Backward traversal | Easy & fast | Can go prev ← prev ← prev |
Big advantages over singly:
- Deleting a node is O(1) if you already have pointer to it (very important!)
- Can traverse backward easily
- Easier to implement LRU Cache, browser history (back & forward)
Disadvantages:
- Uses more memory (extra prev pointer per node)
- More pointers to maintain → more chance of bugs
Very common real-world uses:
- Browser history (back & forward buttons)
- Undo/redo functionality in editors
- LRU Cache implementation
- Music playlist (previous & next song)
3. Circular Linked List
Two main flavors:
- Circular Singly Linked List
- Circular Doubly Linked List
Most common in interviews → Circular Singly
Structure (Circular Singly):
Last node’s next points back to head instead of null.
|
0 1 2 3 4 5 6 7 8 |
┌────────────────────────────────────┐ │ │ head ──→ [10 | →] ──→ [25 | →] ──→ [7 | →] ──→ [42 | ──┘ |
Visual (Circular Doubly):
|
0 1 2 3 4 5 6 7 8 9 |
┌─────────────────────────────────────────────┐ ↓ │ null ← [← | 10 | →] ↔ [← | 25 | →] ↔ [← | 7 | →] ↔ [← | 42 | →] ──┐ └────────────────────────────────────────────────────────────┘ |
Special properties:
- There is no real end — you can keep going forever if you don’t stop
- Very useful to represent circular buffers, round-robin scheduling, Josephus problem
Common interview questions:
- Check if linked list is circular
- Find start of cycle (very famous Floyd’s cycle question variation)
- Split circular list into two halves
- Josephus problem (people standing in circle, every kth is eliminated)
Quick Comparison Table (must remember)
| Feature / Operation | Singly Linked List | Doubly Linked List | Circular (Singly) |
|---|---|---|---|
| Extra memory per node | 1 pointer | 2 pointers | 1 pointer |
| Insert at beginning | O(1) | O(1) | O(1) |
| Insert at end (without tail) | O(n) | O(n) | O(n) |
| Insert at end (with tail) | O(1) | O(1) | O(1) |
| Delete node (with pointer given) | O(n) | O(1) | O(n) |
| Backward traversal | Not possible | Easy | Not possible |
| Has defined end? | Yes (null) | Yes (null) | No |
| Common cycle detection question? | Yes | Yes | Very common |
Quick Summary – Which type when?
| You want… | Best choice |
|---|---|
| Simplest code + least memory | Singly |
| Fast delete given a node pointer | Doubly |
| Browser back/forward, LRU Cache | Doubly |
| Round-robin, circular buffer, Josephus | Circular |
| Most interview questions (90%+) | Singly first, then Doubly |
| Stability + backward movement needed | Doubly |
Bonus – Very Frequently Asked Variations
These appear in top company interviews:
- XOR Linked List (memory efficient doubly linked list using XOR)
- Skip List (probabilistic data structure — like linked list + fast search)
- Self-adjusting list (move-to-front, transpose heuristics)
But for most students → master these three deeply first.
Would you like to go deep into any particular type next?
Popular choices:
- Singly Linked List — all important operations with code
- Doubly Linked List implementation (very common for LRU)
- Detect cycle & find starting point (Floyd’s algorithm)
- Reverse linked list (iterative + recursive)
- Merge two sorted linked lists
- Circular linked list problems (Josephus, split, etc.)
Just tell me which one you want — I’ll explain with the same level of detail and examples! 😄
