Linked list — singly - node structure, traversal, insert head - tail - middle, delete
1. The Node — the atom of the list
class Node:
def __init__(self, data):
self.data = data
self.next = None # null until linked
class LinkedList:
def __init__(self):
self.head = None # empty list
2. Traversal — walking the chain
def traverse(self):
cur = self.head # start at front door
while cur is not None: # null = end of chain
print(cur.data)
cur = cur.next # hop to next box3. Insertion
The whole skill is: create the node first, wire its next first, then change the incoming pointer last. Reverse that order and you cut the chain.
3a. Insert at HEAD —
def insert_head(self, data):
new = Node(data)
new.next = self.head # step 1: grab old front — Why? so we don't lose the chain
self.head = new # step 2: move front door — Why? new is now first3b. Insert at TAIL — (or with a tail pointer)
def insert_tail(self, data):
new = Node(data)
if self.head is None: # empty list special case
self.head = new # Why? no node to attach to; new becomes head
return
cur = self.head
while cur.next is not None: # Why .next here? we WANT the last node, not None
cur = cur.next
cur.next = new # attach after last node3c. Insert in MIDDLE (after position k) —
def insert_after(self, k, data): # insert after the k-th node (0-indexed)
cur = self.head
for _ in range(k): # Why k hops? to land ON node k
if cur is None:
raise IndexError("position out of range")
cur = cur.next
new = Node(data)
new.next = cur.next # step 1: new -> old successor
cur.next = new # step 2: cur -> new4. Deletion
def delete(self, value):
cur = self.head
if cur is None:
return # empty
if cur.data == value: # deleting the head
self.head = cur.next # Why? front door now skips old head
return
prev = self.head
cur = self.head.next
while cur is not None:
if cur.data == value:
prev.next = cur.next # unlink: prev skips cur
return
prev = cur # Why advance BOTH? keep prev one behind
cur = cur.nextRecall Feynman: explain to a 12-year-old
Imagine a treasure hunt. Each clue card has a treasure on it AND tells you where the next card is hidden. You only know where the first card is (that's head). The last card says "no more cards" (that's null). To read all treasures you must follow card-to-card — you can't teleport to card #7. To add a card, you write it, point it to the card the previous one was pointing to, then make the previous one point to your new card. To remove a card, you just make the card before it point to the card after it — the removed card is now lost in the woods. That re-pointing is super cheap; that's the whole magic of linked lists.
Flashcards
What two fields does a singly-linked-list node contain?
data (the value) and next (pointer to the next node, or null at the end).Why is random index access in a linked list but in an array?
base + i*size arithmetic; a linked list only knows each node's successor, so you must walk from head.What is the correct traversal loop condition?
while cur is not None (process node, then cur = cur.next).Why does while cur.next is not None fail as a traversal condition?
None.next).Give the two ordered steps to insert at head.
new.next = head 2) head = new. Reversing them loses the old list.Why is insert-at-tail with only a head pointer?
next is null before attaching.Two steps to insert new after node p?
new.next = p.next 2) p.next = new.Why must deletion track the previous node in a singly list?
prev.next = cur.next, but a singly list has no backward pointer, so prev must be carried.How do you delete the head node?
head = head.next.What happens to a node after nothing points to it?
Connections
- Arrays — contiguous memory & O(1) indexing (the trade-off opposite)
- Doubly Linked List (adds a
prevpointer → backward walk, easier delete) - Stack using Linked List (push/pop = insert/delete at head, )
- Queue using Linked List (needs head + tail pointers)
- Pointers and References (the underlying mechanism)
- Big-O Notation (why insert-head beats array insert-front)
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Socho ek treasure hunt chal rahi hai. Har card pe ek value likhi hai aur saath me likha hai ki agla card kahan chhupa hai. Yahi ek node hai: usme data (value) aur next (agle node ka address) hota hai. Aapko sirf pehle card ka pata hota hai — usse hum head bolte hain. Aakhri card pe likha hota hai "ab koi card nahi" — yeh null hai. Array me to aap seedhe item number 7 pe jump kar sakte ho (base + i*size), par linked list me yeh teleport nahi hota; aapko card-by-card chalna padta hai, isliye traversal aur search dono hote hain.
Magic tab dikhta hai jab insert ya delete karna ho. Array me beech me daalna ho to baaki sab elements shift karne padte hain — mehnga. Linked list me bas do arrows badalne hote hain. Insert ka golden rule: pehle naye node ka next set karo (new.next = purana), uske baad hi head ya prev.next ko naye node pe le jao. Ulta kiya to chain toot jaati hai aur poora aage ka list kho jaata hai.
Delete me ek catch hai: singly list me peeche dekhne ka koi pointer nahi hai. Kisi node ko hatane ke liye uske pehle wale node ko chahiye, taaki prev.next = cur.next karke beech wale node ko skip kar do. Isliye chalte waqt hamesha prev (trailing pointer) saath rakho. Aur head delete karna ho to special case: bas head = head.next.
Yaad rakho: insert head = (sabse sasta), insert tail sirf head se = (end tak chalna padta hai), aur agar aapke paas already wo node ho jiske baad insert karna hai to wo . Exam aur interview dono me yeh "wire-then-redirect" pattern baar-baar aata hai — ratta mat maaro, logic samjho.