5_0: Introduction

লিঙ্কড লিস্টের অপারেশন এর মডিউলে সকলকে স্বাগতম। এই মডিউলে আমরা যা যা শিখবো

1. Function এ পয়েন্টার এর Referecne কীভাবে pass করতে হয় তা শিখবো
2. কীভাবে Node Insert করতে হয় তা দেখবো
3. কীভাবে কোড অপটিমাইজ করতে হয়।
4. কীভাবে টাইম কমপ্লেক্সিটি বের করতে হয়।

পয়েন্টারের রেফারেনস

আমরা সি প্রোগ্রামিং কোর্সের মডিউল ১৬ এ শিখেছিলাম একটি ফাংশনে কোনো একটি ভ্যারিয়েবল দুই ভাবে পাস করা যায়।

1. একটি হলো কল বাই ভ্যালু , যেটি মেইন থেকে পাস করার সময় আমাদের মেইন এর ঐ ভ্যারিয়েবলের একটি কপি ক্রিয়েট করে সেটি ফাংশনে পাস করতো। এইক্ষেত্রে আমি যদি ফাংশনে ঐ ভ্যালুর কোনো পরিবর্তন করি , সেইক্ষেত্রে মেইনের ঐ ভ্যারিয়েবলের কোনো পরিবর্তন হতো না।
2. অপরটি হলো কল বাই রেফারেন্স , এই ক্ষেত্রে মেইন থেকে কোনো ভ্যারিয়েবল ফাংশনে পাস করার সময় ঐ ভ্যারিয়েবলের এড্রেস টি সরাসরি ফাংশনে পাস করতো। যেহেতু আমরা মেইন ফাংশন এর মধ্যে থাকা ভ্যালুটির কোনো রকম কপি ক্রিয়েট না করে সরাসরি ঐ ভ্যালুটির এড্রেস পাস করছি , এই ক্ষেত্রে ফাংশনের মধ্যে ঐ ভ্যারিয়েবল এর মান পরিবর্তন করা হলে মেইন এ থাকা ভ্যারিয়েবল এর মান টি পরিবর্তন হয়ে যাবে।

পয়েন্টারের ক্ষেত্রেও বিষয়টি ঠিক এক ই ভাবে কাজ করে।

ধরেন আপনাকে বলা হলো , একটি ফাংশন রেডি করো , যেখানে প্যারামিটার হিসেবে একটি পয়েন্টার রিসিভ করবা , এরপর ঐ পয়েন্টার এর মধ্যে স্টোর থাকা এড্রেস টি চেঞ্জ করে NULL করে দাও।

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

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

void fun( int *p ){ // কল বাই ভ্যালু হিসেবে পয়েন্টার পাস করা হচ্ছে
p = NULL ;
}

int main()
{
 int a = 10 ; // a নামের একটি ভ্যরিয়েবল নিলেন
 int *p = &a ; // p pointer কে a এর দিকে পয়েন্ট করে দিলেন initially.

 fun(p) ; // এরপর p কে NULL এর দিকে পয়েন্ট করার লক্ষ্যে পয়েন্টারকে ফাংশনে পাস করলেন

 cout << *p << endl ; // ফাংশনটি ঠিক মতো কাজ করছে কিনা চেক করার জন্য আপনি পয়েন্টার টি যে ভ্যারিয়েবলে পয়েন্ট করা আছে তা প্রিন্ট করে দেখছেন

}

Output : 10

কোডটি রান করার পর দেখলেন আপনি a এর ভ্যালুটি স্ক্রিনে দেখতে পেলেন। তার মানে , p যেদিকে পয়েন্ট করা ছিলো অর্থাৎ a এর দিকে এখনো ঠিক সেখানে পয়েন্ট করা আছে। পয়েন্টার টি অন্য দিকে ডিরেক্ট করার কাজটি আমাদের ডিফাইন করা ফাংশন fun ঠিক মতো করতে পারলো না।

এর কারণ কী ? -> খেয়াল করে দেখবেন , আমরা যে ফাংশন টি তৈরি করেছি তাতে যে প্যারামিটার পাস করা হচ্ছে তা আমাদের শেখা প্রথম টাই** কল বাই ভ্যালু **এর কন্সেপ্ট টি ব্যবহার করে করা হয়েছে। অর্থাৎ এই ক্ষেত্রে আমরা পয়েন্টার টাকে ডিরেক্টলি পাস না করে , ঐ পয়েন্টার এর একটি কপি পাস করছি । অর্থাৎ এই ক্ষেত্রে মেইন এ থাকা p পয়েন্টার টি সরাসরি ফাংশনে পাস হচ্ছে না। এটির একটি কপি ক্রিয়েট হয়ে তারপর ফাংশনে পাস হচ্ছে। এর পর আমরা ঐ কপিকৃত পয়েন্টার এর ভ্যালু চেঞ্জ করলেও যেহেতু এটি একটি কপি , তাই মেইনের p পয়েন্টার এ থাকা এড্রেসের কোনো পরিবর্তন হচ্ছে না।

তাহলে এর সমাধান কি ?

উত্তরঃ আমাদের মেইন এ থাকা পয়েন্টার টি এমন ভাবে পাস করতে হবে যাতে করে , মেইন ফাংশনে থেকে পয়েন্টার p এর কপি ক্রিয়েট না হয়ে সরাসরি p পয়েন্টার টি পাস হয়। এই ক্ষেত্রে আমাদের টাইপ ২ঃ কল বাই রেফারেন্স এর সাহায্য নিতে হবে। আমরা যদি ফাংশনে এ রেফারেন্স সহকারে অর্থাৎ এড্রেস (&) সহকারে ফাংশন তৈরি করি সেই ক্ষেত্রে main থেকে ফাংশনে পয়েন্টার টি পাস করার সময় কোনো কপি ক্রিয়েট না হয়ে সরাসরি ঐ পয়েন্টার টি পাস হবে। এবং ফাংশনে ঐ পয়েন্টার এর উপর যে যে অপারেশন করা হয় , সব মেইন ফাংশনে পরিলক্ষিত হবে।

#include <bits/stdc++.h>

using namespace std;

void fun(int *&p)
{
 p = NULL ; // পয়েন্টার এর রেফারেন্স সহ পাস করা হচ্ছে।
}

int main()
{
 int a = 10 ;
 int *p = &a ;

 fun(p) ; // ফাংশন কল করা হলো । যেহেতু রেফারেন্স সহকারে পাস করা হচ্ছে , p এর ভ্যালু চেঞ্জ হয়ে NULL হয়ে যাবে

 if(p==NULL ){ // p এর ভ্যালু নাল কিনা চেক করছি
 cout << "Pointer pointing to NULL " << endl ;
 }
 else{
 cout << *p << endl;

 }
}

Output : Pointer pointing to NULL

এই ক্ষেত্রে পয়েন্টার এর রেফারেন্স সহ পাস করার কারণে আমরা আমাদের কাঙ্খিত রেজাল্ট পেলাম অর্থাৎ মেইন এ থাকা পয়েন্টার p এর ভ্যালু চেঞ্জ হয়ে NULL হয়ে গেলো।

এই বিষয়টি আমাদের সামনের মডিউল গুলার জন্য গুরুত্বপূর্ণ।

Head এ ভ্যালু Insertion

head এ Node insert করা খুবই সিম্পল একটি অপারেশন । আসুন দেখে নেয়া যাক , কীভাবে head এ একটি Node insert করা যায় ।

Working Procedure:

1. New_node বানাবো।
2. New_node এর next এ বর্তমান head কে রেখে দিবো ।
3. যেহেতু new_node এখন নতুন head , তাই head কে move করে new_node এর দিকে point করে দিবো।

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

Code:

#include <bits/stdc++.h>

using namespace std;

class Node // একটা node class create করবো।
{

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

};

void insert_at_head(Node *&head, int value){
 Node *newNode = new Node(value); // নতুন Node বানালাম
 newNode->next = head; // নতুন Node এর next এ বর্তমান head কে রেখে দিলাম
 head = newNode; // বর্তমান head কে মুভ করে নতুন Node এ shift করলাম
}

Tail এ ভ্যালু Insertion

একটি লিঙ্কড লিস্টের শেষ পজিশনে যে Node থাকে তাকে আমরা সাধারণত ঐ লিঙ্কড লিস্টের tail বলে থাকি।

লিঙ্কড লিস্টের এই শেষ পজিশনের পরে আরেকটি নোড Insert করতে হলে আমাদের আগে ঐ পজিশনে যেতে হবে। এখন আমাদের tail এর position e যেতে হলে আমাদের tail টা দেখতে কেমন হবে তা জানতে হবে। যেহেতু আমরা জেনেছি যে , লিস্টের সবার শেষের নোড টি হলো tail. তাই এই নোডের পর কোনো কোনো Node থাকবে না। অর্থাৎ এই tail node এর next পয়েন্টার এ থাকবে Null.

তার মানে হলো লিঙ্কড লিস্টের শেষের পজিশনে কোনো Node এড করাকে আমরা বলছি Tail e insertion. এখন আসুন কয়েকটি সিচুয়েশন চিন্তা করে দেখি।

মনে রাখা ভালোঃ Head সবসময় লিঙ্কড লিস্টের প্রথম Node এ পয়েন্ট করা থাকে বা প্রথম Node এর এড্রেস স্টোর করে রাখে。

১মঃ যদি আমাদের লিঙ্কড লিস্ট টি খালি হয় অর্থাৎ head যদি NULL এ পয়েন্ট করা থাকে , সেইক্ষেত্রে Tail এ insert বলতে আসলে কী বুঝানো হচ্ছে।

-> লিঙ্কড লিস্ট যদি খালি হয় , তবে সেইক্ষেত্রে আমাদের তৈরি করা নতুন Node টিই হবে Head Node বা ঐ লিস্টের প্রথম নোড।

Normal একটি if statement এর সাহায্যে বিষয়টি চেক করা যায়।

Code :

 if (head == NULL) // যদি লিঙ্কড লিস্ট খালি থাকে তবে এই নোড কে head বানিয়ে দিলাম

 {
 head = newNode;
 return;
 }

২য়ঃ যদি Node এর সংখ্যা অধিক হয় তবে -> তবে এই ক্ষেত্রে আমাদের শেষের Node টি খুজে বের করতে হবে।

আমরা জানি , আমাদের লিঙ্কড লিস্টের প্রথম Node এর এড্রেস Head এ স্টোর করা আছে। আমরা চাইলে , head এক্সেস করার মাধ্যমে তার প্রথম Node টি পেয়ে যাবো। প্রথম Node খুজে পেয়ে গেলে এর পরবর্তী Node খুব সহজে ঐ প্রথম Node এর next attribute চেক করলেই পেয়ে যাবো।

এখন head খুজে পেলে , পরবর্তীতে আমরা একটি পয়েন্টার নিতে পারি Temp , যেটি আমরা প্রথমে head এর দিকে পয়েন্ট করাবো , এর পর আস্তে আস্তে সামনের দিকে আগাতে থাকবো যতক্ষন পর্যন্ত না আমরা শেষের Node টিতে পৌঁছে যায়।

তার মানে head থেকে একটি লুপ চালিয়ে আমার এমন একটি Node এ যেতে হবে যে Node এর next এ থাকবে​ ​ Null. এবং ঐ Node টি হবে আমার tail Node.​ ​

tail Node খুজে পেলে এখন একটি Node insert করা খুবই সহজ , আমাদের একটি নতুন Node ক্রিয়েট করতে হবে। এরপর আমাদের tail Node এর next এ ঐ নতুন Node এর এড্রেস টি বসিয়ে দিলেই নতুন Node টি আমাদের লিঙ্কড লিস্ট এর সাথে attach হয়ে যাবে.

Code:

#include <bits/stdc++.h>

using namespace std;

class Node // একটা node class create করবো।
{

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

};

void insert_at_tail(Node *&head, int val) // reference সহ পয়েন্টার পাস করছি যাতে করে main এর head পয়েন্টার change হয়ে যায়
{

 Node *newNode = new Node(val); // নতুন একটি Node ক্রিয়েট করলাম

 // Important : Exception Handling
 if (head == NULL) // যদি লিঙ্কড লিস্ট খালি থাকে তবে এই নোড কে head বানিয়ে দিলাম
 {
 head = newNode;
 return;
 }

 Node *temp = head; // লুপের জন্য temp পয়েন্টার নিলাম

 while (temp->next != NULL) // যতক্ষন tail এ আসছি না , ততক্ষন লুপ চলবে
 {
 temp = temp->next; // প্রতি লুপে temp কে ডানে অর্থাৎ পরবর্তী Node এ shift করছি
 }

 temp->next = newNode; // tail এর next পয়েন্টার এ নতুন Node এর এড্রেস রেখে দিচ্ছি এবং এর মাধ্যমে Node টি লিঙ্কড লিস্টে এড হয়ে যাবে।
}

void print(Node *head)
{
 Node *temp = head;

 while (temp != NULL)
 {
 cout << temp->val << " ";
 temp = temp->next;
 }
 cout << endl;
}

int main()
{
 Node *head = NULL;
 insert_at_tail(head, 1);
 insert_at_tail(head, 2);

 print(head);
}

Output : 1 2

যেকোন পজিশনে ভ্যালু Insertion

গত মডিউলে আমরা দেখেছি কীভাবে linked list এর শেষে একটি Node insert করা যায় , এই মডিউলে দেখবো কীভাবে লিঙ্কড লিস্টের যেকোন পজিশনে একটি Node insert করা যায় তা দেখবো।

প্রথমে দেখে নেয়া যাক Initial অবস্থায় আমাদের linked list টা দেখতে কেমন। এখানে সুবিধার জন্য আমরা indexing করে নিয়েছি।

এখন ধরেন , আমরা চাচ্ছি ২ নাম্বার ইন্ডেক্স এ একটি নতুন Node এড করবো ।​ ​ এর জন্য আমাদের কী করতে হবে তা ছবির মাধ্যমে দেখি।

Working Procedure:

1. নতুন Node বানাবো , যেটাকে New_node বলতে পারি
2. যে index এ Node এড করবো ঐ index এর আগের Node এ যাবো ,যেটাকে আমরা Previous_node বলতে পারি। একই সাথে index এ যে Node আছে তাকে আমরা next_node বলতে পারি।
3. New_node এর next পয়েন্টার এ next_node কে রেখে দিবো।
4. Previous_Node এর next পয়েন্টার এ new_node এর এড্রেস রেখে দিবো

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

Code:

#include <bits/stdc++.h>

using namespace std;

class Node // একটা node class create করবো।
{

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

};

void insert_at_position(Node *&head, int index, int value)
{

 Node *newNode = new Node(value); // নতুন Node বানিয়ে নিলাম

 Node *temp = head; // temp পয়েন্টার এ head রেখে দিলাম

 for (int i = 1; i <= index - 1; i++)
 {
 temp = temp->next;
 }
 // এখানে temp এ যে index এ Node insert করতে হবে তার previous Node আছে
 // temp->next এ আছে তার পরের Node
 newNode->next = temp->next; // New_node এর next পয়েন্টার এ next_node কে রেখে দিলাম
 temp->next = newNode; //Previous_Node এর next পয়েন্টার এ new_node এর এড্রেস রেখে দিলাম
}

insert_at_position() ফাংশনের লুপের logic: আমরা যদি 2 number index এ​ ​ Node insert করতে চাই তবে আমাদের​ ​ temp কে 1 number index এ নিয়ে যেতে হবে। যেহেতু আমাদের temp , head এ পয়েন্ট করা থাকে , তাহলে temp কে একবার move করলে 1 number index এর Node এ চলে যাবে , তার মানে index-1 = 2-1 = 1 বার লুপ চালাতে হয়েছে।

এই মেথডে head এ কোনো Node insert করা যাবে না। নেক্সট মডিউলে আমরা head এ Node insert করা দেখবো।​ ​

Complexity analysis of insertion operations

আমরা আজকে তিন ধরনের Insertion অপারেশন দেখেছি।

1. Insert at head
2. Insert at tail
3. Insert at any position

শুরুতেই দেখা Insert at head এই অপারেশনের টাইম কমপ্লেক্সিটি কেমন হবে। আমরা যদি পূর্বের মডিউল থেকে insert at head এর কোডটি দেখিঃ

void insert_at_head(Node *&head, int value)
{
 Node *newNode = new Node(value); // নতুন Node বানালাম
 newNode->next = head; // নতুন Node এর next এ বর্তমান head কে রেখে দিলাম
 head = newNode; // বর্তমান head কে মুভ করে নতুন Node এ shift করলাম
}

এই ক্ষেত্রে আমরা নতুন একটি নোড Head এ Insert করছি। এবং এই ক্ষেত্রে তিনটি অপারেশনের মাধ্যমেই কাজটি হয়ে যাচ্ছে। নতুন নোডটি তৈরী করা, নতুন নোডের নেক্সট - এ আগের Head কে যুক্ত করা এবং Head কে আপডেট করে নতুন নোড এ shift করা। তাই এই ক্ষেত্রে আমাদের constant টাইম দরকার হচ্ছে। তাই Insert at head এর টাইম কমপ্লেক্সিটি O(1)

এখন দেখা যাক Insert at tail এর টাইম কমপ্লেক্সিটি কেমন হবে। আমাদের দেখা insert at tail এর কোডটি যদি পুনরায় দেখি

void insert_at_tail(Node *&head, int val) // reference সহ পয়েন্টার পাস করছি যাতে করে main এর head পয়েন্টার change হয়ে যায়
{
 Node *newNode = new Node(val); // নতুন একটি Node ক্রিয়েট করলাম

 // Important : Exception Handling

  if (head == NULL) // যদি লিঙ্কড লিস্ট খালি থাকে তবে এই নোড কে head বানিয়ে দিলাম
  {
    head = newNode;
    return;
  }
 Node *temp = head; // লুপের জন্য temp পয়েন্টার নিলাম
 while (temp->next != NULL) // যতক্ষন tail এ আসছি না , ততক্ষন লুপ চলবে
 {
    temp = temp->next; // প্রতি লুপে temp কে ডানে অর্থাৎ পরবর্তী Node এ shift করছি
 }
   temp->next = newNode; // tail এর next পয়েন্টার এ নতুন Node এর এড্রেস রেখে দিচ্ছি এবং এর মাধ্যমে Node টি লিঙ্কড লিস্টে এড হয়ে যাবে।
}

এই ক্ষেত্রে tail এ Insert এর জন্যে আমাদের পুরো Linked List Traverse করে প্রথমে বর্তমান Tail এর কাছে যেতে হচ্ছে। তারপর নতুন নোড তৈরী করে সেই নতুন নোডকে বর্তমান tail এর সাথে যুক্ত করতে হচ্ছে। যেহেতু আমাদের পুরো List Traverse করতে হচ্ছে তাই এই ক্ষেত্রে যদি List এর সাইজ N হয় তবে আমাদের টাইম কমপ্লেক্সিটি হবে O(N).

এখন আসি Insert at any position এর জন্যে টাইম কমপ্লেক্সিটি কেমন হবে। তো প্রথমের এর কোডটি দেখে নেয়া যাক

void insert_at_position(Node *&head, int index, int value)
{
 Node *newNode = new Node(value); // নতুন Node বানিয়ে নিলাম

 Node *temp = head; // temp পয়েন্টার এ head রেখে দিলাম

 for (int i = 1; i <= index - 1; i++)
 {
   temp = temp->next;
 }
 // এখানে temp এ যে index এ Node insert করতে হবে তার previous Node আছে
 // temp->next এ আছে তার পরের Node
 newNode->next = temp->next; // New_node এর next পয়েন্টার এ next_node কে রেখে দিলাম
 temp->next = newNode; //Previous_Node এর next পয়েন্টার এ new_node এর এড্রেস রেখে দিলাম
}

যেহেতু insert করার পজিশন একেক সময় একেক রকম হতে পারে। তার মানে এই ক্ষেত্রে আমরা বিভিন্ন ধরনের টাইম কমপ্লেক্সিটি পাবো। যদি ইনডেক্স 0 তে insert করতে বলা হয় সেক্ষেত্রে টাইম কমপ্লেক্সিটি হবে O(1) আবার যদি Tail এ insert করতে বলা হয় সেক্ষেত্রে আমাদের tail পর্যন্ত Traverse করে যেতে হবে আবার যদি Middle কোনো পয়েন্টেও ইনসার্ট করতে বলা হয় সেক্ষেত্রেও কিন্তু আমাদের ঐ ইনডেক্স পর্যন্ত ট্রাভার্স করে যেতে হবে। তাই এই ক্ষেত্রে আমাদের Worst case time complexity হবে O(N) । এবং এটাই insert at tail এর টাইম কমপ্লেক্সিটি O(N)

Insert at tail Optimized

এই মডিউলে আমরা দেখবো insert at tail কে কিভাবে optimized করা যায়। পূর্বে আমরা যেভাবে insert at tail implement করেছি সেখানে আমরা টাইম কমপ্লেক্সিটি পেয়েছিলাম O(N)

এবং যদি লক্ষ্য করে থাকি পূর্বে আমরা শুধু Linked List এর প্রথম নোডের এড্রেস সেইভ করে রেখেছিলাম Head ব্যবহারের মাধ্যমে।

এই ক্ষেত্রে আমরা যা করবো তা হলো Head এর পাশাপাশি আমরা আমাদের Linked List এর শেষ নোডের এড্রেসটি সেইভ করে রাখবো Tail ব্যবহার করে। অর্থাৎ আমাদের কাছে List এর প্রথম এবং শেষ নোডের এড্রেস স্টোর করা থাকবে।

তাই এই ক্ষেত্রে যদি আমাদের Tail এ ইনসার্ট করতে হয় আমরা সরাসরি আমাদের Linked List এর বর্তমান tail নোডে চলে যেতে পারবো যেহেতু tail এর এড্রেস আমরা সেইভ করে রেখেছি "tail" নামক একটি পয়েন্টার ভ্যারিয়েবলের মাধ্যমে। অর্থাৎ এই ক্ষেত্রে আমাদের head থেকে এক এক করে ট্রাভার্স করে tail এ যেতে হচ্ছে না। যা কিন্তু আমাদের অপারেশনকে কমিয়ে দিচ্ছে।

আর Tail নোড যদি আমাদের কাছে থাকে সেই ক্ষেত্রে নতুন একটি নোড তৈরী করে সেটাকে কিভাবে tail এ ইনসার্ট করতে হয় তা ইতিমধ্যে আমরা দেখে নিয়েছি।

আমরা নতুন নোডটি তৈরী করবো। বর্তমান tail এর নেক্সট এ নতুন নোডটিকে যুক্ত করবো। এবং tail কে সরিয়ে নতুন নোডে নিয়ে যাবো।

যদি কোড দেখি তাহলে বিষয়টি আরও পরিষ্কার হয়ে যাবে।

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

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

// Insert at tail optimized version
void insert_at_tail(Node* &head, Node* &tail, int val) {
    Node* newnode = new Node(val);

    if (head == NULL) { // Head NULL হলে নতুন নোডটিই head/tail হবে।
        head = newnode;
        tail = newnode;
        return;
    }
    // নতুন নোডকে বর্তমান tail এর নেক্সট এ যুক্ত করা এবং tail কে update করা হচ্ছে।
    tail->next = newnode;
    tail = newnode;
}

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

    insert_at_tail(head, tail, 10);
    insert_at_tail(head, tail, 20);

    return 0;
}

যেহেতু এই ক্ষেত্রে আমাদের আর সম্পূর্ণ লিস্ট ট্রাভার্স করতে হচ্ছে না। সরাসরি আমরা Tail এর এক্সেস পাচ্ছি তাই এখানে আমাদের টাইম কমপ্লেক্সিটি হবে O(1)