Linked list — singly - node structure, traversal, insert head - tail - middle, delete

3.2.2 · Coding › Linear Data Structures

1. Node — list ka atom

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

Figure — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

2. Traversal — chain mein chalna

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 box

3. Insertion

Poora skill yeh hai: pehle node create karo, pehle uska next wire karo, phir incoming pointer ko aakhir mein change karo. Yeh order ulta karo aur chain cut ho jaayegi.

3a. HEAD pe Insert — $O (1)$

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 first

3b. TAIL pe Insert — $O (n)$ (ya $O (1)$ tail pointer ke saath)

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 node

3c. MIDDLE mein Insert (position `k` ke baad) — $O (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 -> new

4. 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.next

Formula Complexity summary

Operation	Time
Traverse / search	$O (n)$
Insert head	$O (1)$
Insert tail (head only)	$O (n)$
Insert after node `p` (have `p`)	$O (1)$
Delete (by value)	$O (n)$
Index access	$O (n)$

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek treasure hunt hai. Har clue card pe ek khazana hai AUR yeh bhi likha hai ki agla card kahan chhupa hai. Aapko sirf pehle card ka pata hai (yahi head hai). Aakhri card kehta hai "aur koi card nahi" (yahi null hai). Saare khazane padhne ke liye aapko card-to-card follow karna padega — aap seedha card #7 pe teleport nahi kar sakte. Ek card add karne ke liye, aap likhte ho, usse us card ki taraf point karte ho jis ki taraf pichla card point kar raha tha, phir pichle card ko apne naye card ki taraf point karwa dete ho. Ek card remove karne ke liye, aap bas usse pehle wale card ko uske baad wale card ki taraf point karwa dete ho — hata hua card ab jungle mein kho jaata hai. Yeh re-pointing bahut sasti cheez hai; yahi linked lists ka poora jadoo hai.

Flashcards

Singly-linked-list node mein kaun se do fields hote hain?

data (value) aur next (agle node ka pointer, ya end mein null).

Array mein random index access

O (1)

kyun hai lekin linked list mein

O (n)

kyun?

Array base + i*size arithmetic use karta hai; linked list sirf har node ka successor jaanti hai, isliye head se walk karna padta hai.

Traversal loop ka sahi condition kya hai?

while cur is not None (node process karo, phir cur = cur.next).

while cur.next is not None traversal condition ke roop mein kyun fail karta hai?

Yeh aakhri node skip kar deta hai aur empty list pe crash kar deta hai (None.next).

Head pe insert karne ke liye do ordered steps batao.

1) new.next = head 2) head = new. Inhe ulta karne se poori purani list kho jaati hai.

Sirf head pointer ke saath insert-at-tail

O (n)

kyun hai?

Attach karne se pehle aapko us node tak walk karna padta hai jiska next null hai.

Node p ke baad new insert karne ke do steps?

1) new.next = p.next 2) p.next = new.

Singly list mein deletion mein previous node kyun track karna padta hai?

Unlink karne ke liye aap prev.next = cur.next set karte ho, lekin singly list mein koi backward pointer nahi hota, isliye prev ko saath rakhna padta hai.

Head node ko kaise delete karte hain?

head = head.next.

Kisi node ki taraf kuch point na karne par kya hota hai?

Woh unreachable ho jaata hai aur garbage-collected / freed ho jaata hai.

Connections

Arrays — contiguous memory & O(1) indexing (ulta trade-off)
Doubly Linked List (prev pointer add karta hai → backward walk, aasaan delete)
Stack using Linked List (push/pop = head pe insert/delete, $O (1)$ )
Queue using Linked List (head + tail pointers chahiye)
Pointers and References (underlying mechanism)
Big-O Notation (kyun insert-head array insert-front se behtar hai)