Linked List — Core Operations¶
সব example-এ ব্যবহার হয়েছে Node(value, next)-এর একটা singly linked list, সাথে একটা head reference। "You hold a node" মানে তোমার কাছে ইতিমধ্যে সেটার দিকে point করা একটা variable আছে — find step লাগলে, সেটা আলাদা করে গোনা হয়।
1. Traverse — প্রতিটা node ঘুরে দেখো¶
কী: head থেকে None পর্যন্ত হাঁটো, প্রতিটা node-এ কিছু একটা করতে করতে।
কেন O(n): প্রতি node-এ এক hop, n node, কোনো shortcut সম্ভব না — node i-এর address রাখা আছে node i−1-এর ভেতরে, আর কোথাও না।
Pitfalls: cur = cur.next ভুলে গেলে = infinite loop। Cycle থাকার সম্ভাবনা থাকলে এই loop কখনো শেষ হয় না — আগে cycle detect করো (operation 8)।
2. Value দিয়ে search¶
কী: যে প্রথম node-এর value মেলে সেটা খোঁজো।
কেন O(n): traversal-এর মতোই; worst case-এ value-টা শেষে অথবা নেই-ই।
def find(head, target):
cur = head
while cur is not None:
if cur.value == target:
return cur
cur = cur.next
return None
Pitfalls: caller-এর যখন node দরকার তখন value return করা (surgery করতে সাধারণত node-টাই লাগে)। Deletion-এর জন্য আসলে দরকার predecessor — বরং একটা prev trailing pointer নিয়ে search করো।
3. Head-এ insert¶
কী: নতুন node-টা প্রথম node হয়ে যায়।
কেন O(1): দুটো assignment, n-এর উপর নির্ভর করে না। এটাই linked list-এর signature সস্তা move (একই কাজের জন্য Python list দেয় O(n))।
Pitfalls: class-এর ভেতরে self.head = new ভুলে যাওয়া (বদলে একটা local variable-এ assign করা)। খালি list-এও দিব্যি কাজ করে — new.next আপনা থেকেই None হয়ে যায়।
4. একটা নির্দিষ্ট node-এর পরে insert¶
কী: node a-র ঠিক পরে একটা নতুন node গুঁজে দাও।
কেন O(1): দুটো pointer write; a-র বাইরে কোনো প্রতিবেশী ছোঁয়া হয় না।
new = Node(15)
new.next = a.next # FIRST: grab the tail
a.next = new # THEN: redirect into the new node
Pitfalls: ওই দুটো লাইন অদলবদল করলে a-র পরের সবকিছু এতিম হয়ে যায় (দেখো concept.md snippet 4)। এটাই সবচেয়ে common linked-list bug।
5. Tail-এ insert¶
কী: শেষে append করো।
কেন tail pointer ছাড়া O(n): আগে শেষ node পর্যন্ত হাঁটতেই হবে। কেন একটা থাকলে O(1): একটা tail reference রাখো আর প্রতি append-এ update করো — queue implementation-এর standard upgrade।
def append(head, value): # O(n) version
new = Node(value)
if head is None:
return new # new head
cur = head
while cur.next is not None:
cur = cur.next
cur.next = new
return head
Pitfalls: empty-list case একটা নতুন head return করে — return value ignore করা caller-রা node-টা হারিয়ে ফেলে। আর maintain করা একটা tail pointer-কে শেষ node delete হলেও ঠিক করতে হবে, নাহলে সে dangle করে।
6. Head delete করো¶
কী: প্রথম node সরাও।
কেন O(1): head এক ধাপ সরাও; পুরনো node-টা garbage হয়ে যায়।
Pitfalls: খালি list থেকে delete করা। Class-এ আবারও, self.head update করো, local না।
7. একটা node-এর পরে delete / value দিয়ে delete¶
কী: prev-এর পরের node-টা bypass করে সরাও।
কেন surgery O(1), value দিয়ে total O(n): bypass-টা একটাই assignment, কিন্তু কোনো value-র predecessor খুঁজতে একটা scan লাগে।
before: prev->[10] -> [20] -> [30] after: prev->[10] -> [30]
^ remove (20 has no incoming arrow -> GC)
def delete_value(head, target):
dummy = Node(0) # dummy guards the "delete the head" case
dummy.next = head
prev = dummy
while prev.next is not None:
if prev.next.value == target:
prev.next = prev.next.next # bypass
break
prev = prev.next
return dummy.next # possibly-new head
Pitfalls: dummy ছাড়া head delete করতে আলাদা special case লাগে — dummy pattern (দেখো patterns.md) এক code path দিয়েই সবকিছু সামলায়। আরো: এখানে prev.next.next safe শুধু এই কারণে যে prev.next এইমাত্র check হয়েছে।
8. Cycle detect করো (Floyd's tortoise and hare)¶
কী: ঠিক করো next follow করলে কখনো চিরকাল ঘুরতে থাকবে কিনা।
কেন O(n) time, O(1) space: loop-এর ভেতরে hare প্রতি step-এ একটা position এগিয়ে যায়, তাই এক cycle-length-এর মধ্যে তাদের দেখা হয়; কোনো visited-set memory লাগে না।
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity, not value equality!
return True
return False
Pitfalls: is-এর বদলে == ব্যবহার করা (দুটো আলাদা node সমান value ধরতে পারে); fast.next আগে check না করে fast.next.next check করা (None-এ crash); সরানোর আগেই meeting check শুরু করা (step 0-তে slow is fast এমনিতেই সত্য)।
9. Middle খোঁজো (slow/fast)¶
কী: এক pass-এ middle node।
কেন O(n): fast প্রতি loop-এ 2 hop করে; সে ~n hop শেষ করলে slow করেছে ~n/2।
def middle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow # for even length: the SECOND of the two middles
Pitfalls: even length-এ তোমার loop কোন middle-টা return করে সেটা জেনে রাখো — palindrome আর reorder problem এটার উপর নির্ভর করে। প্রথম middle পেতে চাইলে fast = head.next দিয়ে শুরু করে adjust করো।
10. In place reverse করো¶
কী: প্রতিটা arrow উল্টে দাও যাতে শেষ node-টা head হয়ে যায়।
কেন O(n) time / O(1) space: প্রতিটা node-এর arrow ঠিক একবার flip হয়; n যাই হোক, extra variable মাত্র তিনটা (prev, cur, nxt)।
prev = None
cur = head
while cur is not None:
nxt = cur.next # 1. save the lifeline
cur.next = prev # 2. flip this node's arrow
prev = cur # 3. advance the done-frontier
cur = nxt # 4. step into the saved remainder
head = prev
Pitfalls: ওই চারটা লাইনের যেকোনো reordering এটা ভেঙে দেয় — line 1 অবশ্যই line 2-এর আগে। শেষে prev-এর বদলে cur (যেটা None) return করা। Full frame-by-frame আছে visual-explanation.md section 4-এ।
Big-O summary table¶
| Operation | Singly linked list | Python list (array) |
Winner |
|---|---|---|---|
| Access by index | O(n) | O(1) | array |
| Search by value | O(n) | O(n) | tie (practice-এ array faster — cache) |
| Insert at front | O(1) | O(n) | linked list |
| Insert at back | O(1) with tail / O(n) without | O(1) amortized | tie (tail সহ) |
| Insert after a held node | O(1) | O(n) | linked list |
| Delete at front | O(1) | O(n) | linked list |
| Delete after a held node | O(1) | O(n) | linked list |
| Delete by value | O(n) find + O(1) fix | O(n) find + O(n) shift | linked list (সামান্য) |
| Reverse in place | O(n) / O(1) space | O(n) / O(1) space | tie |
| Find middle / detect cycle | O(n) / O(1) space | trivial / not applicable | — |
| Memory per element | value + pointer + object overhead | value (+ ছোট amortized slack) | array |
এই table-টাই এই chapter-এর গোটা গল্প: front-and-middle surgery vs. instant indexing। যার সস্তা column তোমার hot operation-এর সাথে মেলে, সেই structure-টাই বেছে নাও।
এরপর: এই mechanics গুলোকে named technique বানাও patterns.md-তে।