Chapter 11: DSA Linked Lists
DSA Linked Lists – Let’s understand this topic like I’m sitting next to you in the library, explaining slowly, clearly, with lots of real-life analogies, drawings in words, multiple examples, code in different styles, common mistakes, and most importantly — when and why you should use linked lists instead of arrays.
What is a Linked List?
A Linked List is a linear data structure where elements (called nodes) are not stored in contiguous memory locations like arrays.
Instead, each node contains:
- The actual data (the value you want to store)
- A reference (or pointer/link) to the next node in the sequence
So the elements are linked together like a chain.
Real-life analogy everyone understands
Imagine a train with many compartments:
- Each compartment = one node
- Each compartment has passengers (the data)
- Each compartment has a coupling that connects it to the next compartment (the next pointer)
- The engine is the starting point (head of the list)
- There is no fixed number of compartments — you can add or remove anytime
- Compartments are not fixed in one place — they can be anywhere on the track (non-contiguous memory)
That’s exactly how a linked list works.
Types of Linked Lists (you should know all three)
| Type | Next Pointer | Previous Pointer | Most Common Use / Interview Focus |
|---|---|---|---|
| Singly Linked List | Yes | No | ★★★★★ (most basic & most asked) |
| Doubly Linked List | Yes | Yes | ★★★★☆ (very common) |
| Circular Linked List | Yes (last → first) | Varies | ★★★☆☆ (special cases) |
Most interviews start with Singly → then move to Doubly
Structure of a Node
Visual representation of a Singly Linked List node:
|
0 1 2 3 4 5 6 7 |
[ Data | next ] → [ Data | next ] → [ Data | next ] → null 10 ↓ 25 ↓ 7 ↓ |
Each box is a node. next is the address/pointer to the next node. Last node’s next = null (or None in Python)
Creating a Singly Linked List – Step by Step
Let’s build this list: 10 → 25 → 7 → 42
- Create first node (head): data = 10, next = null
- Create second node: data = 25, next = null
- Connect first to second: head.next = second node
- Create third node: data = 7
- Connect second to third
- Create fourth node: data = 42
- Connect third to fourth
- Fourth node’s next remains null
Now the list is: 10 → 25 → 7 → 42 → null
Code – Singly Linked List in Python (very clean & interview style)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
# Step 1: Define the Node class class Node: def __init__(self, data): self.data = data self.next = None # Step 2: Define the LinkedList class (optional but good practice) class LinkedList: def __init__(self): self.head = None # Insert at the beginning def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # Insert at the end def insert_at_end(self, data): new_node = Node(data) if not self.head: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node # Print the list def print_list(self): temp = self.head while temp: print(temp.data, end=" → ") temp = temp.next print("null") # Usage example ll = LinkedList() ll.insert_at_beginning(7) ll.insert_at_beginning(25) ll.insert_at_beginning(10) ll.insert_at_end(42) ll.insert_at_end(99) ll.print_list() # Output: 10 → 25 → 7 → 42 → 99 → null |
Most Important Operations & Their Time Complexity
| Operation | Singly Linked List | Doubly Linked List | Array (for comparison) |
|---|---|---|---|
| Access by index | O(n) | O(n) | O(1) |
| Insert at beginning | O(1) | O(1) | O(n) |
| Insert at end (with tail) | O(1) | O(1) | O(1) amortized |
| Insert in middle (after given node) | O(1) | O(1) | O(n) |
| Delete at beginning | O(1) | O(1) | O(n) |
| Delete at end | O(n) | O(1) (with tail) | O(1) |
| Delete by value / position | O(n) | O(n) | O(n) |
| Search | O(n) | O(n) | O(n) |
Key takeaway:
- Linked lists are excellent when you do many insertions/deletions at the beginning or at known positions
- Arrays are excellent when you need fast random access by index
Very Common Interview Questions on Linked Lists
| Level | Question examples |
|---|---|
| Easy | Print linked list, Find length, Search element |
| Easy | Insert at beginning / end / position |
| Medium | Delete node by value, Delete without head pointer |
| Medium | Reverse a linked list (iterative + recursive) |
| Medium | Find middle of linked list (two-pointer method) |
| Medium | Detect cycle in linked list (Floyd’s cycle detection) |
| Medium | Remove duplicates from sorted / unsorted list |
| Hard | Merge two sorted linked lists |
| Hard | Reverse in groups of k |
| Hard | Find intersection point of two linked lists |
| Hard | Clone linked list with random pointers |
Doubly Linked List – Quick Visual & Difference
|
0 1 2 3 4 5 6 |
null ← [prev | 10 | next] ↔ [prev | 25 | next] ↔ [prev | 7 | next] → null |
Advantages over singly:
- Can traverse backward
- Delete a node in O(1) if you have direct pointer to it
- Easier to insert/delete in middle if you have pointer
Disadvantages:
- Uses more memory (extra prev pointer)
- Slightly more complex code
Summary – Linked List Cheat Sheet
| Feature | Linked List | Array |
|---|---|---|
| Memory allocation | Non-contiguous | Contiguous |
| Size | Dynamic | Fixed (or amortized) |
| Access by index | O(n) | O(1) |
| Insert/Delete at beginning | O(1) | O(n) |
| Insert/Delete at end | O(n) or O(1) with tail | O(1) amortized |
| Random access | Slow | Fast |
| Cache performance | Poor | Excellent |
| Most used when | Frequent insert/delete, unknown size | Fast access, known size |
Most important sentence for interviews:
Use linked list when you need frequent insertions/deletions in the middle or beginning, and you don’t need random access by index. Use array / vector / list when you need fast access by position.
Would you like to continue with any specific linked list topic next?
Very popular next steps:
- How to reverse a linked list (iterative + recursive)
- Detect cycle (Floyd’s tortoise & hare)
- Find middle of linked list in one pass
- Merge two sorted linked lists
- Delete node without head pointer (very tricky interview question)
- Difference between array vs linked list in depth
Just tell me which one you want — I’ll explain it in the same detailed, human-teacher style! 😄
