লিংকড লিস্ট — মেমরিতে ছড়ানো ঘর, পয়েন্টারে বাঁধা শিকল

১ · Array-র দুই সমস্যা — বাঁধা আকার, মাঝে ঢোকানোর খরচ

নতুন মডিউলে স্বাগতম। এই মডিউলে আমরা একে একে কয়েকটি মৌলিক ডেটা স্ট্রাকচার নিজ হাতে C-তে বানাব — linked list, stack, queue, tree, heap, hash table, graph. আমাদের নজর থাকবে মেমরিতে আসলে কী ঘটছে আর pointer কীভাবে নড়ছে, সেই দিকে। অ্যালগরিদমের আরও গভীর আলোচনা চাইলে ABCL TECH-এর আলাদা Data Structures & Algorithms কোর্স আছে; এই পর্বগুলো তার ভিত্তি গড়ে দেবে।

শুরু করি একটি পরিচিত জিনিস দিয়ে — array (পর্ব ১৬). Array-র ঘরগুলো মেমরিতে গায়ে গায়ে লাগানো (contiguous memory), তাই marks[7] সরাসরি এক লাফে পাওয়া যায়। এটি array-র সবচেয়ে বড় শক্তি। কিন্তু দুটি জায়গায় সে আটকে যায়।

প্রথম সমস্যা — আকার বাঁধা। int marks[50]; লিখলে ৫০টির বেশি ঘর পাবেন না। ক্লাসে ৫১তম ছাত্র এলে? পর্ব ২০-এ দেখেছেন, dynamic array realloc করে বড় হতে পারে — কিন্তু তখন পুরো ব্লক নতুন জায়গায় কপি হতে পারে, আর পুরোনো সব pointer অচল হয়ে যায়।

দ্বিতীয় সমস্যা — মাঝে ঢোকানো। ধরুন রোল নম্বর অনুযায়ী সাজানো নম্বরের তালিকা: [55, 64, 85, 90]. এখন 70 বসাতে চান 64-এর পরে। Array-তে ফাঁকা জায়গা বানাতে 85 আর 90 — দুজনকেই এক ঘর ডানে সরাতে হবে:

আগে :  [55] [64] [85] [90] [  ]
সরানো:  [55] [64] [  ] [85] [90]    <- 85, 90 এক ঘর করে ডানে
পরে :  [55] [64] [70] [85] [90]

তাহলে উল্টো চিন্তা করি: যদি ঘরগুলোকে পাশাপাশি বসিয়ে রাখার বাধ্যবাধকতাই না থাকে? প্রত্যেকে যেখানে খুশি বসুক, শুধু জানুক তার পরে কে আছে। তাহলে নতুন কাউকে মাঝে বসাতে কাউকেই সরতে হবে না — শুধু দুজনের “পরে কে” তথ্যটা বদলালেই হলো। এই চিন্তাটির নামই linked list.

২ · Linked list — ছড়ানো ঘর, ঠিকানার শিকল

Linked list-এর প্রতিটি ঘরকে বলে node. প্রতিটি node-এ দুটি জিনিস থাকে: ডেটা (যেমন একটি নম্বর) আর পরের node-এর ঠিকানা — একটি pointer, যার নাম সাধারণত next. Node-গুলো heap-এর যেখানে জায়গা পাওয়া গেছে সেখানেই থাকে; একটি আরেকটির পাশে থাকার কোনো দরকার নেই।

আরেকটি ছবি: রেলগাড়ির বগি। প্রতিটি বগি শুধু তার পরের বগির সাথে হুকে আটকানো। মাঝে একটি নতুন বগি জুড়তে পুরো ট্রেন ভাঙতে হয় না — একটি হুক খুলে নতুন বগিকে দুই পাশে লাগালেই হয়।

C-তে node দেখতে কেমন

struct Node {
    int marks;            /* ডেটা */
    struct Node *next;    /* পরের node-এর ঠিকানা, না থাকলে NULL */
};

struct Node *head = NULL; /* খালি তালিকা */

খেয়াল করুন, struct Node-এর ভেতরে আছে struct Node * — নিজের টাইপেরই একটি pointer. একে বলে self-referential struct. ভেতরে পুরো struct Node রাখা সম্ভব নয় (তাহলে struct-টি অসীম বড় হয়ে যেত), কিন্তু তার ঠিকানা রাখা যায়, কারণ যেকোনো pointer-এর আকার নির্দিষ্ট — ৬৪-বিট কম্পিউটারে সাধারণত ৮ byte (পর্ব ২২-এর struct মনে করুন)।

এই ধরনের তালিকায় প্রতিটি node কেবল সামনের দিকে চেনে, তাই একে বলে singly linked list. পেছনের দিকেও চেনে এমন তালিকা পরে দেখব (অংশ ৭)।

৩ · Node বানানো আর তালিকা ঘুরে দেখা

প্রতিটি node তৈরি হয় চলার সময়, malloc দিয়ে heap থেকে জায়গা নিয়ে (পর্ব ২০). তারপর তাকে তালিকায় জোড়া হয়। সবচেয়ে সহজ জায়গা হলো শুরুতে জোড়া — মাত্র দুটি লাইন:

n->next = head;   /* ১: নতুন node এখনকার প্রথম node-কে ধরল */
head = n;         /* ২: head এবার নতুন node-কে দেখায় */

এখানে n->next হলো arrow operator — “n যে struct-কে দেখায়, তার next”. তালিকা খালি থাকলেও এই দুই লাইন ঠিক কাজ করে: তখন head ছিল NULL, তাই নতুন node-এর next হয় NULL — সেটিই একমাত্র এবং শেষ node. এমন কোড ভালো, যেখানে খালি তালিকার জন্য আলাদা if লাগে না।

পুরো তালিকা একে একে ঘুরে দেখাকে বলে traversal. একটি অস্থায়ী pointer p নিয়ে head থেকে শুরু করুন, প্রতি ধাপে p = p->next, আর NULL-এ পৌঁছালে থামুন। খেয়াল করুন — head-কে নিজে কখনো সরাবেন না, সরাবেন শুধু p-কে। নিচের প্রোগ্রামটি তিনটি নম্বর দিয়ে তালিকা বানায়, ছাপে, তারপর প্রতিটি node free করে:

#include <stdio.h>
#include <stdlib.h>
struct Node { int marks; struct Node *next; };
int main(void) {
    struct Node *head = NULL;  int marks[] = {64, 85, 72};
    for (int i = 0; i < 3; i++) {        /* each new node goes to the front */
        struct Node *n = malloc(sizeof *n);
        if (n == NULL) break;            /* no memory: stop adding */
        n->marks = marks[i];
        n->next = head;                  /* 1: new node holds the old first node */
        head = n;                        /* 2: head moves to the new node */
    }
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->marks);
    printf("NULL\n");
    while (head != NULL) {               /* free every node, one by one */
        struct Node *next = head->next;  /* save the address BEFORE free */
        free(head);
        head = next;
    }
    return 0;
}

শেষে যোগ করা — tail pointer-এর কৌশল

শুরুতে যোগ করা সস্তা, কিন্তু অনেক সময় ক্রম ঠিক রাখতে শেষে যোগ করতে হয় (যেমন লাইনে দাঁড়ানো মানুষের তালিকা)। শুধু head থাকলে শেষ node খুঁজতে প্রতিবার পুরো তালিকা হাঁটতে হয় — ১০ লাখ node থাকলে ১০ লাখ ধাপ। সমাধান: শেষ node-এর ঠিকানাও আলাদা করে রেখে দিন — tail pointer. তখন শেষে যোগ করা হয় মাত্র দুই ধাপে: tail->next = n; tail = n; (খালি তালিকায় head আর tail দুটোই n হবে — এই edge case ভুললে চলবে না)।

৪ · মাঝে নতুন node ঢোকানো — দুটি লাইন, ক্রমটাই আসল

এবার অংশ ১-এর সেই সমস্যা: 55 → 64 → 85 তালিকায় 64-এর পরে 70 বসাতে হবে। ধরুন prev নামের একটি pointer আগে থেকেই ৬৪-এর node-টিকে দেখাচ্ছে। Array-তে পরের সবাইকে সরাতে হতো; এখানে কাউকে সরাতে হবে না — বদলাবে মাত্র দুটি pointer. কিন্তু এই দুটি লাইনের ক্রম উল্টে গেলে কী হয়, সেটিও নিচে দেখুন:

1struct Node *n = malloc(sizeof *n);2n->marks = 70;3n->next = prev->next;   /* আগে */4prev->next = n;         /* পরে */56/* ভুল ক্রম হলে: */7prev->next = n;8n->next = prev->next;

৫ · Node মুছে ফেলা — আগে জোড়া, পরে free

মুছে ফেলাও pointer জোড়া বদলানোর খেলা: যে node মুছব, তার আগের node-কে সরাসরি তার পরের node-এর সাথে জুড়ে দিন। তারপর মোছা node-টির মেমরি free করে heap-এ ফেরত দিন। কিন্তু এখানেও ক্রম ভুল হলে বিপদ — আর সেই বিপদটি চোখে পড়ে না, তাই আরও ভয়ংকর।

1struct Node *dead = prev->next;2prev->next = dead->next;   /* জোড়া */3free(dead);                /* ফেরত */45/* ভুল ক্রম হলে: */6free(dead);7prev->next = dead->next;   /* free-র পরে ছোঁয়া! */

Head মুছতে হলে? — pointer to pointer-এর কৌশল

উপরের কোডে একটি ফাঁক আছে: প্রথম node (৫৫) মুছতে চাইলে তার কোনো prev নেই! তখন বদলাতে হবে head-কে নিজেই। সাধারণ সমাধানে দুটি আলাদা পথ লেখা হয় — “যদি head হয় তাহলে এটা, নইলে ওটা।” এখানেই AI ও নতুনরা সবচেয়ে বেশি ভুল করেন।

আরও সুন্দর একটি সমাধান আছে। মনে করুন head একটি pointer, আর প্রতিটি node-এর next-ও একটি pointer. মুছতে গিয়ে আমাদের আসলে বদলাতে হয় “যে pointer-টি এই node-কে দেখাচ্ছে” — সেটি head হোক বা কারো next. তাই আমরা হাতে রাখি সেই pointer-টির ঠিকানা, অর্থাৎ struct Node ** — pointer to pointer (পর্ব ১৭)। তখন head আর মাঝের node-এর জন্য একই কোড কাজ করে:

#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *next; };
void delete_value(struct Node **pp, int target) {
    while (*pp != NULL && (*pp)->val != target)
        pp = &(*pp)->next;              /* move to the next "link box" */
    if (*pp == NULL) return;            /* not found: do nothing */
    struct Node *dead = *pp;
    *pp = dead->next;                   /* 1: rewire around it */
    free(dead);                         /* 2: only then free */
}
int main(void) {
    struct Node *head = NULL;
    for (int v = 40; v >= 10; v -= 10) {          /* builds 10 20 30 40 */
        struct Node *n = malloc(sizeof *n);
        if (n == NULL) break;
        n->val = v; n->next = head; head = n;
    }
    delete_value(&head, 10);  delete_value(&head, 30);   /* head, then middle */
    for (struct Node *p = head; p != NULL; p = p->next) printf("%d ", p->val);
    printf("\n");
    while (head != NULL) delete_value(&head, head->val);  /* free all */
    return 0;
}

আরেকটি প্রচলিত উপায় হলো তালিকার শুরুতে একটি ফাঁকা পাহারাদার node রাখা — dummy node. তখন প্রতিটি আসল node-এর আগে সবসময় কেউ না কেউ থাকে, head-এর বিশেষ ক্ষেত্র উঠে যায়। Linux kernel-এর তালিকা ঠিক এভাবে বানানো (অংশ ৯)।

৬ · পুরো তালিকা free করা আর চারটি ক্লাসিক বাগ

প্রোগ্রাম শেষে, বা তালিকার আর দরকার না থাকলে, প্রতিটি node free করতে হবে। শুধু free(head) লিখলে প্রথম node ফেরত যায় — বাকি সব node heap-এ রয়ে যায়, অথচ তাদের ঠিকানা আর কারো কাছে নেই। নিরাপদ উপায়টি ধাপে ধাপে দেখুন:

1while (head != NULL) {2    struct Node *next = head->next;3    free(head);4    head = next;5}

Linked list-এর চারটি ক্লাসিক বাগ

৭ · দুই দিকের ও গোল তালিকা — doubly আর circular

Doubly linked list — পেছনের দিকেও চেনা

Singly list-এর একটি বড় অসুবিধা দেখেছেন: কোনো node মুছতে হলে তার আগের node লাগে, অথচ node নিজে জানে না তার আগে কে। সমাধান — প্রতিটি node-এ আরেকটি pointer যোগ করুন, prev. এই তালিকার নাম doubly linked list.

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

/* x-কে তালিকা থেকে খুলে ফেলা — আগের node খুঁজতে হয় না */
if (x->prev) x->prev->next = x->next; else head = x->next;
if (x->next) x->next->prev = x->prev;
free(x);

এখন হাতে শুধু node-টির ঠিকানা থাকলেই সাথে সাথে মুছে ফেলা যায় — খোঁজার দরকার নেই। দুই দিকেই হাঁটা যায়। দাম কী? প্রতি node-এ আরও একটি pointer (৬৪-বিটে ৮ byte বাড়তি), আর প্রতিটি ঢোকানো বা মুছে ফেলায় দুটির বদলে চারটি pointer ঠিক করতে হয় — ভুলের সুযোগও দ্বিগুণ। ব্রাউজারের Back/Forward বোতাম বা টেক্সট এডিটরের undo/redo-র ইতিহাস এই রকম দুই-দিকি তালিকার চেনা উদাহরণ।

Circular linked list — শেষ বলে কিছু নেই

শেষ node-এর next যদি NULL না হয়ে আবার প্রথম node-কে দেখায়, তাহলে পাওয়া যায় circular linked list. এখানে “শেষ” নেই — ঘুরে ঘুরে চলে।

৮ · খরচের হিসাব — কেন বাস্তবে array প্রায়ই জেতে

পাঠ্যবইয়ে প্রায়ই একটি সারণি থাকে, যা দেখে মনে হয় linked list দারুণ। সারণিটি ভুল নয়, কিন্তু অসম্পূর্ণ। এখানে time complexity-র ভাষায় লিখছি — O(1) মানে তালিকা যত বড়ই হোক সময় প্রায় একই, O(n) মানে সময় তালিকার আকারের সাথে বাড়ে (Big-O নিয়ে বিস্তারিত পর্ব ৩৯-এ)।

শেষ সারিটিই সবচেয়ে গুরুত্বপূর্ণ, অথচ অনেক বইয়ে থাকে না। পর্ব ১৬-এ দেখেছেন, CPU মেমরি থেকে একটি একটি byte আনে না, আনে একবারে একটি পুরো cache line (প্রায়ই ৬৪ byte). পাশাপাশি থাকা ডেটা তাই বিনা খরচে চলে আসে — একে বলে spatial locality. Linked list-এর node-গুলো ছড়ানো, তাই এই সুবিধা প্রায় পাওয়াই যায় না। নিচে দুটির মেমরি পাশাপাশি দেখুন:

ঠিকানা   0x1000  0x1004  0x1008  0x100C
        +-------+-------+-------+-------+
        |  72   |  85   |  64   |  90   |
        +-------+-------+-------+-------+
        |<------ একটি cache line (64 byte) ----->
        একবার RAM-এ গিয়েই চারজন একসাথে এলো

head = 0x5a20

0x3c40: [ 64 | next=0x7e10 ]   <- লাফ ৩ (নতুন cache line)
0x5a20: [ 72 | next=0x91f0 ]   <- শুরু (cache miss)
0x7e10: [ 90 | next=NULL   ]   <- লাফ ৪ (নতুন cache line)
0x91f0: [ 85 | next=0x3c40 ]   <- লাফ ২ (নতুন cache line)
পথ: 0x5a20 → 0x91f0 → 0x3c40 → 0x7e10 → NULL

৯ · বাস্তব সিস্টেমে linked list — kernel, cache, malloc

উপরের হিসাব দেখে মনে হতে পারে linked list বুঝি শুধু পরীক্ষার প্রশ্ন। মোটেই না। পৃথিবীর সবচেয়ে গুরুত্বপূর্ণ কিছু সফটওয়্যারের ভেতরে linked list কাজ করছে — শুধু ঠিক সেই জায়গাগুলোতে, যেখানে তার শক্তি কাজে লাগে।

Linux kernel-এর list_head — ডেটার ভেতরেই হুক

আমরা এতক্ষণ যে list বানিয়েছি, সেখানে node-এর ভেতরে ডেটা থাকে। Linux kernel উল্টোটা করে: ডেটার struct-এর ভেতরে একটি ছোট “হুক” বসিয়ে দেয়। include/linux/list.h ফাইলে সংজ্ঞাটি প্রায় এমন:

struct list_head { struct list_head *next, *prev; };

struct task {                 /* উদাহরণ: একটি প্রসেসের তথ্য */
    int pid;
    struct list_head run_list;   /* এই হুক দিয়ে "চলার অপেক্ষায়" তালিকায় */
    struct list_head all_list;   /* আর এটি দিয়ে "সব প্রসেস" তালিকায় */
};

এ ধরনের তালিকাকে বলে intrusive list — তালিকার pointer ডেটার ভেতরে “ঢুকে” থাকে। লাভ তিনটি: আলাদা node-এর জন্য বাড়তি malloc লাগে না; একটি struct একসাথে কয়েকটি তালিকায় থাকতে পারে (প্রতিটির জন্য একটি করে হুক); আর হুকের ঠিকানা হাতে থাকলে container_of macro দিয়ে পুরো struct-এর ঠিকানা বের করা যায় — হুকের ঠিকানা থেকে offsetof বিয়োগ করে। Kernel-এর তালিকাগুলো circular ও doubly, আর শুরুতে থাকে একটি ফাঁকা list_head — অর্থাৎ অংশ ৫-এর dummy node. তাই সেখানে খালি তালিকা বা head-এর আলাদা কোনো বিশেষ ক্ষেত্রই নেই।

LRU cache — hash table আর doubly list-এর জুটি

ফোনের গ্যালারি অ্যাপ সব ছবির ছোট সংস্করণ (thumbnail) মেমরিতে রাখতে পারে না। জায়গা ফুরালে কোনটি ফেলবে? যুক্তিসংগত উত্তর: যেটি সবচেয়ে বেশি সময় কেউ দেখেনি। এই নিয়মে চলা cache-কে বলে LRU cache (Least Recently Used). দুটি কাঠামো মিলিয়ে বানানো হয়:

• একটি hash table — key দিলে সরাসরি সেই জিনিসের node-এর ঠিকানা দেয় (খুঁজতে হাঁটতে হয় না)।
• একটি doubly linked list — সামনে সবচেয়ে সাম্প্রতিক, পেছনে সবচেয়ে পুরোনো।

কেউ একটি জিনিস চাইলে hash table node দেয়; doubly list বলে সেটিকে O(1)-এ খুলে সামনে নেওয়া যায়। জায়গা ফুরালে পেছনের node ফেলে দেওয়া হয়, এটিও O(1). এখানে linked list-এর দুর্বলতা (খোঁজা) hash table ঢেকে দিয়েছে, আর তার শক্তি (জানা জায়গায় সস্তায় সরানো) পুরো কাজে লাগছে। Memcached-এর মতো cache সার্ভার আর অনেক ডেটাবেস ইঞ্জিন এই ধরনের কাঠামো ব্যবহার করে। চাকরির ইন্টারভিউতেও “একটি LRU cache বানান” খুব পরিচিত প্রশ্ন।

malloc-এর ভেতরের free list

আপনি যখন free(p) করেন, মেমরি সাধারণত সাথে সাথে OS-এ ফেরত যায় না। Allocator সেই ফাঁকা block-গুলো নিজের কাছে একটি তালিকায় জমিয়ে রাখে — free list. মজার ব্যাপার: এই তালিকার next pointer আলাদা কোথাও থাকে না, থাকে ফাঁকা block-গুলোর নিজের ভেতরেই (block তো এখন ফাঁকা, জায়গাটা কাজে লাগানো যায়)। পরের malloc এলে allocator আগে এই তালিকা থেকে মাপমতো block খোঁজে। এ কারণেই অংশ ৫-এ বলেছিলাম — free করা node-এর next ঘরে allocator নিজের তথ্য লিখে ফেলতে পারে। use-after-free কেন এত অদ্ভুত আচরণ করে, এবার পুরো ছবিটা পরিষ্কার।

১০ · AI-এর যুগে linked list কোড যাচাই

“C-তে একটি linked list লিখে দাও” — AI কয়েক সেকেন্ডে লিখে দেবে, আর প্রথম দেখায় সেটি ঠিকই মনে হবে। সাধারণ ইনপুটে চালালে চলবেও। সমস্যা লুকিয়ে থাকে ঠিক সেই জায়গাগুলোতে, যেগুলো সাধারণ পরীক্ষায় ধরা পড়ে না: খালি তালিকা, এক-node তালিকা, প্রথম node, শেষ node.

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

AI-এর লেখা list কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• খালি তালিকায় (head == NULL) প্রতিটি ফাংশন চালিয়েছি — কোনো crash নেই
• এক-node তালিকায় সেই node মুছে দেখেছি — head শেষে NULL হয়েছে
• প্রথম node আর শেষ node আলাদা করে মুছে দেখেছি, তারপর আবার ছেপে মিলিয়েছি
• প্রতিটি free-এর পরে সেই pointer আর ছোঁয়া হয়নি — কোড পড়ে নিশ্চিত হয়েছি
• -fsanitize=address বা Valgrind-এ চালিয়েছি — leak শূন্য, use-after-free নেই
• কাগজে বাক্স আর তীর এঁকে অন্তত একটি ঢোকানো ও একটি মোছা হাতে মিলিয়েছি