Chapter 14: DSA Linked Lists Operations
DSA Linked List Operations – Let’s go through this topic thoroughly, like I’m teaching you face-to-face with a whiteboard, writing code step-by-step, showing memory changes, and explaining why each operation has the time complexity it has.
We will focus mainly on Singly Linked List operations (the most common in interviews), and I’ll mention differences for Doubly Linked List where they matter significantly.
Most Important Linked List Operations (in order of frequency in interviews)
- Traversal / Print
- Find length / size
- Insert at beginning
- Insert at end
- Insert after a given node / at a position
- Delete from beginning
- Delete from end
- Delete a given node (by value or by reference)
- Search for a value
- Reverse a linked list
- Find middle node
- Detect cycle (very famous)
Let’s go one by one with clear explanation, visual memory change, code, and time complexity.
1. Traversal / Print the list
What we do: Start from head and keep moving to next until we reach null.
|
0 1 2 3 4 5 6 7 8 9 10 11 |
def print_list(head): current = head while current is not None: print(current.data, end=" → ") current = current.next print("null") |
Time Complexity: O(n) Space Complexity: O(1)
2. Find length / size of linked list
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
def get_length(head): count = 0 current = head while current: count += 1 current = current.next return count |
Time: O(n) Used very often as a helper function.
3. Insert at Beginning (very fast & very common)
Memory change (new node becomes new head):
Before: head → [10] → [25] → [7] → null
After insert 99: head → [99] → [10] → [25] → [7] → null
|
0 1 2 3 4 5 6 7 8 9 10 |
def insert_at_beginning(head, data): new_node = Node(data) new_node.next = head head = new_node # important: update head return head # return new head |
Time: O(1) Very important: This is one of the biggest advantages of linked list over array.
4. Insert at End
Two versions:
Version A: Without tail pointer → O(n)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def insert_at_end(head, data): new_node = Node(data) if head is None: return new_node current = head while current.next is not None: current = current.next current.next = new_node return head |
Version B: With tail pointer → O(1) (recommended in good implementations)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class LinkedList: def __init__(self): self.head = None self.tail = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = new_node |
Time: O(1) with tail, O(n) without
5. Insert after a given node (or at position k)
Very common interview question
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Insert after a given node (we already have pointer to prev_node) def insert_after(prev_node, data): if prev_node is None: print("Previous node cannot be None") return new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node |
Time: O(1) (if we already have pointer to the node after which we want to insert)
Insert at position k (1-based):
|
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 |
def insert_at_position(head, data, position): if position < 1: return head new_node = Node(data) if position == 1: new_node.next = head return new_node current = head count = 1 while current and count < position - 1: current = current.next count += 1 if current is None: return head # position out of range new_node.next = current.next current.next = new_node return head |
Time: O(position) → worst case O(n)
6. Delete from Beginning
|
0 1 2 3 4 5 6 7 8 9 |
def delete_first(head): if head is None: return None return head.next # just move head forward |
Time: O(1)
7. Delete from End
Without tail → O(n)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def delete_last(head): if head is None or head.next is None: return None current = head while current.next.next is not None: current = current.next current.next = None return head |
With tail → still O(n) unless you keep second-last pointer (rare)
Time: O(n) in singly linked list
8. Delete a node by value
Two famous versions:
A. Normal delete by value
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def delete_by_value(head, key): if head is None: return None # If head itself is the node to delete if head.data == key: return head.next current = head while current.next and current.next.data != key: current = current.next if current.next is None: return head # not found current.next = current.next.next return head |
B. Delete without head pointer (very famous tricky question)
You are given only pointer to the node to be deleted (not head).
Trick: copy next node’s data to current and delete next node.
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
def delete_node_without_head(node): if node is None or node.next is None: # Cannot delete last node this way (special handling needed) return node.data = node.next.data node.next = node.next.next |
Time: O(1)
9. Search for a value
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def search(head, key): current = head position = 1 while current: if current.data == key: return position current = current.next position += 1 return -1 |
Time: O(n)
Quick Summary Table – Singly Linked List Operations
| Operation | Time Complexity | Very Important? |
|---|---|---|
| Insert at beginning | O(1) | ★★★★★ |
| Insert at end (with tail) | O(1) | ★★★★ |
| Insert after given node | O(1) | ★★★★ |
| Delete from beginning | O(1) | ★★★★ |
| Delete from end | O(n) | ★★★ |
| Delete given node (with ptr) | O(1) | ★★★★★ (tricky version) |
| Search / traversal | O(n) | ★★★★★ |
| Reverse | O(n) | ★★★★★ |
| Find middle | O(n) | ★★★★★ |
| Detect cycle | O(n) | ★★★★★ |
Would you like to go deeper into any of these operations with full code + dry run?
Most requested next topics:
- Reverse a linked list (iterative + recursive)
- Find middle of linked list (fast & slow pointer)
- Detect & remove cycle
- Merge two sorted linked lists
- Reverse in groups of k (hard but very asked)
- Doubly linked list important operations
Just tell me which one you want next — I’ll explain with the same level of detail, visuals, and examples! 😊
