#লিংকড লিস্ট #linked list bangla #ডাটা স্ট্রাকচার বাংলা #ডাবলি লিংকড লিস্ট #বাইনারি সার্চ ট্রি #পয়েন্টার #c++ ডাটা স্ট্রাকচার #অ্যারে বনাম লিংকড লিস্ট #প্রোগ্রামিং #অ্যালগরিদম #c++ #লিংকড লিস্ট #linked list #ডাটা স্ট্রাকচার #data structure #লিংকড লিস্ট বাংলা #linked list bangla #ডাবলি লিংকড লিস্ট #doubly linked list #সিঙ্গলি লিংকড লিস্ট #বাইনারি সার্চ ট্রি #binary search tree #পয়েন্টার #pointer #c++ #c programming #অ্যারে বনাম লিংকড লিস্ট #array vs linked list #টাইম কমপ্লেক্সিটি #big o #মার্জ সর্ট #lru cache #প্রোগ্রামিং শিক্ষা #বাংলা প্রোগ্রামিং টিউটোরিয়াল #কোডিং ইন্টারভিউ #competitive programming
লিংকড লিস্টঃ ট্রেজার হান্টের মতো করে ডাটা সাজানোর কৌশল
2026-09-21 · 35 min read

ছোটবেলায় ট্রেজার হান্ট খেলেছেন? প্রথম চিরকুটে লেখা থাকে "পরের সূত্র আছে ফ্রিজের নিচে"। ফ্রিজের নিচের চিরকুটে লেখা "এবার খোঁজো বালিশের ভেতর"। এভাবে এক সূত্র থেকে আরেক সূত্রে যেতে যেতে শেষে গুপ্তধন পাওয়া যায়। লিংকড লিস্ট (Linked List) ঠিক এভাবেই কাজ করে। প্রতিটা ঘরে থাকে কিছু তথ্য আর পরের ঘরের ঠিকানা। কোনো ঘর জানে না পুরো লিস্টে কী আছে। সে শুধু জানে তার পরে কে আছে। এই লেখায় যা থাকছে,
- লিংকড লিস্ট কী, আর অ্যারে থাকতে এটা কেন লাগে
- নোড যোগ করা, প্রিন্ট করা, মুছে ফেলা আর মাঝখানে বসানো
- ডাবলি লিংকড লিস্ট আর বাইনারি সার্চ ট্রি
- বাস্তবে কোথায় লিংকড লিস্ট ব্যবহার হয়, আর কোথায় এটা এড়ানো উচিত
- নতুনরা সাধারণত কোন ভুলগুলো করে
শুরুর আগে যা জানা থাকা দরকার
একদম নতুন হলে এই ক্রমে এগোলে সুবিধা হবেঃ
- ভেরিয়েবল, লুপ, কন্ডিশনঃ প্রোগ্রামিংয়ের একদম বেসিক
- ফাংশনঃ কোড ছোট ছোট অংশে ভাগ করা
- অ্যারেঃ একই ধরনের অনেক ডাটা একসাথে রাখা
- পয়েন্টারঃ এটাই সবচেয়ে জরুরি। পয়েন্টার না বুঝলে লিংকড লিস্ট বোঝা খুব কঠিন হবে
- struct: কয়েক রকম ডাটা মিলিয়ে নিজের একটা টাইপ বানানো
- টাইম কমপ্লেক্সিটি (Big O): কোড কত দ্রুত চলে তা মাপার উপায়
এগুলো জানা থাকলে পড়তে থাকুন। না থাকলে আগে পয়েন্টার শিখে আসুন। এই লেখা কোথাও চলে যাচ্ছে না।
অ্যারের সমস্যা কোথায়?
অ্যারের সব এলিমেন্ট মেমরিতে পাশাপাশি থাকে, সিনেমা হলের এক সারির সিটের মতো। প্রথম সিটের নম্বর জানলে ৫ নম্বর সিট কোথায় তা সাথে সাথে হিসাব করা যায়। নিচের কোডটা চালিয়ে দেখুনঃ
#include <cstdio>
int main() {
int a[5];
for (int i = 0; i < 5; i++) {
printf("a[%d] আছে এই ঠিকানায়ঃ %p\n", i, (void*)&a[i]);
}
return 0;
}
আউটপুটে দেখবেন প্রতিটা ঠিকানা আগেরটার চেয়ে ৪ বাইট করে বেশি, কারণ সাধারণত একটা int ৪ বাইট জায়গা নেয়। তাই i নম্বর এলিমেন্টের ঠিকানা হলোঃ
প্রথম এলিমেন্টের ঠিকানা + i × ৪
এই কারণেই অ্যারেতে a[1000] পড়তে এক ধাপই লাগে, অর্থাৎ O(1)। সমস্যা হয় যখন মাঝখান থেকে কাউকে সরাতে হয়। সিনেমা হলের মাঝের সিটের কেউ উঠে গেলে ফাঁকা ঘর রাখা যায় না, ডান পাশের সবাইকে এক সিট করে বামে সরতে হয়। ১০ লাখ এলিমেন্টের অ্যারেতে এটা বেশ খরচের কাজ।

লিংকড লিস্টের গঠনঃ নোড
লিংকড লিস্টের প্রতিটা ঘরকে বলে নোড (Node)। প্রতিটা নোডে দুটো জিনিস থাকেঃ
- ডাটাঃ যেটা রাখতে চাই, যেমন একজন ছাত্রের রোল
- next পয়েন্টারঃ পরের নোডটা মেমরির কোথায় আছে তার ঠিকানা
শেষ নোডের পরে কেউ নেই, তাই তার next-এ থাকে nullptr (C-তে NULL)। প্রথম নোডের ঠিকানা রাখা হয় head নামের একটা পয়েন্টারে। অনেক বইয়ে একে root বলা হয়।

আধুনিক C++-এ নোড এভাবে লেখা যায়ঃ
#include <iostream>
using namespace std;
struct Node {
int roll;
Node* next;
Node(int r) : roll(r), next(nullptr) {} // নতুন নোড তৈরির সময়ই মান বসে যাবে
};
Node* head = nullptr; // শুরুতে লিস্ট খালি
মনে রাখুনঃ
headহারিয়ে ফেললে পুরো লিস্ট হারিয়ে যাবে। প্রথম চিরকুট হারালে ট্রেজার হান্টও ওখানেই শেষ।
লিস্টের শেষে নোড যোগ করা (Append)
দুটো অবস্থা ভাবতে হবেঃ
- লিস্ট খালি হলেঃ নতুন নোডটাই
headহবে। - খালি না হলেঃ হাঁটতে হাঁটতে শেষ নোডে যেতে হবে, তারপর তার
next-এ নতুন নোড জুড়ে দিতে হবে।

void append(int roll) {
Node* newNode = new Node(roll);
if (head == nullptr) { // লিস্ট খালি
head = newNode;
return;
}
Node* cur = head; // head-এর কপি নিয়ে হাঁটছি
while (cur->next != nullptr) { // যার next নেই, সে-ই শেষ নোড
cur = cur->next;
}
cur->next = newNode; // শেষ নোডের সাথে নতুন নোড জুড়ে দিলাম
}
এখানে লক্ষ্য করুন, হাঁটার জন্য head সরানো হয়নি, তার একটা কপি cur নেওয়া হয়েছে। head নিজেই সামনে গেলে প্রথম নোডগুলোর ঠিকানা আর কোথাও থাকবে না। প্রতিবার শেষ পর্যন্ত হাঁটতে হয়, তাই এই append-এর কমপ্লেক্সিটি O(n)। একটু পরে এটাকে O(1) করা যাবে।
পুরো লিস্ট প্রিন্ট করা
void printList() {
for (Node* cur = head; cur != nullptr; cur = cur->next) {
cout << cur->roll << " -> ";
}
cout << "NULL\n";
}
int main() {
append(1);
append(2);
append(6);
printList(); // আউটপুট: 1 -> 2 -> 6 -> NULL
return 0;
}লিংকড লিস্টের দুর্বলতাঃ সরাসরি এক্সেস নেই
১০ নম্বর ছাত্রের রোল দরকার হলে অ্যারেতে roll[9] লিখলেই হয়। লিংকড লিস্টে নোডগুলো মেমরিতে ছড়িয়ে আছে, তাই প্রথম থেকে একটা একটা করে গুনে যেতে হবেঃ
// k-তম নোড খোঁজা (০ থেকে গণনা)
Node* getAt(int k) {
Node* cur = head;
while (cur != nullptr && k > 0) {
cur = cur->next;
k--;
}
return cur; // না পেলে nullptr
}
এর কমপ্লেক্সিটি O(n), আর অ্যারেতে একই কাজ O(1)। এটা ইনস্টাগ্রাম স্টোরির মতো। বন্ধুর ১৫ নম্বর স্টোরি দেখতে চাইলে সরাসরি সেখানে যাওয়া যায় না, একটা একটা ট্যাপ করে এগোতে হয়।
নোড মুছে ফেলা (Delete)
এখানে লিংকড লিস্ট অ্যারের চেয়ে এগিয়ে। কাউকে মুছতে হলে বাকিদের সরাতে হয় না, শুধু দুটো পয়েন্টার ঠিক করলেই হয়। ধরুন রোল ২ মুছতে হবে।
- রোল ২-এর আগের নোড (রোল ১) এখন সরাসরি রোল ২-এর পরের নোডকে দেখাবে।
- রোল ২-এর মেমরি সিস্টেমকে ফেরত দিতে হবে।

মুছতে চাওয়া নোডটা যদি head হয়, তাহলে কাজ আরও সহজ। head-কে এক ঘর সামনে সরিয়ে পুরনো নোডটা মুছে দিলেই হয়।
bool deleteNode(int roll) {
Node* cur = head;
Node* prev = nullptr;
while (cur != nullptr && cur->roll != roll) { // খুঁজছি, আগেরটাও মনে রাখছি
prev = cur;
cur = cur->next;
}
if (cur == nullptr) return false; // এমন রোল লিস্টে নেই
if (prev == nullptr) head = cur->next; // head মুছছি
else prev->next = cur->next; // মাঝের বা শেষের নোড মুছছি
delete cur; // মেমরি ফেরত দেওয়া বাধ্যতামূলক
return true;
}
এই কোডে cur != nullptr চেকটা খুব জরুরি। এটা না থাকলে লিস্টে নেই এমন কোনো রোল মুছতে গেলে প্রোগ্রাম ক্র্যাশ করবে। অনেক টিউটোরিয়ালেও এই চেকটা বাদ পড়ে।
deleteদিতে ভুলবেন না। লিস্ট থেকে নোডের লিংক সরালেও তার মেমরি দখল হয়েই থাকে। একে বলে মেমরি লিক। অনেকদিন চলা সার্ভারে এভাবে একটু একটু করে মেমরি জমতে জমতে একসময় সার্ভার বন্ধ হয়ে যায়।
চ্যালেঞ্জঃ দুই নোডের মাঝে নতুন নোড বসানো
একটা ফাংশন লিখুন insertAfter(target, roll)। এটা target রোলের নোডটা খুঁজে বের করবে, তারপর ঠিক তার পরে roll দিয়ে নতুন নোড বসাবে। আগে নিজে চেষ্টা করুন, তারপর নিচের সমাধান দেখুন।
bool insertAfter(int target, int roll) {
Node* cur = head;
while (cur != nullptr && cur->roll != target) cur = cur->next;
if (cur == nullptr) return false;
Node* newNode = new Node(roll);
newNode->next = cur->next; // আগে নতুন নোডকে পরেরটার সাথে জুড়ি
cur->next = newNode; // তারপর আগেরটাকে নতুন নোডের সাথে
return true;
}
শেষ দুই লাইনের ক্রম উল্টে দিলে কী হবে ভেবে দেখুন। cur->next আগে বদলে গেলে পরের নোডগুলোর ঠিকানা আর কোথাও থাকবে না, লিস্টের বাকি অংশ হারিয়ে যাবে।
ডাবলি লিংকড লিস্টঃ দুই দিকেই যাওয়া যায়
আমাদের এখনকার লিস্টে দুটো সীমাবদ্ধতা আছেঃ
- শেষে যোগ করতে প্রতিবার পুরো লিস্ট হাঁটতে হয় (O(n))
- পেছনের দিকে যাওয়া যায় না
এর সমাধান হলো প্রতিটা নোডে আরেকটা পয়েন্টার prev যোগ করা, আর শেষ নোডের ঠিকানা রাখার জন্য একটা tail পয়েন্টার রাখা।

struct DNode {
int roll;
DNode* prev;
DNode* next;
DNode(int r) : roll(r), prev(nullptr), next(nullptr) {}
};
DNode* dhead = nullptr;
DNode* tail = nullptr;
void pushBack(int roll) { // এখন O(1)
DNode* n = new DNode(roll);
if (tail == nullptr) { // লিস্ট খালি
dhead = tail = n;
return;
}
tail->next = n;
n->prev = tail; // দুই দিকের লিংকই দিতে হবে
tail = n;
}
void printBackward() {
for (DNode* c = tail; c != nullptr; c = c->prev) cout << c->roll << " ";
cout << "\n";
}
দুটো বিষয় আলাদা করে বোঝা দরকারঃ
- শেষে O(1)-এ যোগ করার সুবিধা আসে tail পয়েন্টার থেকে। সিঙ্গলি লিস্টেও tail রাখলে এটা পাওয়া যায়।
- পেছনে হাঁটা, আর কোনো নোডের পয়েন্টার হাতে থাকলে তাকে O(1)-এ মুছতে পারা আসে prev পয়েন্টার থেকে।
মিউজিক প্লেয়ারের Next/Previous বাটন বা ব্রাউজারের Back/Forward বাটন এই ধারণার সবচেয়ে পরিচিত উদাহরণ।
লিংকড লিস্ট থেকে ট্রিঃ বাইনারি সার্চ ট্রি
একটা নোডে শুধু next-এর বদলে দুটো পয়েন্টার left আর right রাখলে একটা ট্রি তৈরি হয়। বাইনারি সার্চ ট্রি (BST)-তে নিয়মটা এরকমঃ
- কোনো নোডের বাম দিকে থাকে তার চেয়ে ছোট মান
- ডান দিকে থাকে সমান বা বড় মান

struct TreeNode {
int roll;
TreeNode* left;
TreeNode* right;
TreeNode(int r) : roll(r), left(nullptr), right(nullptr) {}
};
TreeNode* insert(TreeNode* root, int roll) {
if (root == nullptr) return new TreeNode(roll); // ফাঁকা জায়গা পেলে এখানেই বসাও
if (roll < root->roll) root->left = insert(root->left, roll);
else root->right = insert(root->right, roll);
return root;
}
void preorder(TreeNode* r) {
if (r == nullptr) return;
cout << r->roll << " ";
preorder(r->left);
preorder(r->right);
}
int main() {
TreeNode* root = nullptr;
for (int x : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, x);
preorder(root); // 50 30 20 40 70 60 80
}
BST থেকে নোড মুছে ফেলার ফাংশন লিখুন। তিনটা অবস্থা আলাদাভাবে ভাবতে হবেঃ নোডের কোনো চাইল্ড নেই, একটা চাইল্ড আছে, আর দুটো চাইল্ডই আছে। শেষেরটাই সবচেয়ে মজার।
লিংকড লিস্ট সর্ট করবেন কীভাবে?
লিংকড লিস্টে সরাসরি এক্সেস নেই। তাই Quick Sort বা Heap Sort-এর মতো যেসব অ্যালগরিদম বারবার যেকোনো ইনডেক্সে লাফ দেয়, সেগুলো এখানে ভালো কাজ করে না। লিংকড লিস্টের জন্য সবচেয়ে উপযুক্ত হলো Merge Sort:
- লিস্টকে মাঝখান থেকে দুই ভাগ করা হয় (slow/fast পয়েন্টার দিয়ে)
- দুই ভাগকে আলাদাভাবে সর্ট করা হয়
- সর্ট করা দুই লিস্টকে পয়েন্টার বদলে জোড়া লাগানো হয়
এতে সময় লাগে O(n log n), আর অ্যারের মতো বাড়তি অ্যারে বানাতে হয় না। C++-এর std::list::sort()-ও মার্জ সর্টের মতো পদ্ধতিতে কাজ করে। সর্টিং ভালোভাবে শিখতে VisuAlgo সাইটে অ্যানিমেশন দেখে প্রতিটা অ্যালগরিদম ধাপে ধাপে অনুসরণ করুন। এরপর LeetCode 148 (Sort List) সমস্যাটা নিজে সমাধান করুন।
C নাকি C++?
উপরের কোডগুলো C++। new, delete, nullptr, cout বা struct না লিখে শুধু Node* লেখা, এগুলো C-তে চলবে না। C-তে লিখতে চাইলে এভাবে লিখুনঃ
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int roll;
struct Node* next;
} Node;
Node* head = NULL;
void append(int roll) {
Node* n = malloc(sizeof(Node)); // new-এর বদলে malloc
n->roll = roll;
n->next = NULL;
if (head == NULL) { head = n; return; }
Node* cur = head;
while (cur->next != NULL) cur = cur->next;
cur->next = n;
}
// মুছে ফেলার সময় delete-এর বদলে free(node) ব্যবহার করুন
বাস্তবে লিংকড লিস্ট কোথায় ব্যবহার হয়?
- LRU ক্যাশঃ ব্রাউজার, ডাটাবেস আর ক্যাশ সার্ভার ঠিক করে কোন ডাটা মেমরিতে থাকবে আর কোনটা বাদ যাবে। সাধারণত হ্যাশম্যাপ আর ডাবলি লিংকড লিস্ট একসাথে ব্যবহার করে এটা বানানো হয়।
- অপারেটিং সিস্টেমঃ লিনাক্স কার্নেলে প্রসেস, টাইমার আর আরও অনেক কিছুর তালিকা রাখতে
list_headনামের লিংকড লিস্ট ব্যবহার হয়। - Undo/Redo: টেক্সট এডিটর বা ডিজাইন টুলে আগের আর পরের অবস্থায় যেতে এই ধরনের লিস্ট কাজে লাগে।
- ব্লকচেইনঃ প্রতিটা ব্লকে আগের ব্লকের হ্যাশ থাকে, যা পয়েন্টারের মতোই এক ব্লক থেকে আরেক ব্লকে যোগসূত্র তৈরি করে।
- অন্যান্য ডাটা স্ট্রাকচারঃ স্ট্যাক, কিউ, গ্রাফের অ্যাডজেসেন্সি লিস্ট, হ্যাশ টেবিলের chaining আর Trie, সবগুলোই লিংকড লিস্টের ধারণার ওপর তৈরি।
কখন লিংকড লিস্ট ব্যবহার করবেন না
আধুনিক CPU-তে ক্যাশ মেমরি আছে। অ্যারের ডাটা পাশাপাশি থাকে, তাই CPU একবারে অনেকগুলো এলিমেন্ট ক্যাশে তুলে নিতে পারে। লিংকড লিস্টের নোড মেমরিতে ছড়িয়ে থাকে, তাই প্রায় প্রতিটা নোড পড়তে CPU-কে আলাদা করে মেমরি থেকে আনতে হয় (cache miss)। এর ফলে কাগজে-কলমে লিংকড লিস্টের যেসব কাজ দ্রুত হওয়ার কথা, বাস্তবে সেখানেও অনেক সময় std::vector বেশি দ্রুত চলে। C++-এর স্রষ্টা Bjarne Stroustrup নিজেও তাঁর বক্তৃতায় এটা দেখিয়েছেন। তাহলে কী ব্যবহার করবেন?
| পরিস্থিতি | ভালো পছন্দ |
|---|---|
| ইনডেক্স দিয়ে বারবার পড়তে হবে | অ্যারে / vector |
| শুধু শেষে যোগ বা মোছা হবে | vector |
| নোডের পয়েন্টার হাতে আছে, আর মাঝখানে বারবার যোগ বা মোছা হবে | লিংকড লিস্ট |
| যোগ বা মোছার পরেও বাকি এলিমেন্টের ঠিকানা আগের মতো থাকতে হবে | লিংকড লিস্ট |
| ইন্টারভিউ বা অ্যালগরিদমের ধারণা শেখা | অবশ্যই লিংকড লিস্ট |
আধুনিক C++-এ std::list (ডাবলি) আর std::forward_list (সিঙ্গলি) তৈরি অবস্থায় পাওয়া যায়। প্রোডাকশন কোডে নিজে পয়েন্টার সামলানোর বদলে এগুলো, অথবা std::unique_ptr দিয়ে মেমরি ব্যবস্থাপনা করাই নিরাপদ। Rust-এর মতো নতুন ভাষায় পয়েন্টারের নিয়ম এত কড়া যে লিংকড লিস্ট লেখা নিয়ে রীতিমতো একটা বিখ্যাত বই আছে। এআই টুল আজ লিংকড লিস্টের কোড সেকেন্ডেই লিখে দিতে পারে। কিন্তু সেই কোডে কোথায় মেমরি লিক হচ্ছে বা কোথায় nullptr চেক বাদ পড়েছে, তা ধরতে হলে ধারণাটা আপনার নিজের জানা থাকতে হবে। ভবিষ্যতে এই দক্ষতার গুরুত্ব কমবে না, বরং বাড়বে।
নতুনদের সাধারণ ভুল
nullptrচেক না করাঃcurনাল হয়ে যাওয়ার পরেওcur->nextবাcur->rollপড়তে গেলে প্রোগ্রাম ক্র্যাশ করে (segmentation fault)।deleteবাfreeভুলে যাওয়াঃ এতে মেমরি লিক হয়।headবাtailনিজেই সরিয়ে ফেলাঃ হাঁটার জন্য সবসময় আলাদা কপি পয়েন্টার নিন।- পয়েন্টার বদলানোর ক্রম ভুল করাঃ লিংক আগে ভাঙলে বাকি লিস্ট হারিয়ে যায়।
- ডাবলি লিস্টে
prevআপডেট না করাঃ সামনে থেকে হাঁটলে সব ঠিক দেখায়, কিন্তু পেছন থেকে হাঁটলে লিস্ট ভাঙা পাওয়া যায়।
পরামর্শঃ খাতায় বক্স আর তীর এঁকে প্রতিটা ধাপ মিলিয়ে দেখুন। লিংকড লিস্টের বেশিরভাগ বাগ কাগজে আঁকলেই ধরা পড়ে।
এরপর কী শিখবেন?
- লিংকড লিস্ট দিয়ে স্ট্যাক আর কিউ বানানো
- লিংকড লিস্টে লুপ বা সাইকেল আছে কিনা খোঁজাঃ Floyd's Cycle Detection (কচ্ছপ আর খরগোশ পদ্ধতি)
- LRU ক্যাশ নিজে ইমপ্লিমেন্ট করা (LeetCode 146)
- Trie আর হিপ
- অনুশীলনের জন্য LeetCode 206 (Reverse Linked List), 21 (Merge Two Sorted Lists), 141 (Linked List Cycle)
সংক্ষেপে প্রশ্নোত্তর (FAQ)
প্রশ্নঃ লিংকড লিস্ট কী? উত্তরঃ এটা এমন একটা ডাটা স্ট্রাকচার যেখানে প্রতিটা নোডে ডাটা আর পরের নোডের ঠিকানা থাকে। নোডগুলো মেমরিতে পাশাপাশি থাকার দরকার হয় না।
প্রশ্নঃ অ্যারে আর লিংকড লিস্টের মূল পার্থক্য কী? উত্তরঃ অ্যারেতে ইনডেক্স দিয়ে সরাসরি পড়া যায় (O(1)), কিন্তু মাঝখানে যোগ বা মোছা ধীর। লিংকড লিস্টে কোনো এলিমেন্টে পৌঁছাতে O(n) লাগে, কিন্তু নোড হাতে থাকলে যোগ বা মোছা O(1)।
প্রশ্নঃ লিংকড লিস্ট শিখতে কী কী জানা দরকার? উত্তরঃ পয়েন্টার, struct আর বেসিক টাইম কমপ্লেক্সিটি।
প্রশ্নঃ লিংকড লিস্ট সর্ট করার সবচেয়ে ভালো উপায় কী? উত্তরঃ Merge Sort। এতে সময় লাগে O(n log n) আর বাড়তি অ্যারে লাগে না।