Phitron Book

Appearance

মডিউল ৬: More Operation on Singly Linked List ​

6_0 Introduction ​

আজকের মডিউলে আমরা শিখবো কিভাবে Singly Linked List থেকে কোনো নোড ডিলিট করা যায়। -> Delete from head -> Delete from tail -> Delete from any position

তাছাড়াও আমরা দেখবো Singly Linked List কীভাবে সর্ট করা যায় এবং রিভার্স ওয়েতে প্রিন্ট করা যায়।

Input a Linked List ​

Singly Linked List এ ইনপুটের ক্ষেত্রে আমরা ভেক্টর এর Insertion এর মতো করে চিন্তা করতে পারি। আমরা একটি ভ্যালু নিতাম সেটি ভেক্টরের শেষে পুশ ব্যাক করে দিতাম।

ঠিক তেমন ই এখানে আমরা আমাদের আগে বানানো একটি ফানশন Insert at tail ব্যবহার করতে পারি , যেটি একটি লিঙ্কড লিস্টের শেষে ভ্যালু নিয়ে একটি Node Insert করে দেয়। আমরা প্রতিটি ইনপুট নিয়ে এই ফানশনে pass করে দিলেই লিঙ্কড লিস্টের শেষের দিকে Node insert হতে থাকবে।

আসেন নিচের চিত্র দেখে এই অপারেশন টি আরেকটু ভালো বুঝার চেষ্টা করি।

Linked List Input Operation

Code:

c
#include <bits/stdc++.h>
using namespace std;

class Node
{
   public:

   int val;

   Node *next;

   Node(int val)
   {
     this->val = val;
     this->next = NULL;
   }

};

void insert_at_tail(Node* &head, Node* &tail, int val) {
    Node* newNode = new Node(val);

    if (head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }

    tail->next = newNode;
    tail = newNode;
}

void print(Node *head)
{
  Node *temp = head;
  while (temp != NULL)
  {
    cout << temp->val << " ";
    temp = temp->next;
  }
  cout << endl;
}


int main()
{
 Node *head = NULL ;
 Node *tail = NULL ;
 int x ;

 while(1) { // একটি infinity loop চালাচ্ছি
 cin >> x ; // x ভ্যালু ইনপুট নিচ্ছি
 if(x!=-1){ // যদি x, -1 না হয় তবে
 insert_at_tail(head, tail, x) ; // লিঙ্কড লিস্ট এর শেষে insert করে দিচ্ছি
 }
 else{
 break ; // -1 হলে loop break করে দিচ্ছি
 }
 }

 print(head) ;

}

input : 1 2 3 -1
Output : 1 2 3

Linked List reverse printing ​

এবার আমরা লিঙ্কড লিস্টকে রিভার্স প্রিন্ট করব।

প্রথমে আমরা সিংগলি লিঙ্কড লিস্ট কে রিকারশন দিয়ে প্রিন্ট করার চেষ্টা করি। আমাদের নরমাল প্রিন্ট ফাংশনটি ছিল এরকম।

c
void print_linked_list(Node *head)
{

 Node *tmp = head;
 while (tmp != NULL)
 {
 cout << tmp->val << " ";
 tmp = tmp->next;
 }
 cout << endl;
}

আমরা একটি নোড নিয়ে হেড থেকে প্রিন্ট করা শুরু করতাম। প্রতিবার নোডকে তার নেক্সট নোডে নিয়ে যেতাম। নোড যখন নালে চলে যেত তখন আমরা প্রিন্ট করা থামিয়ে দিতাম। এই সেইম প্রসেস আমরা এখন রিকারশন দিয়ে করব।

c
void print_recursion(Node *n)
{
 // base case
 if (n == NULL) // শুরুতে বেস কেস লিখা হচ্ছে। নোড যখন নালে চলে যাচ্ছে তখন আমরা প্রিন্ট করা থামিয়ে দিচ্ছি।
 return ; // বেস কেস ট্রু হলে রিটার্ন করে দিচ্ছি।
 cout << n->val << " "; // নোডের ভেলু প্রিন্ট করছি।
 print_recursion(n->next); // নোডকে তার নেক্সট নোডে নিয়ে যাচ্ছি।
}

কোডটি রান করলে দেখব লিঙ্কড লিস্ট এর প্রতিটি এলিমেন্ট প্রিন্ট হচ্ছে। এবার আসি আমাদের মেইন টার্গেট কিন্তু এটি ছিল না। আমাদের টার্গেট ছিল লিঙ্কড লিস্ট রিভার্স প্রিন্ট করা। এটি আমরা নরমালি while লুপ দিয়ে করতে পারব না। কারন সিংগলি লিঙ্কড লিস্টে পিছনের দিকে আসা যায় না। সোজা প্রিন্ট করার সময় আমরা যেমন একটি টেম্প নোড নিয়ে হেড থেকে টেল পর্যন্ত প্রিন্ট করেছি, রিভার্স প্রিন্ট এর সময় কিন্তু আমরা সেইমভাবে একটি টেম্প নোড নিয়ে টেল থেকে হেড পর্যন্ত প্রিন্ট করতে পারব না। কারন সিংগলি লিঙ্কড লিস্টে টেল থেকে হেডের দিকে আসা যায় না।

তো এটি আমরা খুব সহজে রিকারশন দিয়ে করে ফেলতে পারি। আমরা যখন রিকারশন দিয়ে সোজা প্রিন্ট করেছি তখন আমরা শুরুতে কাজ করেছি ( cout << n->val << " "; ) তারপর রিকারশন ফাংশন কল করেছি ( print_recursion(n->next); ) । জাস্ট এই দুটি লাইন যদি আমরা উল্টিয়ে দেই তাহলেই আসলে আমাদের রিকারশন দিয়ে রিভার্স প্রিন্ট করা হয়ে যাবে। আমরা আগে কল করে করে একদম শেষ অর্থাৎ টেল পর্যন্ত যাব তারপর প্রিন্ট করা শুরু করব।

c
void print_reverse(Node *n)
{
 // base case
 if (n == NULL)
 return ;

 print_reverse(n->next); // আগে কল করছি।
 cout << n->val << " "; // তারপর কাজ করছি।
}

এবার আমরা সিমুলেশনটা দেখে নেইঃ

Reverse Print Step 1

n এখন ১০ এ আছে। বেস কেস এর কন্ডিশন সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

Reverse Print Step 2

এবার n ২০ এ আছে। বেস কেস এর কন্ডিশন এবারও সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

Reverse Print Step 3

এবার n ৩০ এ আছে। বেস কেস এর কন্ডিশন এবারও সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

Reverse Print Step 4

এবার n নালে আছে। বেস কেস এর কন্ডিশন সত্য হচ্ছে তাই এবার এই রিকারশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

Reverse Print Step 5

এখানে এসে ৩০ প্রিন্ট হচ্ছে। তারপর এই ফাংশনের কাজ শেষ এবার এই ফাংশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

Reverse Print Step 6

এই ফাংশনে n এর মান ২০। তাই ২০ প্রিন্ট হচ্ছে। তারপর এই ফাংশনের কাজ শেষ এবার এই ফাংশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

Reverse Print Step 7

এই ফাংশনে n এর মান ১০। তাই ১০ প্রিন্ট হচ্ছে। এভাবে পুরো লিঙ্কড লিস্টটি রিভার্স প্রিন্ট হয়ে গেল।

সম্পূর্ণ কোডঃ

c
#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
 int val;
 Node *next;
 Node(int val)
 {
 this->val = val;
 this->next = NULL;
 }
};

void print_recursion(Node *n)
{
 // base case
 if (n == NULL)
 return ;
 cout << n->val << " ";
 print_recursion(n->next);
}

void print_reverse(Node *n)
{
 // base case
 if (n == NULL)
 return ;

 print_reverse(n->next); // আগে কল করছি।
 cout << n->val << " "; // তারপর কাজ করছি।
}

int main()
{
 Node *head = new Node(10);
 Node *a = new Node(20);
 Node *b = new Node(30);
 Node *c = new Node(40);
 Node *d = new Node(50);
 head->next = a;
 a->next = b;
 b->next = c;
 c->next = d;

 print_recursion(head);
 cout << endl;
 print_reverse(head);
 return 0;
}

কোডটি রান করলে দেখব প্রথমে লিঙ্কড লিস্ট সোজা প্রিন্ট হচ্ছে এবং তারপর রিভার্স প্রিন্ট হচ্ছে।

Delete at Head ​

এবার আমরা লিঙ্কড লিস্টে হেড থেকে কিভাবে ডিলিট করা হয় তা দেখবো।

হেড ডিলিট করা খুবই ইজি। আমরা শুরুতে হেডকে একটি ডিলিট নোড পয়েন্টারে রেখে দিব, কাজ শেষে ডিলিট করে দেওয়ার জন্য।

কোডঃ

c
Node *deleteNode = head;

Delete Head Step 1

হেড পয়েন্টারকে তার নেক্সটে নিয়ে যাব।

কোডঃ

c
head = head->next;

Delete Head Step 2

তারপর হেড ডিলিট করে দিব।​ ​

কোডঃ

c
delete deleteNode;

Delete Head Step 3

সম্পূর্ণ কোডঃ

c
#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
 int val;
Node *next;
 Node(int val)
 {
 this->val = val;
 this->next = NULL;
 }
};

void print_linekd_list(Node *head)
{
Node *tmp = head;
 while (tmp != NULL)
 {
cout << tmp->val << " ";
tmp = tmp->next;
 }
cout << endl;
}

int size(Node *head)
{
Node *tmp = head;
 int count = 0;

 while (tmp != NULL)
 {
count++;
tmp = tmp->next;
 }
 return count;
}

void delete_node(Node *head, int pos)
{
Node *tmp = head;
 for (int i = 1; i <= pos - 1; i++)
 {
tmp = tmp->next;
 }
Node *deleteNode = tmp->next; // 30
tmp->next = tmp->next->next;
delete deleteNode;
}

void delete_head(Node *&head)
{
Node *deleteNode = head; // শুরুতে হেডকে একটি ডিলিট নোড পয়েন্টারে রেখে দিব, কাজ শেষে ডিলিট করে দেওয়ার জন্য।
head = head->next; // হেড পয়েন্টারকে তার নেক্সটে নিয়ে যাব।
delete deleteNode; // তারপর হেড ডিলিট করে দিব।
}

int main()
{
 Node *head = new Node(10);
 Node *a = new Node(20);
 Node *b = new Node(30);
 Node *c = new Node(40);
 Node *d = new Node(50);
 head->next = a;
a->next = b;
b->next = c;
c->next = d;

 print_linekd_list(head);

 int pos;
 cin >> pos;
 if (pos >= size(head))
 {
cout << "Invalid" << endl;
 }
 else if (pos == 0)
 {
 delete_head(head);
 }
 else
 {
 delete_node(head, pos);
 }
 print_linekd_list(head);

 return 0;
}

Delete at any position ​

এইবার দেখবো কীভাবে লিঙ্কড লিস্ট থেকে কীভাবে একটি ভ্যালু ডিলিট করতে হয়।

প্রথমে দেখবো কীভাবে যেকোন পজিশন/ ইন্ডেক্স এর Node Delete করতে হয়।

ধরেন নিচের চিত্রের ২ নাম্বার index এর Node টি delete করতে বলা হয়েছে।​ ​

Delete at Position Initial

Working Procedure :

  1. প্রথমে temp কে যে index ডিলিট করতে হবে তার আগের Node এ নিয়ে যাবো।
  2. এরপর temp->next কে delete_node এ স্টোর করে রাখবো যাতে পরবর্তীতে delete করতে পারি।
  3. temp->next এ temp->next->next স্টোর করবো। কারণ temp->next এ আছে যে Node ডিলিট করতে হবে সেই Node , তার নেক্সট এ আছে delete_node এর পরবর্তী Node. এখন আমরা delete করতে হবে যে Node কে তার পূর্ববর্তী Node এর next এ delete_node এর পরবর্তী node এর এড্রেস রেখে দিচ্ছি। এর মাধ্যমে delete_node আর এই লিঙ্কড লিস্টের মধ্যে থাকবে না।
  4. সবশেষে delete keyword ব্যবহার করে delete_node কে মেমরি থেকে delete করে দিবো।

আসুন এইবার কোড দেখে নেয়া যাক।

Code:

c
void delete_at_position(Node *&head, int position)
{

 Node *temp = head;

 for (int i = 1; i <= position - 1; i++) // আগের লজিক ব্যবহার করে tmp কে যে index এ Node ডিলিট করতে হবে ঐ পজিশনে নিয়ে গেলাম
 {
 temp = temp->next;
 }
 Node* delete_node = temp->next; // temp->next কে delete_node এ স্টোর করে রাখলাম যাতে পরবর্তীতে delete করতে পারি।
 temp->next = temp->next->next; // temp->next এ যে Node ডিলিট করতে হবে তার পরবর্তী Node রেখে দিলাম
 delete delete_node; // ঐ নোড ডিলিট করে দিলাম
}

Delete at tail ​

পূর্বের মডিউলে আমরা দেখেছি Singly Linked List এর যেকোনো পজিশন থেকে কিভাবে একটি নোড ডিলিট করা যায়।

তো এই মডিউলে আমরা দেখবো কিভাবে Tail থেকে ডিলিট করা যায়।

একটি খুব সহজ উপায় হলো, আমরা delete_at_any_pos() ফাংশন তৈরী করেছিলাম। সেখানে যদি আমরা Tail এর ইনডেক্স পাঠিয়ে দেই তাহলে খুব সহজেই আমরা Tail কিন্তু ডিলিট করে ফেলতে পারবো।

c
void delete_at_any_pos(Node* &head, int idx) {
    Node* tmp = head;
    for(int i=1; i<idx; i++) {
        tmp = tmp->next;
    }
    Node* deleteNode = tmp->next;
    tmp->next = tmp->next->next;
    delete deleteNode;
}

এই ফাংশনে শুধু Tail এর ইনডেক্স পাঠিয়ে দিলেই কিন্তু Tail ডিলিট হয়ে যাবে।

আবার আমরা যদি চাই ইনডেক্স ছাড়া Tail ডিলিট করতে, সেটাও কিন্তু সম্ভব।

সেক্ষেত্রে আমাদের Tail এর ঠিক আগের নোডে যেতে হবে। তারপর Tail কে ডিলিট করতে হবে।

সেটা যেভাবে করতে পারি তার কোড নিম্নে দেয়া হলো।

c
void delete_at_tail(Node* &head) {
    Node* tmp = head;
    if (head == NULL) return; // empty list
    if (head->next == NULL) { // Only one element so head will be set to NULL
        delete head;
        head = NULL;
        return;
    }
    while(tmp->next->next != NULL) {
        tmp = tmp->next;
    }
    Node* deleteNode = tmp->next;
    tmp->next = NULL;
    delete deleteNode;
}

১। যদি লিষ্ট empty থাকে তাহলে কিছু ডিলিট করা সম্ভব নয়।

২। যদি শুধু একটি নোড থাকে, তাহলে Tail ডিলিট করা মানে ঐ নোডটিই ডিলিট করা। এবং সেক্ষেত্রে head = NULL হয়ে যাবে।

৩। যদি ২ বার তার অধিক নোড থাকে, তাহলে Tail এর আগের নোডে যেতে হবে। তারপর tail কে deleteNode এর মাধ্যমে স্টোর করতে হবে যেনো ডিলিট করতে পারি। আর tmp->next = NULL করতে হবে। অর্থাৎ বর্তমান Tail এর আগের নোডকে tail বানিয়ে দিতে হবে।

Complexity analysis of every operations ​

বোনাস পার্টঃ এবার আমরা লিঙ্কড লিস্ট এর সবগুলো অপারেশন এর কমপ্লেক্সিটি এনালাইসিস করব।

ইনসার্ট হেডঃ কোন লুপ চালাতে হয় না। কমপ্লেক্সিটি O(1)

ইনসার্ট টেলঃ যদি আমরা টেল ট্র্যাক রাখি তাহলে কোন লুপ চালাতে হয় না। কমপ্লেক্সিটি O(1)। যদি টেল ট্র্যাক না রাখি তাহলে লুপ চালিয়ে টেল পর্যন্ত যেতে হয়। তখন কমপ্লেক্সিটি O(N)

ইনসার্ট এট এনি পজিশনঃ লুপ চালিয়ে পজিশন পর্যন্ত যেতে হয়। কমপ্লেক্সিটি O(N)।

ডিলিট হেডঃ কোন লুপ চালাতে হয় না। কমপ্লেক্সিটি O(1)

ডিলিট টেলঃ যদি আমরা টেল ট্র্যাক রাখি তাহলেও লুপ চালাতে হবে কারন টেলকে পিছিয়ে নিয়ে আসা যায় না। তাই আগে লুপ চালিয়ে লাস্ট এর আগের নোড পর্যন্ত যেতে হবে তারপর টেল ডিলিট করতে হবে। কমপ্লেক্সিটি O(N)।

ডিলিট এট এনি পজিশনঃ লুপ চালিয়ে পজিশন পর্যন্ত যেতে হয়। কমপ্লেক্সিটি O(N)।

Complexity Analysis Table

Sorting a linked List with selection sort ​

এবার আমরা লিঙ্কড লিস্ট সর্ট করা দেখব সিলেকশন সর্ট দিয়ে।

আমরা এরে যেভাবে সর্ট করেছিলাম সিলেকশন সর্ট দিয়ে সেইমভাবে আমরা একটি লিঙ্কড লিস্ট ও সর্ট করে ফেলতে পারব। আমরা শুরুতে সিলেকশন সর্ট দিয়ে এরে সর্ট করার কোডটা একটু মনে করি।

c
for(int i=0;i<n-1;i++)  ​ ​ ​ ​ ​ ​ // নেস্টেড লুপ চালিয়ে প্রতিটি এলিমেন্ট এর সাথে প্রতিটি এলিমেন্ট কম্পেয়ার করা হচ্ছে।
{
​ ​ for(int j=i+1;j<n;j++)
​ ​ ​ ​ {
​ ​ ​ ​ ​ ​ ​ ​ if(a[i]>a[j]) ​ ​ ​ ​ ​ ​ ​ ​ // যদি পূর্বের ভেলুটি পরের ভেলু থেকে বড় হয়ে যায় তারমানে এরেটি সর্টেড নেই।
​ ​ ​ ​ ​ ​ ​ ​ {
​ ​ ​ ​ ​ ​ ​ ​ ​ swap(a[i],a[j]); ​ ​ ​ ​ // তখন আমরা ভেলু দুটো সোয়াপ করে দিচ্ছি যেন সর্টেড হয়ে যায়।
​ ​ ​ ​ ​ ​ ​ ​ }
​ ​ ​ ​ }
}

এবার আমরা এই কোডটিকে লিঙ্কড লিস্টে কনভার্ট করি।​ ​

for(int i=0;i<n-1;i++)

  • int i=0 -> Node *i = head [ এখানে একটি পয়েন্টার নিয়ে তাতে হেড রেখে দিচ্ছি ]
  • i<n-1 -> i->next != NULL [ i<n-1 দিয়ে আমরা লাস্টের আগের ইন্ডেক্স পর্যন্ত যাচ্ছিলাম, i->next != NULL দিয়ে আমরা লাস্টের আগের নোড পর্যন্ত যাচ্ছি ]
  • i++ -> i = i->next [ i++ দিয়ে আমরা ইন্ডেক্স কে সামনে আগাচ্ছিলাম, i = i->next দিয়ে আমরা পয়েন্টার কে নেক্সট নোডে অর্থাৎ সামনে আগাচ্ছি ]

int j=i+1 -> Node *j = i->next [ int j=i+1 দিয়ে আমরা নতুন ভেরিয়েবল নিয়েছিলাম যা শুরু হচ্ছিল i এর পরের ইন্ডেক্স থেকে, Node *j = i->next দিয়ে আমরা নতুন পয়েন্টার নিয়েছি যা শুরু হচ্ছে i এর পরের নোড থেকে ]

j<n -> j != NULL [ j<n দিয়ে আমরা লাস্ট ইন্ডেক্স পর্যন্ত যাচ্ছিলাম, j != NULL দিয়ে আমরা লাস্ট নোড পর্যন্ত যাচ্ছি ]

j++ -> j = j->next [ j++ দিয়ে আমরা ইন্ডেক্স কে সামনে আগাচ্ছিলাম, j = j->next দিয়ে আমরা পয়েন্টার কে নেক্সট নোডে অর্থাৎ সামনে আগাচ্ছি ]

a[i],a[j] -> i->val, j->val [ a[i],a[j] দিয়ে আমরা এরেতে i,j ইন্ডেক্সে থাকা ভেলু এক্সেস করছিলাম, i->val, j->val দিয়ে আমরা i,j পয়েন্টারে থাকা ভেলু এক্সেস করছি।]

সম্পুরন কোডঃ

c
#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
 int val;
 Node *next;
 Node(int val)
 {
 this->val = val;
 this->next = NULL;
 }
};

void insert_tail(Node *&head, Node *&tail, int val)
{
 Node *newNode = new Node(val);
 if (head == NULL)
 {
 head = newNode;
 tail = newNode;
 return;
 }
 tail->next = newNode;
 tail = newNode;
}

void print_linekd_list(Node *head)
{
 Node *tmp = head;
 while (tmp != NULL)
 {
 cout << tmp->val << " ";
 tmp = tmp->next;
 }
 cout << endl;
}

int main()
{
 Node *head = NULL;
 Node *tail = NULL;
 int val;
 while (true)
 {
 cin >> val;
 if (val == -1)
 break;
 insert_tail(head, tail, val);
 }
 for (Node *i = head; i->next != NULL; i = i->next)
 {
 for (Node *j = i->next; j != NULL; j = j->next)
 {
 if (i->val < j->val)
 {
 swap(i->val, j->val);
 }
 }
 }
 print_linekd_list(head);
 return 0;
}

Released under the MIT License.

Copyright © 2026 - Phitron Book