Lesson 2 � Beginner-Intermediate

Insert, Delete, Reverse

Linked list banana toh seekh liya, ab uspe operations karna seekho. Insert karna � beginning, end, ya beech mein. Delete karna � kisi bhi jagah se. Reverse karna � poori list ko. Ye teen operations linked list ki real power hain.

? 25 min✓ Beginner-Intermediate✓ Linked Lists Basics

Insert at Beginning (Head)

Sabse easy operation � naya node shuru mein lagao. Bas naya node banao, uska next current head ko point karo, aur head ko naye node pe update karo. Done!

WHAT

Naya node linked list ke beginning mein add hota hai. Current head se pehle naya node aa jaata hai. Time complexity O(1) hai � constant time, chahe list kitni bhi badi ho.

WHEN

Stack implement karna ho (LIFO � last in, first out), ya jab frequently beginning mein insert karna ho. Arrays mein ye O(n) hota hai but linked list mein O(1).

WHERE

Stack implementation, undo functionality, playlist mein naya song shuru mein add karna, browser history mein naya page.

# Insert at beginning � O(1) time
def insert_at_head(head, data):
 new_node = Node(data)
 new_node.next = head # Naya node purane head ko point kare
 return new_node # Naya node ab head hai

# Example
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
# List: 10 ? 20 ? 30 ✓ None

head = insert_at_head(head, 5)
# List: 5 ? 10 ? 20 ? 30 ✓ None

Key Insight: Insert at head mein sirf 2 assignments hain � new_node.next = head aur head = new_node. Isliye ye O(1) hai. Arrays mein ye impossible hai kyunki sab elements shift karne padte hain.

Insert at End (Tail)

End mein insert karna thoda tricky hai kyunki tumhe last node tak jaana padega. Agar tail pointer hai toh O(1) ho jaata hai, warna O(n) traversal lagega.

# Insert at end � O(n) without tail pointer, O(1) with tail pointer
def insert_at_tail(head, data):
 new_node = Node(data)
 
 # Agar list empty hai
 if head is None:
 return new_node
 
 # Last node tak jao
 current = head
 while current.next is not None:
 current = current.next
 
 # Last node ka next naye node ko point kare
 current.next = new_node
 return head

# Example
head = Node(10)
head.next = Node(20)

head = insert_at_tail(head, 30)
# List: 10 ? 20 ? 30 ✓ None

# Optimized version � tail pointer use karke O(1)
class LinkedList:
 def __init__(self):
 self.head = None
 self.tail = None # Tail pointer rakhna
 
 def insert_at_tail(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 # Tail update karo

Insert at Position

Kisi specific position pe insert karna � jaise 3rd position pe naya node lagao. Ye thoda complex hai kyunki tumhe us position ke pehle tak jaana padega.

# Insert at given position � O(n) time
def insert_at_position(head, data, position):
 if position == 0: # Beginning pe insert
 return insert_at_head(head, data)
 
 new_node = Node(data)
 current = head
 
 # Position-1 tak traverse karo
 for i in range(position - 1):
 if current is None:
 return head # Position valid nahi hai
 current = current.next
 
 if current is None:
 return head # Position valid nahi hai
 
 # Insert karo
 new_node.next = current.next
 current.next = new_node
 return head

# Example: 2nd position pe 15 insert karo
# Before: 10 ? 20 ? 30 ✓ None
head = insert_at_position(head, 15, 2)
# After: 10 ? 20 ? 15 ? 30 ✓ None

Visual:
Position 2 pe insert karna hai [15]:
10 ? 20 ? 30 ✓ None
current = 20 (position 1 tak gaye)
new_node.next = current.next (15 ? 30)
current.next = new_node (20 ? 15)
Result: 10 ? 20 ? 15 ? 30 ✓ None

Delete Operations

Linked list se node delete karna � beginning se, end se, ya kisi specific value se. Delete mein special dhyan rakhna padta hai kyunki pointers carefully handle karne hote hain.

# Delete from beginning � O(1)
def delete_from_head(head):
 if head is None:
 return None
 return head.next # Head agla node ban jayega

# Delete from end � O(n)
def delete_from_tail(head):
 if head is None:
 return None
 if head.next is None: # Sirf ek node hai
 return None
 
 # Second last node tak jao
 current = head
 while current.next.next is not None:
 current = current.next
 
 current.next = None # Last node hata do
 return head

# Delete by value � O(n)
def delete_by_value(head, value):
 if head is None:
 return None
 
 # Agar head hi delete karna hai
 if head.data == value:
 return head.next
 
 current = head
 while current.next is not None:
 if current.next.data == value:
 current.next = current.next.next # Node skip karo
 return head
 current = current.next
 
 return head # Value nahi mili

# Example
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

head = delete_by_value(head, 20)
# List: 10 ? 30 ✓ None

Deletion ka Pattern: Hamesha "previous" node ka pointer change karo. Current node ka pointer change mat karo � usse pehle wale ka next change karo taaki current node skip ho jaye. Ye pattern yaad rakho � interview mein bahut kaam aayega.

Reverse Linked List

Linked list ko reverse karna � sabse popular interview question! Ye pointer manipulation ka best example hai. Do approaches hain � iterative aur recursive.

# Iterative approach � O(n) time, O(1) space
def reverse_iterative(head):
 prev = None
 current = head
 
 while current is not None:
 next_node = current.next # Agla node save karo
 current.next = prev # Pointer reverse karo
 prev = current # Prev aage badho
 current = next_node # Current aage badho
 
 return prev # Prev ab naya head hai

# Step by step visualization:
# Start: None ? 10 20 ? 30 ✓ None
# prev curr
# Step 1: None ? 10 ? 20 30 ✓ None
# prev curr
# Step 2: None ? 10 ? 20 ? 30
# prev curr (None)
# Result: None ? 10 ? 20 ? 30
# Return prev = 30 (new head)

# Recursive approach � O(n) time, O(n) space (stack)
def reverse_recursive(head):
 # Base case
 if head is None or head.next is None:
 return head
 
 # Recursively reverse rest of list
 new_head = reverse_recursive(head.next)
 
 # Current node ko next ke baad lagao
 head.next.next = head
 head.next = None
 
 return new_head

# Recursive mein stack frame har node ke liye banta hai
# Space O(n) hoti hai � recursive approach less preferred
# But code elegant hota hai

Mental Model for Reverse: Imagine karo tum ek chain of cards palat rahe ho. Har card ko utha ke peeche lagao. Pehle card (head) sabse peeche jaayega, aur last card sabse aage. Tumhe sirf pointers palatne hain � data nahi hilna chahiye.

Try it: code khud likho

Exercise

Question: Function likho jo linked list [1, 2, 3, 4, 5] ko reverse kare. Answer mein reversed list likho.

Question: List [10, 20, 30] mein position 2 pe value 25 insert karo. Final list likho.

Common mistakes

Losing head during reverse: Reverse karte waqt prev aur current ko galat order mein update karna. Hamesha pehle next_node = current.next save karo, phir current.next = prev karo.
Breaking the chain: Insert/delete mein ek pointer change karne se pehle doosra change kar dena. Hamesha naye node ka next pehle set karo, phir previous node ka next update karo.
Null pointer access: Empty list pe delete operation try karna. Hamesha if head is None check karo.
Off-by-one in position: Position 0 = head, position 1 = second node. Beginners position 1 se start karte hain but 0-based indexing hoti hai.

Lesson complete?

Operations seekh liye✓ Ab Floyd's Cycle Detection algorithm seekhte hain � ye linked list ka sabse interesting algorithm hai aur interview favourite hai.