Register Now

Login


Lost Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Login


Register Now

Welcome to Our Site. Please register to get amazing features .

লিঙ্কড লিস্ট-০১ (Singly Linked List-01)[Data insertion at the end position]

লিঙ্কড লিস্ট-০১ (Singly Linked List-01)[Data insertion at the end position]

বাংলাদেশের বড় কোন সন্ত্রাসী গ্রুপের  লিডারকে ধরে শাস্তির আওয়তায় নিয়ে আসতে হবে। সেক্ষেত্রে আইনপ্রয়োগকারী সংস্থা কিভাবে তাকে ধরবে?

প্রথমেই মাঠ পর্যায়ে যারা সন্ত্রাস করে তাদের কেউ একজনকে (মনে করো তার নাম কালু মাস্তান) গ্রেপ্তার করা হলো। সে শুধু মাত্র তার ইমিডিয়েট উপরের বসের (তার নাম জেলু মাস্তান) নাম ঠিকানা জানে ।  এখন জেলু মাস্তানকে গ্রেপ্তার করা হলো, সে তার উপরের বস (নাম লালু মাস্তান ) যাকে চিনে তার নাম ঠিকানা বলে দিলো। এভাবে প্রত্যেকের কাছে থেকে তার উপরের বসের নাম ঠিকানা নিয়ে লিডারকে গ্রেপ্তার করা সম্ভব হলো। অর্থাৎ একজনের কাছে শুধুমাত্র তার পরের জনের তথ্য থাকবে ( তাদের নিরাপত্তার স্বার্থে)।

এটাই হচ্ছে লিঙ্কড লিস্ট।

Data Insertion in the End Position:

এখন, আমাদের কিছু সংখ্যা আছে যেগুলেোকে পর পর ইনপুট হিসেবে নিতে হবে। যেমন- প্রথমে 2, তারপর 3 , তারপর 4 ।

এখন 2 যে ‍মেমোরিতে আছে তার এড্রেস মনে করো ২০০, আর 3 যে মেমোরিতে আছে তার এড্রেস ২১৬, এবং 6 যে মেমেরিতে আছে তার এড্রেস হচ্ছে ২৪৮ (যেকোন ভিন্ন ভিন্ন  এড্রেসে যে কোন ভিন্ন ভিন্ন সংখ্যা থাকতে পারে)।  নিচের দিকে লক্ষ্য করো-

 

এখন ২ এর পর ৩ এটা কিভাবে বুঝবে? অথবা ৩ এর পর ৬ এই ধারবাহিকতা কিভাবে বজায় রাখতে হবে?

উপরের সন্ত্রাসী গ্রুপের মতো আমরা যদি 2 এর কাছে 3 এর এড্রেসটা রাখি তাহলে খুব সহজেই 2 এর পর যে 3 সেটার ধারাবাহিকতা থাকবে। আবার 3 এর কাছে যদি 6 এর এড্রেসটা রাখি তবে 3 এর পর যে 6 সংখ্যাটি আছে সেটা পাওয়া যাবে। এভাবে যত সংখ্যা যোগ করবো প্রত্যেকটাতে তার পরের সংখ্যাটির  এড্রেস সংরক্ষিত থাকবে। অর্থাৎ-

অর্থাৎ প্রতিটা সংখ্যার জন্য একটা করে ব্লক তৈরি করতে হবে যেখানে প্রদত্ত সংখ্যাটি থাকবে এবং পরের সংখ্যাটির অ্যাড্রেস সংরক্ষিত থাকবে। এবং সর্বশেষ সংখ্যাটির পর যেহেতু আর কোন সংখ্যা থাকবে না, তাই সর্বশেষ সংখ্যাটির এড্রেস NULL হবে।

এখন চলো আমরা উপরের অ্যালগরিদমটা কোডে কিভাবে লিখবো সেটা দেখি।

প্রথমে প্রতিটি সংখ্যার জন্য একটা করে Node বা ব্লক তৈরি করতে হবে। এটা করার জন্য আমরা Structure এর সহায়তা নিবো।

struct node{
    int data;
    struct node* next; //c++ এর জন্য struct না লিখে শুধুমাত্র node* next লিখতে হবে।
}

node নামে একটা স্ট্রকচার তৈরি করা হয়েছে যেখানে int টাইপের একটা data থাকবে এবং node* next দিয়ে বুঝাচ্ছে  এখানে node নামে আরেকটি স্ট্রকচারের (পরবর্তী সংখ্যার) অ্যাড্রেস পয়েন্ট করা থাকবে যা next ভেরিয়েবলে থাকবে।

এখন সংখ্যাটির শুরু অবস্থান বুঝানোর জন্য head নামক একটা node বানাতে হবে যেটা দ্বারা বুঝবো সংখ্যাটি কোথায় থেকে শুরু হয়েছে। যদি প্রথমে কোন সংখ্যা না থাকে তবে head নামক node টি NULL থাকবে। সেক্ষেত্রে প্রথমে যে সংখ্যাটি বসবে সেই সংখ্যাটিকেই তখন head হিসেবে ধরা হবে। অর্থাৎ head তখন প্রথম সংখ্যাটির অ্যাড্রেস ধারণ  করবে। আর সবসময় নতুন সংখ্যার জন্য আমরা nptr (new pointer) নামক ভ্যারিয়েবল ব্যবহার করবো যেটা সবসময় নতুন node ক্রিয়েট করবে। তাহলে ব্যপারটি এমন হবে-

node* head = NULL;
node* nptr = (node*) malloc(size of(node));
nptr->data = 2;
nptr->next = NULL;
if(head == NULL){
   head = nptr; // প্রথম নোডটি হেড হিসেবে ব্যবহার করবো।
}

সি এর জন্য উপরের malloc() ফাংশটি ব্যবহার করা হয় যা ডাটা রাখার জন্য মেমরিতে নতুন জায়গা তৈরি করে। এটা ভয়েড টাইপের ডাটা রিটার্ন করে। তাই টাইপকাস্ট করে এটা node টাইপের করা হয়েছে। এটা কি পরিমাণ জায়গা তৈরি করবে সেটা বুঝানোর জন্য size of (node) দেওয়া হয়েছে অর্থাৎ এটা node এর সমপরিমাণ জায়গা তৈরি করবে।

সি++ এর জন্য এটাকে খুব সহজে new নামক ফাংশন ব্যবহার করে তৈরি করা যায়-

node* head = NULL;
node* nptr = new node;
nptr->data = 2;
nptr->next = NULL;
if(head == NULL){
   head = nptr; // প্রথম নোডটি হেড হিসেবে ব্যবহার করবো।
}
এখন, হেড নোডটি পেয়ে যাওয়ার পর আমাদের কি করতে হবে? পরের নোডের এড্রেসকে হেডের next পয়েন্ট করবে। অর্থাৎ এখানে ২ যদি হেড নোড হয়, তবে ২ এর node এর next এ পরের নোডের অর্থাৎ 3 এর এড্রেস ২১৬ ধারণ করবে। এখন আমরা যদি প্রতিবার head নোড ব্যবহার করে নতুন নোডটি তার সাথে লিঙ্ক করে দিই, তবে আমরা হেড নোডটি হারিয়ে ফেলবো এবং কোথা থেকে ডাটা ইনপুট শুরু হয়েছে সেটা বুঝতে পারবো না। সেজন্য আমরা আরেকটা টেম্পরারি ভ্যারিবেল  পয়েন্টার tptr নিবো যার কাজ হবে পুরাতন নোডকে পয়েন্ট করা। তাহলে tptr এর কাজ হবে সর্বশেষ নোডের  next এ নতুন নোডের এড্রেস পয়েন্ট করে দেওয়া। অর্থাৎ
node* head = NULL;
node* nptr = new node;
nptr->data = 2;
nptr->next = NULL;
if(head == NULL){
   head = nptr;
}
else{
    node* tptr = head;
    while(tptr->next!=NULL){
         tptr = tptr->next;
     }
    tptr->next = nptr;
}

এখানে while লুপটি ব্যবহার করা হয়েছে সর্বশেষ নোডটি খুঁজে বের করার জন্য। সর্বশেষ নোড কোনটি হবে? যার next এর এড্রেস NULL । সর্বশেষ নোডটি খুঁজে বের করার পর tptr এর next টি নতুন নোডকে পয়েন্ট করবে।

উপরের সবটুকু অংশকে যদি আমরা create নামক একটি ফাংশন আকারা লিখি যার কাজ হবে নতুন ডাটা বা সংখ্যার নোড তৈরি করে পরস্পর যুক্ত করা-

void create(int value){
    node* nptr = new node;
    nptr->data = value;
    nptr->next = NULL;
    if(head==NULL){
       head = nptr;
     }
    else{
       node* tptr = head;
       while(tptr->next!=NULL){
          tptr = tptr->next;
       }
       tptr->next = nptr;
     }
}
এখন আমরা ডাটাগুলোকে প্রিন্ট করবো কিভাবে? head থেকে শুরু করে যতক্ষণপর্যন্ত আমরা NULL নোড না পাই।
নিচের কোডটি দেখো-
void print(){
    node* tptr = head;
    while(tptr!=NULL){
        printf("%d ",tptr->data);
        tptr= tptr->next;
    }
    printf("\n");
}
নিচে সম্পূর্ণ কোডটি দেওয়া হলো (সি++ এর জন্য)–
#include<iostream>
using namespace std;
struct node{
    int data;
    node* next;
};
node* head = NULL;
void create(int value){
    node* nptr = new node;
    nptr->data = value;
    nptr->next = NULL;
    if(head==NULL){
       head = nptr;
     }
    else{
       node* tptr = head;
       while(tptr->next!=NULL){
           tptr = tptr->next;
       }
       tptr->next = nptr;
     }
}
void print(){
    node* tptr = head;
    while(tptr!=NULL){
        cout<< tptr->data << " ";
        tptr= tptr->next;
    }
    cout<<endl;
}
int main(){
    create(2);
    print();
    create(3);
    print();
    create(6);
    print();
}
ধন্যবাদ সাথে থাকার জন্য…

আশা করি বুঝতে পেরেছো।

Author: MSI Shafik

(পোস্ট পড়ার পর কেমন লাগল সেটা কমেন্ট সেকশনে জানিয়ে দেবেন)

About Ask me anything


Follow Me

Leave a reply

What is the capital of Egypt? ( Cairo )