Linked List — Concept (ধারণা)¶

একটা বাস্তব জীবনের analogy দিয়ে শুরু করি¶

ভাবো একটা scavenger hunt-এর কথা।

তোমার হাতে একটা clue ধরিয়ে দেওয়া হলো (এটাই head)। সেই clue-তে আছে একটা পুরস্কার (এটাই value) আর পরের clue-টা কোথায় তার ঠিকানা (এটাই next pointer)। তুমি সেখানে যাও, পুরস্কার নাও, পরের clue কোথায় পড়ে নাও, আর এগোতে থাকো। শেষ clue-তে লেখা "THE END" (None)।

Scavenger hunt-এর key property গুলো:

Clue গুলো শহরের যেকোনো জায়গায় লুকানো থাকতে পারে — পাশাপাশি থাকার দরকার নেই। (Node গুলো memory-র যেকোনো জায়গায় থাকে।)
তুমি সরাসরি clue #7-এ jump করতে পারো না। তোমাকে clue 1 → 2 → ... → 7 follow করতেই হবে। (কোনো O(1) indexing নেই।)
Clue 2 আর clue 3-এর মাঝে নতুন clue যোগ করা সহজ: clue 3-এর location-এর দিকে point করা নতুন একটা clue লেখো, তারপর clue 2 edit করে নতুনটার দিকে point করাও। আর কোনো clue নড়ে না। (জানা জায়গায় O(1) insertion।)
পরেরটা কোথায় তা পড়ার আগেই কোনো clue নষ্ট হয়ে গেলে, তার পরের সবকিছু চিরতরে হারিয়ে যায়। (Classic lost-pointer bug।)

Array chapter-এর mailbox-সারির সাথে তুলনা করো: mailbox গুলো পাশাপাশি bolt করা (instant access, কষ্টের insertion); scavenger clue গুলো ছড়ানো কিন্তু re-link করা যায় (slow access, ব্যথাহীন insertion)।

Memory-র ছবিটা¶

Array memory-র একটা অখণ্ড block দখল করে। Linked list-এর node গুলো ছড়িয়ে থাকে — allocator যেখানে জায়গা পেয়েছে সেখানে — আর জোড়া থাকে store করা address দিয়ে:

RAM (addresses are made up):

  addr 5000            addr 7240            addr 6016
  +------+------+      +------+------+      +------+------+
  |  10  | 7240 | ---> |  20  | 6016 | ---> |  30  | None |
  +------+------+      +------+------+      +------+------+
   value   next         value   next         value   next

  head = 5000   (the ONLY thing the list object itself remembers)

Logical view (এখন থেকে আমরা এভাবেই আঁকব):

head -> [10|*] -> [20|*] -> [30|/]        ( / means next = None )

এই ছড়িয়ে থাকার দুটো consequence:

Memory overhead। প্রতিটা element একটা extra pointer-এর দাম দেয় (আর Python-এ, প্রতি node-এ full object overhead)। দশ লাখ int node-এর list-এ রাখলে দশ লাখ int array-তে রাখার চেয়ে অনেক বেশি memory খরচ হয়।
Cache-এর শত্রুতা। List-এর উপর হাঁটতে গেলে RAM-এ লাফালাফি হয়, তাই দুটো structure-এর জন্যই traversal "O(n)" হলেও wall-clock time-এ array scan অনেক fast। Big-O constant লুকায়; hardware লুকায় না।

Python-এ Node¶

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None       # None = "points at nothing yet"

আরেকটা node ধরে রাখা একটা next field-ই হলো ছবিগুলোর arrow। a.next = b assign করা মানে একটাই arrow নতুন করে আঁকা — কিছু copy হয় না।

Core invariants¶

একটাই entry point। List-এ reachable সবকিছু head থেকে next arrow follow করেই reachable।
Termination। একটা সুস্থ (non-circular) list-এ next follow করতে করতে শেষমেশ None-এ পৌঁছাও। কখনো না পৌঁছালে তোমার একটা cycle আছে।
শুধু local edit। Insertion আর deletion বড়জোর দুটো pointer বদলায়; প্রতিবেশী ছাড়া আর কোনো node ছোঁয়া হয় না।
Rewiring-এর order matter করে। a-র পরে new insert করার সময়: আগে new.next = a.next set করো, তারপর a.next = new। Order উল্টে দাও আর list-এর লেজটা হারিয়ে যায়।
(Size counter থাকলে) length সমান head থেকে None পর্যন্ত hop-এর সংখ্যা — প্রতিটা insert/delete-এ sync রাখো।

কখন linked list ব্যবহার করবে¶

ঘন ঘন জানা position-এ insertion/deletion (বিশেষ করে সামনে), আর জায়গাটার reference তোমার হাতে আছে।
তোমার O(1) splicing দরকার — copy না করে sequence কাটা/জোড়া।
যে structure গুলো ভেতরে আসলে linked list, সেগুলো বানানো: queue/deque, LRU cache, hash-table collision chain, adjacency list।
যে interview answer-এ "O(1) extra space, modify in place" শর্ত array-তে copy করা rule out করে দেয়।

কখন linked list ব্যবহার করবে NA¶

তোমার index দিয়ে access দরকার → array দেয় O(1); list দেয় প্রতি access-এ O(n)।
তোমার binary search দরকার → O(1) jump লাগে; সাধারণ linked list-এ অসম্ভব।
বড় data-র performance-critical scan → cache behavior-এ array জেতে।
Memory টানাটানি → per-node overhead ভারী, বিশেষ করে Python-এ।
রোজকার Python code-এ → list আর collections.deque-ই প্রায় সব practical দরকার মেটায়; হাতে বানানো linked list মূলত শেখা আর interview-র জন্য।

Complexity table¶

head (আর optionally একটা tail pointer) সহ n node-এর singly linked list-এর জন্য:

Operation	Time	Why
Access by index i	O(n)	head থেকে i hop হাঁটতেই হবে
Search by value	O(n)	হাঁটো আর compare করো
Insert at head	O(1)	একটা arrow rewire + head সরাও
Insert at tail (with tail pointer)	O(1)	tail-এর arrow rewire করো
Insert at tail (without tail pointer)	O(n)	আগে শেষ পর্যন্ত হাঁটতে হবে
Insert after a node you hold	O(1)	দুটো arrow assignment
Delete head	O(1)	head এক ধাপ সরাও
Delete after a node you hold	O(1)	একটা arrow bypass করো
Delete a node by value	O(n)	তার predecessor খুঁজতেই হবে
Reverse in place	O(n) time, O(1) space	এক pass, তিনটা নড়তে থাকা pointer
Find middle / detect cycle	O(n) time, O(1) space	slow/fast pointers

ছোট ছোট snippet, dry run সহ¶

Snippet 1 — হাতে হাতে একটা list বানানো¶

a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.next = c
head = a            # head -> 10 -> 20 -> 30 -> None

Dry run:

create a [10|/], b [20|/], c [30|/]   (three islands)
a.next = b   ->  [10|*]->[20|/]   [30|/]
b.next = c   ->  [10|*]->[20|*]->[30|/]
head = a     ->  the chain now has its entry point

Snippet 2 — traversal (universal loop-টা)¶

cur = head
while cur is not None:
    print(cur.value)
    cur = cur.next     # hop forward

Dry run:

cur=node(10) -> print 10 -> hop
cur=node(20) -> print 20 -> hop
cur=node(30) -> print 30 -> hop
cur=None     -> loop ends (the / terminator did its job)

Snippet 3 — head-এ insert মানে দুটো লাইন¶

new = Node(5)
new.next = head     # new points at the old front
head = new          # the entry point moves

Dry run:

before: head -> [10] -> [20] -> [30] -> /
new=[5|/]
new.next = head   ->  [5]->[10]->[20]->[30]->/   (head still at 10!)
head = new        ->  head now at 5. Zero nodes moved. O(1).

Snippet 4 — lost-tail bug (আর তার fix)¶

# Goal: insert x between a and its successor.
# BUG: a.next = x          # the old a.next is now unreachable!
#      x.next = a.next     # ...so this makes x point to ITSELF.

# FIX: save/redirect before overwriting:
x.next = a.next            # x grabs the tail first
a.next = x                 # then a lets go

Bug-টার dry run:

before: a=[10|*]->[20|...]      x=[15|/]
a.next = x  ->  a=[10|*]->x=[15|/]      node 20 and everything after: LOST
x.next = a.next  ->  x.next = x         a self-referencing knot. Infinite loop ahead.

এই একটা ordering rule — incoming arrow ঘোরানোর আগে নতুন node-এর outgoing arrow জোড়া লাগাও — পৃথিবীর সবচেয়ে common linked-list bug-টা আটকে দেয়।

মনে রাখার মতো এক বাক্য¶

Linked list instant position-এর বদলে নেয় instant surgery: সে item i-তে jump করতে পারে না, কিন্তু একবার সঠিক node-এর সামনে দাঁড়িয়ে গেলে, insert বা remove-এর খরচ মাত্র দুটো pointer move — list যত লম্বাই হোক না কেন।

এরপর: pointer গুলোকে সত্যি সত্যি নড়তে দেখো visual-explanation.md-তে।