Linked List — Frame-by-Frame Visuals¶
Notation: [10|*] মানে value 10 আর একটা জ্যান্ত next-arrow সহ একটা node; [30|/] মানে next হলো None। উপরে/নিচের label দেখায় কোন variable কোন node-এর দিকে point করছে। প্রতিটা frame নিজে আবার আঁকো — pointer fluency আসলে হাতের skill।
1. Head-এ insert¶
10 -> 20 -> 30-এর সামনে 5 insert করো।
FRAME 1 — before FRAME 2 — create the node
head head
| |
v v
[10|*] -> [20|*] -> [30|/] [10|*] -> [20|*] -> [30|/]
new = [5|/] (an island)
FRAME 3 — new.next = head FRAME 4 — head = new
head head
| |
v v
[10|*] -> [20|*] -> [30|/] [5|*] -> [10|*] -> [20|*] -> [30|/]
^
|
[5|*] (new now points INTO the list) done — 2 assignments, O(1)
2. একটা node-এর পরে insert (safe order-টা)¶
10 ধরে রাখা node-টার পরে 15 insert করো।
FRAME 1 — before FRAME 2 — new.next = a.next (grab tail FIRST)
a a
| |
v v
head->[10|*] -> [20|*] -> [30|/] head->[10|*] -> [20|*] -> [30|/]
new=[15|/] ^
|
[15|*] (15 already points at 20)
FRAME 3 — a.next = new RESULT
a
|
v
head->[10|*] -> [15|*] -> [20|*] -> [30|/]
done — nothing was ever unreachable, even mid-operation
Step গুলো উল্টো order-এ করলে, frame 2-তেই 20 আর 30 চিরতরে কেটে আলাদা হয়ে যেত।
3. একটা node delete করা (bypass করো)¶
20 ধরে রাখা node-টা delete করো। আমাদের দাঁড়াতে হবে তার predecessor prev-এর কাছে।
FRAME 1 — locate prev and target FRAME 2 — prev.next = target.next
prev target prev target
| | | |
v v v v
head->[10|*]->[20|*]->[30|/] head->[10|*] [20|*]->[30|/]
|________________^
(10 now bypasses 20)
FRAME 3 — final shape
head->[10|*]->[30|/] node 20 has no incoming arrows; Python's
garbage collector reclaims it. O(1) once found.
খোঁজার ধাপটা (prev পর্যন্ত হাঁটা) হলো O(n) অংশ; surgery-টা নিজে O(1)।
4. List-টা in place reverse করো — তিন-pointer-এর নাচ¶
1 -> 2 -> 3 -> / reverse করো। Pointer: prev (done part), cur (current node), nxt (saved lifeline)।
FRAME 0 — start
prev = / cur the loop body, every time:
| 1) nxt = cur.next (save the tail!)
v 2) cur.next = prev (flip one arrow)
[1|*] -> [2|*] -> [3|/]
3) prev = cur (advance)
4) cur = nxt (advance)
FRAME 1 — after first loop body
prev cur
| |
v v
[1|/] [2|*] -> [3|/] arrow 1->2 became 1->/ ... wait, it became
^ 1 -> prev(None). The "done" part is just [1].
(reversed part) nxt had saved node 2, so nothing is lost.
FRAME 2 — after second loop body
prev cur
| |
v v
[1|/] <- [2|*] [3|/] done part: 2 -> 1 -> /
remaining: just 3
FRAME 3 — after third loop body
prev cur = / -> loop ends
|
v
[1|/] <- [2|*] <- [3|*]
FRAME 4 — head = prev
new head -> [3|*] -> [2|*] -> [1|/] every arrow flipped, O(n) time, O(1) space
যে একটা জিনিস এটাকে safe বানায়: step 2 ধ্বংস করার আগেই step 1 cur.next save করে রাখে। Insertion-এর ordering rule-এর সাথে একই শিক্ষা।
5. Slow/fast pointers — এক pass-এ middle খোঁজা¶
slow 1 hop করে, fast 2 hop করে। fast যখন পড়ে যায়, slow দাঁড়িয়ে থাকে middle-এ।
list: [1] -> [2] -> [3] -> [4] -> [5] -> /
FRAME 0: slow=1 fast=1 [1] [2] [3] [4] [5]
S
F
FRAME 1: slow=2 fast=3 [1] [2] [3] [4] [5]
S (fast moved 2)
F
FRAME 2: slow=3 fast=5 [1] [2] [3] [4] [5]
S
F
FRAME 3: fast.next is None -> stop. slow is at [3], the exact middle.
কেন কাজ করে: fast দ্বিগুণ দূরত্ব cover করে, তাই fast যখন n node দেখে ফেলেছে, slow দেখেছে n/2।
6. Tortoise and hare — cycle detection¶
নিচের list-টা loop করে: node 5-এর next আবার node 3-এর দিকে point করে (একটা "rho" ρ shape)।
[1] -> [2] -> [3] -> [4] -> [5]
^ |
+-------------+
FRAME 0: T=1 H=1
FRAME 1: T=2 H=3
FRAME 2: T=3 H=5
FRAME 3: T=4 H=4 <-- SAME NODE. Cycle confirmed.
Cycle থাকলে কেন তাদের দেখা হতেই হবে: দুজনেই একবার loop-এর ভেতরে ঢুকে গেলে, hare প্রতি step-এ tortoise-এর উপর ঠিক একটা position এগিয়ে যায়। যে gap প্রতি step-এ 1 করে কমে, সেটা বড়জোর (cycle length) step-এ 0-তে নামে — তারা একে অপরকে "টপকে যেতে" পারে না। Cycle নেই? Hare শুধু None-এ গিয়ে ধাক্কা খায় আর আমরা false report করি।
7. Runner technique — শেষ থেকে nth node, এক pass-এ¶
1 -> 2 -> 3 -> 4 -> 5-এর শেষ থেকে 2nd node delete করো। একটা dummy থেকে front-কে n+1 = 3 hop এগিয়ে পাঠাও, তারপর দুজনকে একসাথে সরাও।
dummy -> [1] -> [2] -> [3] -> [4] -> [5] -> /
FRAME 0: back=dummy front=dummy
FRAME 1: (advance front 3x) back=dummy front=[3]
FRAME 2: move both until front = None:
back=[1] front=[4]
back=[2] front=[5]
back=[3] front=/ <- stop
back is at [3]; back.next is [4] = the 2nd from the end. Bypass it:
dummy -> [1] -> [2] -> [3] -> [5] -> /
n+1-এর fixed gap-এর মানে: front শেষে পৌঁছালে, back ঠিক শেষ থেকে n+1 দূরে — অর্থাৎ যে node delete করতে হবে তার predecessor-এ। এক pass, length আগে থেকে গোনার দরকার নেই।
এই frame গুলো কীভাবে study করবে¶
- Sequence 4 (reversal) আর 6 (tortoise-hare) হলো interview-র heavyweight — খালি পাতা থেকে আঁকতে না পারা পর্যন্ত বারবার আঁকো।
- তারপর পড়ো operations.md, যেখানে প্রতিটা operation পায় cost আর pitfall, আর patterns.md, যেখানে এই visual গুলো named technique হয়ে ওঠে।