Linked list — singly, doubly আর circular

১ · Linked list কী — ট্রেনের বগির মতো node আর pointer

কমলাপুর থেকে চট্টগ্রামগামী একটি ট্রেনের কথা ভাবুন। ইঞ্জিনের পেছনে একটার পর একটা বগি। প্রতিটি বগি শুধু জানে তার ঠিক পরের বগিটি কোনটি — আংটা দিয়ে জোড়া। মাঝে একটি নতুন বগি জুড়তে হলে পুরো ট্রেন সরাতে হয় না: শুধু একটি আংটা খুলে নতুন বগিটি ঢুকিয়ে দুই দিকে আংটা লাগালেই হলো। আবার ১২ নম্বর বগিতে যেতে চাইলে ইঞ্জিন থেকে হেঁটে হেঁটে গুনতে হয় — সরাসরি “১২ নম্বরে লাফ দেওয়ার” কোনো উপায় নেই।

এটাই linked list. পর্ব ১০-এ দেখেছেন, array-র সব উপাদান মেমরিতে পাশাপাশি বসে থাকে, তাই ঠিকানার হিসাব করে যেকোনো ঘরে সরাসরি যাওয়া যায়। Linked list-এ উপাদানগুলো মেমরির যেখানে খুশি থাকতে পারে; প্রতিটি উপাদান নিজের সাথে রাখে পরেরটির ঠিকানা। প্রতিটি উপাদানকে বলে node, আর সেই ঠিকানাকে বলে pointer (Python বা Java-তে একে reference বলে — কাজ একই)।

মেমরিতে আসলে কী ঘটে, একটি উদাহরণে দেখুন। ধরুন তিনটি node — 10, 20, 30 — মেমরির তিনটি এলোমেলো জায়গায় তৈরি হয়েছে। ঠিকানাগুলো কাল্পনিক, কিন্তু ধারণাটি আসল:

head = 0x7a40

ঠিকানা   val   next
0x7a40   10    0x91c8   ──┐
0x91c8   20    0x6010   ←─┘ ──┐
0x6010   30    null     ←─────┘

ছবিতে:  head → [10] → [20] → [30] → null

লক্ষ করুন, ঠিকানাগুলো ক্রমানুসারে নেই — 0x6010 আসলে 0x7a40-এর আগে। তাতে কিছু যায় আসে না; ক্রম ঠিক করে next-এর শিকল। এই নমনীয়তাই linked list-এর শক্তি, আর (পরে দেখবেন) এটাই তার দুর্বলতাও। কোডে একটি node লিখতে লাগে মাত্র একটি ছোট struct বা class:

Pseudocode (0-based গণনা; NIL = null)

NODE:
    val          // the data
    next         // address of the next NODE, or NIL

LENGTH(head):
    count = 0
    cur = head
    while cur != NIL:
        count = count + 1
        cur = cur.next
    return count

C++-এ struct Node { int val; Node* next; }; — এখানে Node* মানে “একটি Node-এর ঠিকানা”। Python-এ একটি ছোট class, যার next অ্যাট্রিবিউটে আরেকটি Node বস্তু বা None. Node-গুলো তৈরি হয় চলার সময়, প্রয়োজনমতো, heap memory থেকে — তাই list আগে থেকে আকার না জেনেই বাড়তে-কমতে পারে।

Linked list-এর তিনটি প্রধান রূপ আছে, এই পর্বে তিনটিই দেখব: singly linked list (প্রতিটি node শুধু পরেরটি চেনে), doubly linked list (আগে-পরে দুটোই চেনে) আর circular linked list (শেষ node আবার প্রথমটিতে ফেরে)।

২ · List-এ হাঁটা — traversal আর search

Linked list-এর প্রায় সব কাজের ভিত্তি একটি লুপ: head থেকে শুরু করে একটি pointer (নাম দিই cur, “current”) একটার পর একটা node-এ সরানো, যতক্ষণ না null আসে। একে বলে traversal. list ছাপা, দৈর্ঘ্য গোনা, যোগফল বের করা, কিছু খোঁজা — সব এই এক ধাঁচ।

খোঁজার কাজটি দেখুন। list-টি sorted হলেও এখানে binary search চলে না, কারণ মাঝের node-এ পৌঁছাতেই অর্ধেক পথ হাঁটতে হয়। তাই linear search-ই একমাত্র উপায়। নিচে প্রথমে 30 খুঁজব (পাওয়া যায়), তারপর 35 (পাওয়া যায় না):

1Node* search(Node* head, int x) {2    for (Node* cur = head; cur != nullptr; cur = cur->next)3        if (cur->val == x) return cur;   // found4    return nullptr;                      // not in the list5}

বিশ্লেষণ। লুপ প্রতিটি node-এ একবার থামে, প্রতিবার O(1) কাজ (একটি তুলনা, একটি pointer পড়া)। তাই traversal Θ(n), search worst case-এ Θ(n), আর k-তম node-এ পৌঁছানো Θ(k). বাড়তি জায়গা শুধু একটি pointer: O(1). array-তে a[k] O(1) — এই random access-এর সুবিধা linked list-এ নেই, আর এটিই তার সবচেয়ে বড় দাম।

৩ · Insert আর delete — শুধু কয়েকটি তীর বদলানো

Array-র মাঝে একটি উপাদান ঢোকাতে হলে তার ডানের সবাইকে এক ঘর সরাতে হয় — O(n). Linked list-এ কেউ সরে না; শুধু তীর (pointer) নতুন করে আঁকা হয়। ট্রেনের উদাহরণে, নতুন বগি জুড়তে মাত্র দুটি আংটা বদলাতে হয়। তিনটি মূল কাজ:

• শুরুতে যোগ (push front): নতুন node-এর next = পুরোনো head; তারপর head = নতুন node. O(1).
• p-র পরে যোগ (insert after): নতুন node-এর next = p-র next; তারপর p-র next = নতুন node. O(1) — যদি p আগে থেকেই হাতে থাকে।
• prev-এর পরেরটি মোছা (delete after): prev-এর next = মুছতে চাওয়া node-এর next; তারপর সেই node-এর মেমরি ফেরত। O(1) — কিন্তু মুছতে চাওয়া node-এর আগেরটি হাতে থাকতে হবে।

নিচের ডায়াগ্রামে head → [20] → [40] list-এ এই তিনটি কাজ পরপর দেখুন। ক্রমটি খুব মনোযোগ দিয়ে লক্ষ করুন — তীর বদলানোর ক্রম ভুল হলে list ভেঙে যায়।

1struct Node { int val; Node* next; };2// 1) insert at head: O(1)3Node* n = new Node{10, head};   // n->next = head4head = n;5// 2) insert after p: O(1)6n = new Node{30, p->next};      // n->next = p->next7p->next = n;8// 3) delete the node after prev: O(1)9Node* t = prev->next;10prev->next = t->next;           // unlink11delete t;                        // free the memory

সারকথা: তীর বদলানো O(1), কিন্তু সঠিক জায়গায় পৌঁছানো সাধারণত O(n). “মান 30-এর node মুছুন” বললে আগে search করে তার আগের node খুঁজতে হয় — মোট O(n). তাই linked list-এর O(1) insert/delete-এর দাবি সত্য শুধু তখনই, যখন সংশ্লিষ্ট node (বা তার আগেরটি) আগে থেকেই হাতে আছে। পরীক্ষায় এই সূক্ষ্ম পার্থক্যটি প্রায়ই জিজ্ঞেস করা হয়।

শেষে যোগ (push back) কেমন? শুধু head থাকলে শেষ node খুঁজতে পুরো list হাঁটতে হয় — O(n). সমাধান সহজ: head-এর সাথে একটি tail pointer-ও রাখুন, যা সবসময় শেষ node দেখায়। তখন push back O(1) — tail->next = n; tail = n;. তবে শেষ node মুছতে singly list-এ tail থাকলেও O(n) লাগে, কারণ শেষের আগের node খুঁজতে হয় — এই সমস্যার সমাধান doubly list (অংশ ৫)।

৪ · Dummy (sentinel) head — বিশেষ ক্ষেত্র দূর করার কৌশল

অংশ ৩-এর delete-এ একটি প্রশ্ন লুকিয়ে ছিল: যদি head নিজেকেই মুছতে হয়? head-এর আগে তো কোনো node নেই, তাই “prev-এর তীর বদলাও” নিয়মটি চলে না — head ভ্যারিয়েবলটিই বদলাতে হয়। ফলে প্রায় প্রতিটি linked list ফাংশনে একটি আলাদা if (head ...) শাখা ঢুকে পড়ে, আর বাগের বড় অংশ জন্মায় ঠিক সেখানেই।

কৌশলটি হলো: আসল head-এর সামনে একটি নকল node বসিয়ে দিন, যার মান অর্থহীন। একে বলে dummy বা sentinel node. এখন প্রতিটি আসল node-এর — প্রথমটিরও — একটি আগের node আছে। সব ক্ষেত্র একই নিয়মে চলে, শেষে শুধু dummy.next ফেরত দিলেই নতুন head পাওয়া যায়।

উদাহরণ: list থেকে মান x-এর সব node মুছে ফেলুন। dummy ছাড়া লিখলে আগে head-এর জন্য একটি আলাদা লুপ লাগে (কারণ শুরুর কয়েকটি node-ই x হতে পারে)। dummy দিয়ে লিখলে একটিই লুপ:

// remove every node whose value is x; returns the (possibly new) head
Node* removeAll(Node* head, int x) {
    Node dummy{0, head};                 // fake node in front of the real head
    Node* prev = &dummy;
    while (prev->next) {
        if (prev->next->val == x) {
            Node* t = prev->next;
            prev->next = t->next;        // unlink, prev stays where it is
            delete t;
        } else {
            prev = prev->next;           // move on only when nothing was removed
        }
    }
    return dummy.next;                   // the head may have changed
}

খেয়াল করুন দুটি সূক্ষ্ম বিষয়। (১) কিছু মুছলে prev এগোয় না — কারণ নতুন prev->next-ও x হতে পারে (যেমন 7 → 7 → 7). (২) dummy একটি সাধারণ local ভ্যারিয়েবল, heap-এ নয় — তাই একে delete করতে হয় না। এই ফাংশনের loop invariant: “dummy থেকে prev পর্যন্ত অংশে x-এর কোনো node নেই।” প্রতিটি ধাপে এটি টিকে থাকে, আর লুপ শেষে prev শেষ node-এ — তাই পুরো list-এ আর কোনো x নেই। সময় Θ(n), বাড়তি জায়গা O(1).

৫ · Doubly আর circular linked list

Doubly linked list — আগে-পরে দুই দিকেই তীর

Singly list-এর দুটি সীমাবদ্ধতা: পেছনে হাঁটা যায় না, আর একটি node হাতে থাকলেও তাকে মুছতে তার আগের node খুঁজতে হয় (O(n)). সমাধান: প্রতিটি node-এ দ্বিতীয় একটি pointer, prev, যা আগের node দেখায়।

null ← [10] ⇄ [20] ⇄ [30] → null
        head          tail

struct DNode { int val; DNode *prev, *next; };

// unlink node x in O(1): both neighbours are reachable from x itself
void unlink(DNode* x) {
    if (x->prev) x->prev->next = x->next;   // (else x was the head: update head)
    if (x->next) x->next->prev = x->prev;   // (else x was the tail: update tail)
    delete x;
}

এখন node হাতে থাকলে delete O(1), শেষ node মোছাও O(1) (tail-এর prev-ই নতুন tail), আর উল্টো দিকে traversal সম্ভব। দাম: প্রতিটি node-এ আরেকটি pointer (64-bit মেশিনে আরও 8 byte), আর প্রতিটি insert/delete-এ চারটি তীর ঠিক রাখার দায়িত্ব — একটি ভুললেই list এক দিক থেকে ঠিক, আরেক দিক থেকে ভাঙা।

ওপরের কোডে দুটি if লক্ষ করুন — আবার সেই বিশেষ ক্ষেত্র। বাস্তবের লাইব্রেরি এটি এড়ায় একটি sentinel দিয়ে: একটিমাত্র header node, যার next প্রথম node আর prev শেষ node, আর list-টি বৃত্তাকারে বন্ধ। তখন প্রতিটি আসল node-এর দুই পাশেই কেউ না কেউ থাকে, if লাগে না। GCC-র std::list আর Linux kernel-এর list_head দুটোই এই নকশা ব্যবহার করে।

C++-এ তৈরি doubly linked list হলো std::list (আর singly list হলো std::forward_list, C++11 থেকে)। এর বিশেষ গুণ: কোনো উপাদান যোগ বা মুছলে অন্য উপাদানের iterator অচল হয় না, আর splice দিয়ে একটি node বা পুরো আরেকটি list O(1)-এ জুড়ে দেওয়া যায় — কোনো কপি ছাড়াই।

#include <list>
std::list<int> L = {10, 20, 30};
auto it = std::next(L.begin());   // iterator to 20
L.insert(it, 15);                 // 10 15 20 30   O(1)
L.erase(it);                      // 10 15 30      O(1), other iterators stay valid
L.push_front(5); L.push_back(40); // 5 10 15 30 40 O(1) each

Python-এ আলাদা কোনো linked list টাইপ নেই। list আসলে একটি dynamic array (পর্ব ১০)। দুই প্রান্তে দ্রুত যোগ-বিয়োগের জন্য আছে collections.deque, যা CPython-এ ভেতরে ছোট ছোট array-ব্লকের একটি doubly linked list — পর্ব ১৪-এ এটি বিস্তারিত দেখবেন। Java-র LinkedList একটি doubly linked list.

Doubly list-এর সবচেয়ে বিখ্যাত ব্যবহার LRU cache (least recently used — “যে জিনিস সবচেয়ে বেশি সময় ধরে ব্যবহার হয়নি, সেটি আগে বাদ”): একটি hash table প্রতিটি key-র node সরাসরি খুঁজে দেয়, আর doubly list ব্যবহারের ক্রম রাখে। কোনো key ব্যবহার হলে তার node O(1)-এ তুলে list-এর সামনে বসানো হয়, জায়গা ফুরালে পেছনের node O(1)-এ বাদ। Hash table পর্ব ৩২-এ আসবে; তখন এই জোড়টি আবার মনে করবেন।

Circular linked list — শেষ থেকে আবার শুরুতে

শেষ node-এর next যদি null না হয়ে আবার প্রথম node-কে দেখায়, তাহলে পাই circular linked list. এখানে “শেষ” বলে কিছু নেই — একটি pointer চিরকাল ঘুরতে পারে। প্রায়ই head-এর বদলে শুধু tail রাখা হয়, কারণ tail->next-ই head — একটি pointer দিয়ে দুই প্রান্তই হাতের নাগালে।

   ┌──────────────────────┐
   ↓                      │
  [A] → [B] → [C] → [D] ──┘
                     tail

Round-robin scheduling. আপনার কম্পিউটারে একসাথে অনেক প্রোগ্রাম চলছে, কিন্তু CPU core হাতে গোনা। Operating system প্রতিটি প্রোগ্রামকে পালা করে অল্প সময় (time slice) দেয় — A, তারপর B, তারপর C, তারপর আবার A-র পালা। এই পদ্ধতির নাম round-robin scheduling, আর অপেক্ষমাণ প্রোগ্রামগুলোকে circular list-এ রাখা খুব স্বাভাবিক: “পরের জন” মানে শুধু cur = cur->next, শেষে পৌঁছে আলাদা করে শুরুতে ফেরার নিয়ম লাগে না। কোনো প্রোগ্রাম শেষ হলে তার node O(1)-এ বাদ। চায়ের দোকানে কয়েকজন বন্ধু পালা করে বিল দিলে যেমন — “এবার কার পালা” গোনা চক্রাকারেই চলে।

Josephus problem. একটি পুরোনো ধাঁধা, ইতিহাসবিদ Flavius Josephus-এর নামে: n জন মানুষ বৃত্তে দাঁড়িয়ে। ১ থেকে গোনা শুরু; প্রতি k-তম জন বৃত্ত থেকে বেরিয়ে যান, আর গোনা চলে পরের জন থেকে। শেষে কে টিকে থাকবেন? n = 7, k = 3 হলে বেরোনোর ক্রম 3, 6, 2, 7, 5, 1 — টিকে থাকেন ৪ নম্বর। circular list-এ এটি হুবহু অনুকরণ করা যায়: k − 1 ধাপ এগোন, পরের node মুছুন, আবার। মোট সময় Θ(n·k).

কিন্তু এখানে অ্যালগরিদমিক চিন্তা আরও ভালো উত্তর দেয়। 0 থেকে নম্বর দিলে, n জনের বৃত্তে বিজয়ীর অবস্থান J(n) মেনে চলে J(1) = 0 আর J(n) = (J(n − 1) + k) mod n — কারণ প্রথম জন বেরোনোর পর বাকি n − 1 জনের সমস্যাটি একই, শুধু নম্বরগুলো k ঘর সরে গেছে। এতে সময় Θ(n), কোনো list ছাড়াই। n = 7, k = 3-এ: J = 0, 1, 1, 0, 3, 0, 3 → 0-based 3 মানে ৪ নম্বর জন — অনুকরণের সাথে মিলে গেল।

def josephus(n, k):          # 1-based survivor, Theta(n) time, O(1) space
    j = 0                    # J(1) = 0
    for m in range(2, n + 1):
        j = (j + k) % m      # J(m) = (J(m-1) + k) mod m
    return j + 1

print(josephus(7, 3))        # 4

৬ · Array বনাম linked list — কাগজে এক, বাস্তবে আরেক

এবার দুটিকে মুখোমুখি দাঁড় করাই। নিচের সারণিতে n = উপাদানের সংখ্যা; “জায়গা জানা” মানে সংশ্লিষ্ট node বা index আগে থেকেই হাতে।

সারণি দেখে মনে হতে পারে, যেখানে অনেক insert/delete, সেখানে linked list-ই সেরা। বাস্তবে প্রায়ই উল্টো। কারণ দুটি।

(১) Cache locality. আধুনিক CPU মেমরি থেকে একটি একটি byte আনে না — একসাথে একটি পুরো “cache line” (সাধারণত 64 byte) আনে, আর প্যাটার্ন বুঝে পরের অংশও আগেভাগে আনতে থাকে (prefetch). vector-এ পাশাপাশি 16টি int এক cache line-এ চলে আসে, তাই traversal উড়ে চলে। linked list-এর প্রতিটি node মেমরির অন্য কোথাও; প্রতিটি cur = cur->next হতে পারে একটি cache miss, যার খরচ cache থেকে পড়ার চেয়ে প্রায় শত গুণ বেশি হতে পারে। আর পরের node-এর ঠিকানা আগের node পড়ার আগে জানাই যায় না, তাই CPU আগেভাগে আনতেও পারে না। দুটিই O(n), কিন্তু ধ্রুবকে বিশাল পার্থক্য।

(২) Memory overhead. 64-bit মেশিনে 4 byte-এর একটি int রাখতে singly node-এ লাগে 4 + 4 (padding) + 8 (pointer) = 16 byte, আর glibc-এর মতো সাধারণ allocator প্রতিটি ছোট বরাদ্দে নিজের হিসাবের জন্যও জায়গা নেয় — বাস্তবে প্রায়ই প্রতি node-এ 32 byte. অর্থাৎ ডেটার ৮ গুণ মেমরি! আর প্রতিটি new নিজেও একটি তুলনামূলক ধীর কাজ।

এজন্য C++-এর স্রষ্টা Bjarne Stroustrup-সহ অনেক বিশেষজ্ঞ পরামর্শ দেন: ডিফল্ট হিসেবে vector নিন; linked list নিন তখনই, যখন মাপজোক করে প্রমাণ পেয়েছেন। Stroustrup একটি বক্তৃতায় দেখিয়েছিলেন, sorted ক্রম বজায় রেখে এলোমেলো জায়গায় উপাদান ঢোকানো আর মোছার পরীক্ষায় vector, list-কে বড় ব্যবধানে হারায় — কারণ “জায়গা খুঁজতে” দুটিকেই হাঁটতে হয়, আর হাঁটায় vector অনেক দ্রুত।

তাহলে linked list কখন সত্যিই সঠিক পছন্দ?

• উপাদানের ঠিকানা বা iterator বদলানো চলবে না — অন্য অনেক জায়গা থেকে node-কে সরাসরি দেখানো হচ্ছে (LRU cache, OS-এর process তালিকা)।
• node হাতে রেখে O(1)-এ মাঝখান থেকে মোছা বা পুরো list জোড়া (splice) দরকার, আর হাঁটার দরকার কম।
• প্রতিটি উপাদান বিশাল, সরানো খুব খরুচে; অথবা real-time সিস্টেমে vector-এর হঠাৎ resize-এর বিরতি সহ্য করা যায় না।
• গ্রাফের adjacency list, hash table-এর chaining, memory allocator-এর free list — যেখানে অনেকগুলো ছোট তালিকা দরকার (পর্ব ৩২, ৩৯)।

৭ · মেমরির দায়িত্ব — C++-এ new/delete, Python-এ garbage collector

Linked list-এর প্রতিটি node আলাদা করে heap থেকে নেওয়া। কে এই মেমরি ফেরত দেবে? এখানে C++ আর Python দুটি সম্পূর্ণ আলাদা দর্শন মেনে চলে।

C++-এ পুরো list মুছে ফেলার সঠিক উপায় একটি লুপ — প্রতিটি node মোছার আগে তার next ধরে রাখতে হবে, কারণ মোছার পরে সেই node-এর ভেতরে পড়া নিষেধ:

void destroy(Node* head) {
    while (head) {
        Node* nxt = head->next;   // save first: after delete, head->next is gone
        delete head;
        head = nxt;
    }
}
// WRONG: for (Node* c = head; c; c = c->next) delete c;   // reads c->next after delete

আধুনিক C++ এই দায়িত্ব অনেকটা কমায় smart pointer দিয়ে। std::unique_ptr<Node> next; লিখলে প্রতিটি node তার পরের node-এর “মালিক”, আর node ধ্বংস হলে সে নিজে থেকেই পরেরটিকে মুছে দেয় — delete লেখার দরকার নেই, leak অসম্ভব। তবে একটি ফাঁদ আছে: এই মোছা রিকার্সিভভাবে ঘটে (node 1-এর destructor ডাকে node 2-এরটি, সেটি node 3-এরটি…)। দশ লাখ node-এর list-এ সেটি দশ লাখ গভীর রিকার্শন — stack overflow (পর্ব ০৭)। তাই unique_ptr-ভিত্তিক list-এও destructor-এ একটি লুপ লিখে node-গুলো একে একে ছেড়ে দেওয়া হয়।

Python-এ head = None লিখলেই প্রথম node-এর reference count শূন্য হয়, সে মুছে যায়, তার ফলে দ্বিতীয়টির count শূন্য… পুরো শিকল ভেঙে পড়ে। কিন্তু list-এ যদি cycle থাকে (শেষ node আবার আগের কোনো node দেখায়), তাহলে প্রতিটি node-কে অন্তত একজন দেখাচ্ছে — reference count কখনো শূন্য হয় না। এই ক্ষেত্রেই CPython-এর cycle collector (gc মডিউল) কাজে আসে: সে পর্যায়ক্রমে খোঁজে, কোন বস্তুর দল বাইরে থেকে আর পৌঁছানো যায় না, আর পুরো দলটিকে মুছে দেয়।

৮ · ক্লাসিক সমস্যা — উল্টানো, মাঝখান, merge আর শেষ থেকে n-তম

List উল্টানো — তিনটি pointer

“একটি singly linked list উল্টে দিন” — সম্ভবত সবচেয়ে বিখ্যাত linked list ইন্টারভিউ প্রশ্ন। নতুন list না বানিয়ে, O(1) বাড়তি জায়গায় (in-place) করতে হবে। মূল চিন্তা: প্রতিটি node-এর তীর ঘুরিয়ে আগের node-এর দিকে করে দিন। সমস্যা একটাই — তীর ঘোরালেই সামনের অংশের ঠিকানা হারিয়ে যায়। তাই তিনটি pointer: prev (উল্টানো অংশের মাথা), cur (এখন যে node), nxt (ঘোরানোর আগে বাঁচিয়ে রাখা বাকি অংশ)।

1Node* reverse(Node* head) {2    Node* prev = nullptr;3    Node* cur = head;4    while (cur != nullptr) {5        Node* nxt = cur->next;   // 1) save the rest6        cur->next = prev;        // 2) flip the arrow7        prev = cur;              // 3) move prev8        cur = nxt;               // 4) move cur9    }10    return prev;                 // prev is the new head11}

শুদ্ধতার যুক্তি। লুপের প্রতিটি ঘূর্ণনের শুরুতে সত্য থাকে: “মূল list-এর প্রথম i টি node উল্টো ক্রমে prev থেকে শুরু হয়ে null-এ শেষ, আর বাকি node-গুলো মূল ক্রমে cur থেকে শুরু।” শুরুতে i = 0 (prev = null, cur = head) — সত্য। এক ঘূর্ণনে cur-এর node উল্টানো অংশের সামনে যায় — i + 1-এর জন্যও সত্য। লুপ শেষে cur = null, অর্থাৎ বাকি অংশ খালি, তাই prev থেকে পুরো list উল্টো ক্রমে। এটিই পর্ব ০৩-এর loop invariant-এর পদ্ধতি।

রিকার্সিভ সংস্করণ। পর্ব ০৭-এর leap of faith দিয়ে ভাবুন: “head-এর পরের অংশটি উল্টে দেবে রিকার্সিভ কল; আমার কাজ শুধু head-কে তার শেষে জোড়া।” উল্টানোর পর পুরোনো head->next node-টি হয়ে গেছে উল্টানো অংশের শেষ node, তাই তার next-এ head বসালেই হলো:

Node* reverseRec(Node* head) {
    if (!head || !head->next) return head;    // 0 or 1 node: already reversed
    Node* newHead = reverseRec(head->next);   // leap of faith: the rest is reversed
    head->next->next = head;                  // old second node now points back to head
    head->next = nullptr;                     // head becomes the last node
    return newHead;
}

সুন্দর, কিন্তু বাড়তি জায়গা O(1) নয় — recursion depth n, তাই call stack-এ Θ(n). লাখখানেক node-এর list-এ C++-এ stack overflow-এর ঝুঁকি, আর Python-এ ১০০০-এর বেশি node হলেই RecursionError. ইন্টারভিউতে দুটিই জানতে চাওয়া হয়, আর সাথে এই জায়গার পার্থক্যও।

মাঝখান খোঁজা — slow আর fast pointer

দৈর্ঘ্য না জেনে এক পাসে মাঝের node বের করতে চাই। কৌশল: দুটি pointer একসাথে head থেকে ছাড়ুন — slow প্রতি ধাপে এক node, fast দুই node. fast যখন শেষে পৌঁছায়, slow তখন ঠিক অর্ধেক পথে। একে বলে fast-slow pointer কৌশল (two pointer-এর একটি রূপ, পর্ব ১৬)।

Node* middle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {       // fast can take two more steps
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;   // n odd: the middle; n even: the second of the two middles
}

1 → 2 → 3 → 4 → 5-এ slow যায় 1, 2, 3 আর fast 1, 3, 5 — থামে, slow = 3. 1 → … → 6-এ slow 1, 2, 3, 4 আর fast 1, 3, 5, null — slow = 4, দুটি মাঝের দ্বিতীয়টি। প্রথমটি চাইলে শর্ত লিখুন fast->next && fast->next->next. সময় Θ(n), জায়গা O(1). merge sort-কে linked list-এ চালাতে (list দুই ভাগ করতে) ঠিক এই ফাংশনই লাগে।

দুটি sorted list জোড়া (merge)

পরীক্ষার খাতা দুই শিক্ষক আলাদা করে রোল নম্বর অনুযায়ী সাজিয়েছেন; এখন দুটি গাদা মিলিয়ে একটি সাজানো গাদা চাই। দুই গাদার ওপরের খাতা তুলনা করুন, ছোটটি নতুন গাদায় দিন, আবার — এভাবে। linked list-এ কোনো নতুন node বানাতে হয় না: শুধু তীর জুড়ে জুড়ে নতুন ক্রম তৈরি হয়। dummy head আবার কাজে আসে — শুরুতে “নতুন list-এর প্রথম node কোনটি” নিয়ে আলাদা শাখা লাগে না।

Node* merge(Node* a, Node* b) {              // a and b are sorted
    Node dummy{0, nullptr};
    Node* tail = &dummy;
    while (a && b) {
        Node*& smaller = (a->val <= b->val) ? a : b;   // reference to a or b
        tail->next = smaller;                // link it
        tail = smaller;
        smaller = smaller->next;             // advance that list
    }
    tail->next = a ? a : b;                  // attach whatever is left
    return dummy.next;
}

প্রতিটি ধাপে একটি node নতুন list-এ যায়, তাই সময় Θ(n + m), বাড়তি জায়গা O(1). <= ব্যবহারে সমান মানে a-এর node আগে আসে — ফলে ক্রম stable থাকে (পর্ব ২৫)। এটিই পর্ব ২১-এর merge sort-এর merge ধাপ; linked list-এ merge sort O(n log n) সময়ে চলে, আর array-র মতো বাড়তি O(n) জায়গাও লাগে না — তাই linked list sort করার জন্য এটিই পছন্দের অ্যালগরিদম।

শেষ থেকে n-তম node মোছা — এক পাসে

দৈর্ঘ্য জানলে সহজ: L − n + 1 তম node মুছুন — কিন্তু তাতে দুটি পাস লাগে। এক পাসে করতে আবার দুটি pointer: fast-কে আগে n ঘর এগিয়ে দিন, তারপর দুজনকে একসাথে চালান। fast যখন শেষ node-এ, slow তখন ঠিক মুছতে-চাওয়া node-এর আগের node-এ — কারণ দুজনের ব্যবধান সবসময় n. dummy থেকে শুরু করলে “head নিজেই মুছতে হবে” (n = L) ক্ষেত্রটিও আলাদা করে ভাবতে হয় না।

Node* removeNthFromEnd(Node* head, int n) {   // assumes 1 <= n <= length
    Node dummy{0, head};
    Node *fast = &dummy, *slow = &dummy;
    for (int i = 0; i < n; ++i) fast = fast->next;   // open a gap of n
    while (fast->next) { fast = fast->next; slow = slow->next; }
    Node* t = slow->next;                     // the n-th node from the end
    slow->next = t->next;
    delete t;
    return dummy.next;
}

যাচাই: 1 → 2 → 3 → 4 → 5, n = 2. ফাঁক তৈরির পর fast = [2], slow = dummy. একসাথে চলে fast [3], [4], [5]; slow [1], [2], [3]. fast-এর next null — থামুন। slow = [3], মুছবে [4] — শেষ থেকে দ্বিতীয়। ✔ n = 5 হলে fast = [5], লুপ একবারও চলে না, slow = dummy, মুছবে [1] = head — dummy ছাড়া এখানেই ভুল হতো। সময় Θ(L), জায়গা O(1).

৯ · Floyd-এর cycle detection — কচ্ছপ আর খরগোশ

ধরুন কোনো বাগের কারণে একটি list-এর শেষ node null-এর বদলে আগের কোনো node দেখাচ্ছে। এখন traversal কখনো থামবে না। প্রশ্ন: list-এ cycle আছে কি না, আর থাকলে কোন node থেকে শুরু?

সহজ উপায়: দেখা প্রতিটি node-এর ঠিকানা একটি hash set-এ রাখুন; কোনো ঠিকানা দ্বিতীয়বার এলে সেটিই cycle-এর শুরু। সময় O(n), কিন্তু জায়গাও O(n). Robert W. Floyd-এর নামে পরিচিত একটি অসাধারণ কৌশল একই কাজ করে মাত্র দুটি pointer দিয়ে — Floyd's cycle detection, ডাকনাম “কচ্ছপ আর খরগোশ” (tortoise and hare). slow (কচ্ছপ) এক ধাপে চলে, fast (খরগোশ) দুই ধাপে। cycle না থাকলে fast null-এ পৌঁছায়। cycle থাকলে দুজনেই একসময় চক্রে ঢোকে, আর দৌড়ের মাঠে দ্রুততর দৌড়বিদ যেমন একসময় ধীরজনকে “এক চক্কর পেছন থেকে” ধরে ফেলেন, fast-ও slow-কে ধরে ফেলে।

নিচের list: 1 → 2 → 3 → 4 → 5 → 6, আর 6-এর next আবার 3. cycle-এর আগের লেজের দৈর্ঘ্য μ = 2 (node 1, 2), cycle-এর দৈর্ঘ্য λ = 4 (node 3, 4, 5, 6).

1Node* cycleStart(Node* head) {2    Node *slow = head, *fast = head;3    while (fast && fast->next) {4        slow = slow->next;          // 1 step5        fast = fast->next->next;    // 2 steps6        if (slow == fast) {         // they met inside the cycle7            slow = head;            // phase 2: slow back to head8            while (slow != fast) { slow = slow->next; fast = fast->next; }9            return slow;            // the first node of the cycle10        }11    }12    return nullptr;                 // fast fell off the end: no cycle13}

কেন দেখা হয়, আর কেন শুরুতেই দেখা হয় — প্রমাণের রূপরেখা

ধরি লেজের দৈর্ঘ্য μ (head থেকে cycle-এর প্রথম node পর্যন্ত ধাপ) আর cycle-এর দৈর্ঘ্য λ. t ধাপ পরে slow আছে head থেকে t ধাপ দূরে, fast আছে 2t ধাপ দূরে (cycle-এর ভেতরে ঘুরে ঘুরে)।

1. দেখা হবেই। t ≥ μ হলে দুজনেই চক্রে। চক্রের ভেতরে দুটি অবস্থান এক হয় ঠিক তখন, যখন তাদের দূরত্বের পার্থক্য λ-এর গুণিতক: 2t − t = t ≡ 0 (mod λ). অর্থাৎ যে প্রথম t ≥ μ, যা λ দিয়ে বিভাজ্য, সেখানেই দেখা। এমন t সবসময় আছে, আর t ≤ μ + λ − 1 ≤ n. অন্যভাবে: চক্রে ঢোকার পর ব্যবধান প্রতি ধাপে ১ কমে, তাই সর্বোচ্চ λ − 1 ধাপে শূন্য হয়।
2. শুরুটা কেন পাওয়া যায়। মিলনের মুহূর্তে t = mλ (কোনো পূর্ণসংখ্যা m ≥ 1-এর জন্য)। এবার slow-কে head-এ ফেরত পাঠিয়ে দুজনকে এক ঘর করে চালাই। μ ধাপ পরে slow ঠিক cycle-এর প্রথম node-এ। fast তখন head থেকে t + μ = mλ + μ ধাপ দূরের অবস্থানে — অর্থাৎ cycle-এর শুরু থেকে আরও mλ ধাপ, মানে m বার পুরো চক্কর দিয়ে আবার শুরুর node-এই। দুজন প্রথমবার সেখানেই মেলে, কারণ μ-এর আগে slow লেজে আর fast চক্রে — আলাদা জায়গায়।
3. খরচ। পর্যায় ১-এ সর্বোচ্চ μ + λ ধাপ, পর্যায় ২-এ μ ধাপ — মোট O(μ + λ) = O(n) সময়। জায়গা শুধু দুটি pointer: O(1).

ওপরের উদাহরণে মিলিয়ে দেখুন: μ = 2, λ = 4. প্রথম t ≥ 2 যা 4 দিয়ে বিভাজ্য: t = 4 — ঠিক ধাপ ৪-এ মিলন। তারপর পর্যায় ২-এ μ = 2 ধাপে [3]. এবার পুরো প্রোগ্রাম চালিয়ে দেখুন: list তৈরি, ছাপা, উল্টানো, আর দুটি list-এ cycle খোঁজা:

#include <iostream>
#include <vector>
using namespace std;

struct Node { int val; Node* next = nullptr; };

Node* build(const vector<int>& xs, vector<Node*>& pool) {  // pool owns every node
    Node dummy{0}, *tail = &dummy;                         // dummy head: no special case
    for (int x : xs) { pool.push_back(new Node{x}); tail = tail->next = pool.back(); }
    return dummy.next;
}
void print(const Node* h) {
    for (; h; h = h->next) cout << h->val << " -> ";
    cout << "null\n";
}
Node* reverse(Node* cur) {                                 // O(n) time, O(1) extra space
    Node* prev = nullptr;
    while (cur) { Node* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; }
    return prev;
}
Node* cycleStart(Node* h) {                                // Floyd; nullptr = no cycle
    Node *slow = h, *fast = h;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {                                // met: restart slow from head
            for (slow = h; slow != fast; slow = slow->next) fast = fast->next;
            return slow;
        }
    }
    return nullptr;
}
int main() {
    vector<Node*> pool;
    Node* h = build({1, 2, 3, 4, 5}, pool);
    print(h);
    h = reverse(h);
    print(h);
    cout << "cycle? " << (cycleStart(h) ? "yes" : "no") << '\n';
    Node* c = build({1, 2, 3, 4, 5, 6}, pool);
    pool.back()->next = c->next->next;                     // 6 -> 3 makes a cycle
    cout << "cycle starts at " << cycleStart(c)->val << '\n';
    for (Node* p : pool) delete p;                         // free each node exactly once
}

1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
cycle? no
cycle starts at 3

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def build(xs):
    dummy = tail = Node(0)                 # dummy head: no special case
    for x in xs:
        tail.next = tail = Node(x)         # link the new node, then move tail
    return dummy.next

def show(h):
    vals = []
    while h:
        vals.append(str(h.val)); h = h.next
    print(" -> ".join(vals + ["null"]))

def reverse(cur):                          # O(n) time, O(1) extra space
    prev = None
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

def cycle_start(h):                        # Floyd; None = no cycle
    slow = fast = h
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                   # met: restart slow from head
            slow = h
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

h = build([1, 2, 3, 4, 5])
show(h)
h = reverse(h)
show(h)
print("cycle?", "yes" if cycle_start(h) else "no")
c = build([1, 2, 3, 4, 5, 6])
last = c.next.next.next.next.next          # node 6
last.next = c.next.next                    # 6 -> 3 makes a cycle
print("cycle starts at", cycle_start(c).val)

1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
cycle? no
cycle starts at 3

নিজে হাতে চালিয়ে দেখুন

নিচের ছোট টুলটিতে “চালিয়ে দেখুন” চাপুন। একটি সংখ্যা লিখে বোতাম চাপলে list-এ সেটি শুরুতে বা শেষে যোগ হবে, মুছে যাবে, পুরো list উল্টে যাবে, বা slow/fast দিয়ে মাঝের node লাল হয়ে জ্বলে উঠবে। শেষে যোগ করার সময় “steps” সংখ্যাটি খেয়াল করুন — list যত লম্বা, তত বেশি।

// A small singly linked list, drawn as boxes and arrows
class LNode { constructor(val, next = null) { this.val = val; this.next = next; } }
let lhead = null, mark = null;
const $ = id => document.getElementById(id);
const toText = () => { const a = []; for (let c = lhead; c; c = c.next) a.push(c.val); return a.concat("null").join(" -> "); };
function show(msg) {
  let h = "head →";
  for (let c = lhead; c; c = c.next)
    h += ` <span class="nd${c === mark ? " hl" : ""}"><b>${c.val}</b><i>•</i></span> →`;
  $("vw").innerHTML = h + " null";
  $("msg").textContent = msg;
  console.log(msg.padEnd(22) + toText());
}
function pushFront(v) { lhead = new LNode(v, lhead); mark = lhead; show(`pushFront(${v}): 1 step`); }
function pushBack(v) {
  const dummy = new LNode(0, lhead); let t = dummy, steps = 0;
  while (t.next) { t = t.next; steps++; }
  t.next = mark = new LNode(v); lhead = dummy.next; show(`pushBack(${v}): ${steps} steps`);
}
function removeVal(v) {
  const dummy = new LNode(0, lhead); let p = dummy;
  while (p.next && p.next.val !== v) p = p.next;
  const ok = p.next !== null; if (ok) p.next = p.next.next;
  lhead = dummy.next; mark = null; show(`remove(${v}): ${ok ? "done" : "not found"}`);
}
function reverseAll() {
  let prev = null, cur = lhead;
  while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
  lhead = prev; mark = null; show("reverse():");
}
function middle() {
  let slow = lhead, fast = lhead;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  mark = slow; show(`middle(): ${slow ? slow.val : "none"}`);
}
const num = () => Number($("val").value);
$("bf").onclick = () => pushFront(num()); $("bb").onclick = () => pushBack(num());
$("bd").onclick = () => removeVal(num()); $("br").onclick = reverseAll; $("bm").onclick = middle;
for (const v of [30, 20, 10]) pushFront(v);
pushBack(40); pushBack(50); middle(); removeVal(30); reverseAll();

pushFront(30): 1 step 30 -> null
pushFront(20): 1 step 20 -> 30 -> null
pushFront(10): 1 step 10 -> 20 -> 30 -> null
pushBack(40): 3 steps 10 -> 20 -> 30 -> 40 -> null
pushBack(50): 4 steps 10 -> 20 -> 30 -> 40 -> 50 -> null
middle(): 30          10 -> 20 -> 30 -> 40 -> 50 -> null
remove(30): done      10 -> 20 -> 40 -> 50 -> null
reverse():            50 -> 40 -> 20 -> 10 -> null

১০ · AI-এর যুগে linked list — তীর এঁকে যাচাই করুন

Linked list-এর কোড ছোট, তাই AI মুহূর্তে লিখে দেয় — আর প্রায়ই সুন্দর উদাহরণে চলেও। কিন্তু linked list-এর বাগ লুকিয়ে থাকে ঠিক সেই জায়গায়, যেখানে উদাহরণ পৌঁছায় না: খালি list, এক node-এর list, head মোছা, শেষ node, আর cycle. তাছাড়া এখানে একটি pointer-এর ভুল ক্রম পুরো list হারিয়ে দেয়, অথচ ছোট পরীক্ষায় সেটি ধরা পড়ে না।

Linked list-এ AI সাধারণত যেসব ভুল করে

Linked list কোড যাচাইয়ের চেকলিস্ট

• খালি list, এক node আর দুই node-এর list দিয়ে চালিয়েছি
• head বদলায় এমন ক্ষেত্র (head মোছা, শুরুতে যোগ) আলাদা করে পরীক্ষা করেছি — বা dummy head ব্যবহার করেছি
• প্রতিটি pointer লেখার আগে ভেবেছি: এই লাইনের পরে কোনো node-এর ঠিকানা কি হারিয়ে যাচ্ছে?
• C++-এ প্রতিটি new-এর জন্য ঠিক একটি delete আছে; sanitizer দিয়ে চালিয়েছি
• দাবি করা complexity-র সাথে লুপ আর রিকার্শনের গভীরতা মিলিয়েছি
• ছোট এলোমেলো ইনপুটে একই কাজ Python-এর সাধারণ list (বা C++-এর vector) দিয়ে করে ফল মিলিয়ে stress testing করেছি