Linked List — node, arrow ও pointer¶

একটি node-এ মান ও পরের node-এর reference থাকে। তীর বদলানোই list বদলানো; মানগুলোকে array-এর মতো সরাতে হয় না। নিচের প্রতিটি ধাপে দেখো, কোন variable থেকে এখনও বাকি node-গুলোতে পৌঁছানো যায়।

1. সামনে insert: আগে জুড়ো, পরে head সরাও¶

10 → 20 → 30-এর সামনে 5 বসাতে দুটি assignment যথেষ্ট। নতুন node বানানোর পর তার next প্রথমে পুরনো head-কে দেখাবে।

flowchart LR
  subgraph before["১ · নতুন node আলাদা"]
    direction LR
    H1["head"] --> A1["10"] --> B1["20"] --> C1["30"] --> Z1["None"]
    N1["new · 5"] --> NZ1["None"]
  end
  subgraph linked["২ · new.next = head"]
    direction LR
    N2["new · 5"] --> A2["10"] --> B2["20"] --> C2["30"] --> Z2["None"]
    H2["head"] --> A2
  end

৩ · head = new: নতুন প্রথম node

শেষ অবস্থা
চিহ্নিত ঘর: 5↑ head
→
10
→
20
→
30
→
None
পুরো list না হেঁটেই কাজ শেষ: O(1)।

2. মাঝখানে insert: পুরনো next বাঁচিয়ে রাখো¶

a node 10-কে দেখাচ্ছে; তার পরে 15 বসাব। আগে new.next = a.next, পরে a.next = new।

flowchart TD
  subgraph saved["আগে · নতুন node-কে পুরনো tail-এর সঙ্গে জুড়ো"]
    A["a · 10"] --> B["20"] --> C["30"] --> Z["None"]
    N["new · 15"] --> B
  end
  subgraph inserted["পরে · a.next নতুন node-কে দেখাবে"]
    A2["a · 10"] --> N2["new · 15"] --> B2["20"] --> C2["30"] --> Z2["None"]
  end

উল্টো ক্রমে a.next = new করে তারপর new.next = a.next করলে 15 নিজের দিকেই তীর বানাবে। পুরনো 20→30 অংশের reference হারাতে পারো। অন্য নিরাপদ উপায়: আগে old_next = a.next রাখো, তারপর তীর বদলাও।

3. Delete: আগের node থেকে পরেরটিতে সেতু বানাও¶

20 মুছতে prev থাকবে 10-এ। prev.next = target.next করলে head থেকে হাঁটার পথে 20 আর পড়বে না।

flowchart LR
  subgraph original["আগে"]
    A["prev · 10"] --> B["target · 20"] --> C["30"] --> Z["None"]
  end
  subgraph bypassed["তীর বদলানোর পরে"]
    A2["prev · 10"] --> C2["30"] --> Z2["None"]
    B2["target · 20"] --> C2
  end

prev খুঁজতে O(n) লাগতে পারে; তীর বদলাতে O(1)। ছবিতে target এখনও 20-কে ধরে আছে। সব জীবিত reference চলে গেলে Python সেই node-এর memory পুনরুদ্ধার করতে পারে; list থেকে বাদ গেলেই object সঙ্গে সঙ্গে মুছে যায় না।

4. Reverse: আগে পরের node বাঁচাও, তারপর তীর ঘোরাও¶

তিনটি reference-এর কাজ আলাদা: prev উল্টানো অংশের শুরু, cur বর্তমান node, nxt বাকি অংশের নিরাপদ reference।

Python

prev = None
cur = head
while cur is not None:
    nxt = cur.next      # বাকি list-এর reference বাঁচাও
    cur.next = prev     # একটি তীর উল্টাও
    prev = cur          # উল্টানো অংশ বড় হলো
    cur = nxt           # বাকি অংশে এগোও
head = prev

1 → 2 → 3 থেকে 3 → 2 → 1

শুরু · সব node এখনও বাকি
1↑ cur
→
2
→
3
→
None
prev = None।
শেষ · সব তীর উল্টেছে
3↑ head · prev
→
2
→
1
→
None
cur = None, তাই loop শেষ।

মাঝের প্রতিটি loop-এর অবস্থা:

loop	তীর ঘোরানোর আগে `nxt`	উল্টানো অংশ: `prev` থেকে	বাকি অংশ: `cur` থেকে
শুরু	—	`None`	`1 → 2 → 3 → None`
1	node 2	`1 → None`	`2 → 3 → None`
2	node 3	`2 → 1 → None`	`3 → None`
3	`None`	`3 → 2 → 1 → None`	`None`

প্রতিটি node-এ একবার কাজ: O(n) সময়, O(1) অতিরিক্ত জায়গা। nxt না বাঁচিয়ে তীর ঘোরালে বাকি অংশে যাওয়ার পথ হারায়।

5. Slow/fast: একই পথে দুই গতি¶

প্রতি loop-এ slow এক node, fast দুই node এগোয়। এখানে fast.next শেষ হলে slow মাঝখানে থাকে।

পাঁচ node-এর middle হলো 3

শুরু
1↑ slow · fast
→
2
→
3
→
4
→
5
→
None
এক loop পরে
1
→
2↑ slow
→
3↑ fast
→
4
→
5
→
None
দুই loop পরে
1
→
2
→
চিহ্নিত ঘর: 3↑ slow
→
4
→
5↑ fast
→
None
fast.next = None। slow-এর node 3-ই middle।

জোড় সংখ্যক node হলে while fast and fast.next দ্বিতীয় middle দেয়। যেমন 1 → 2 → 3 → 4-এ উত্তর 3।

6. Cycle: দ্রুত pointer ঘুরে ধীরটিকে ধরে¶

এবার node 5 আবার node 3-কে দেখায়। একই মান নয়, একই node reference-এ পৌঁছেছে কি না পরীক্ষা করি।

flowchart LR
  A["1"] --> B["2"] --> C["3"] --> D["4"] --> E["5"]
  E --> C

loop	slow: এক ধাপ	fast: দুই ধাপ	সিদ্ধান্ত
শুরু	1	1	এখনও চালানো শুরু হয়নি
1	2	3	আলাদা
2	3	5	আলাদা
3	4	4	একই node: cycle আছে

Cycle-এর মধ্যে fast প্রতি loop-এ slow-এর তুলনায় এক node বেশি এগোয়। তাই তাদের দূরত্ব, cycle length দিয়ে ভাগের অবশিষ্ট হিসেবে, এক করে বদলে একসময় শূন্য হয়। Cycle না থাকলে fast বা তার next None হবে।

7. শেষ থেকে nth node: দুই pointer-এর ফাঁক স্থির রাখো¶

পাঁচ node থেকে শেষের দ্বিতীয় node, অর্থাৎ 4, বাদ দেব। Dummy node থাকলে প্রথম node বাদ দেওয়ার ক্ষেত্রও একইভাবে করা যায়।

n = 2: front-কে আগে n + 1 = 3 ধাপ পাঠাও

তিন ধাপ এগোনোর পরে
dummy↑ back
→
1
→
2
→
3↑ front
→
4
→
5
→
None
এরপর দুই pointer সমান গতিতে চলবে।
4 বাদ দেওয়ার পর
dummy
→
1
→
2
→
চিহ্নিত ঘর: 3↑ back
→
চিহ্নিত ঘর: 5
→
None
back.next = back.next.next; ফল 1 → 2 → 3 → 5।

ধাপ	back	front
শুরু	dummy	dummy
শুধু front: 1ম hop	dummy	1
শুধু front: 2য় hop	dummy	2
শুধু front: 3য় hop	dummy	3
দুজন এক ধাপ	1	4
দুজন আরও এক ধাপ	2	5
দুজন আরও এক ধাপ	3	`None`

এখন back ঠিক target-এর আগের node-এ। দৈর্ঘ্য আগে গোনা লাগেনি; মোট O(n) সময় ও O(1) অতিরিক্ত জায়গা।

নিজে চেষ্টা করো: তিন node reverse করার সময় প্রতিটি assignment-এর পরে prev, cur, nxt কোথায় আছে আঁকো। পরের পাঠ: operations ও patterns।