পোস্টটি পড়া হয়েছে 3,240 বার
Data Structure in Bengali

লিংকড লিস্ট – ৫ [Circular Singly Linked List: Insert, Delete and Print]

Post updated on 28th June, 2017 at 12:58 am

লিংকড লিস্টের আগের চারটি পর্বে দেখানো হয়েছিল Singly Linked List এবং Doubly Linked List. তুমি যদি ঐ পর্বগুলো বুঝে থাকো তাহলে Circular Linked List বা আরো specific ভাবে বললে Circular Singly Linked List বুঝতে তোমার কোনো অসুবিধা হবে না। তাই আগের টপিকগুলো ভুলে গিয়ে থাকলে প্রথম লাইনে দেয়া লিংক দুটিতে গিয়ে একটু চোখ বুলিয়ে আসো। Singly Linked List এ দেখিয়েছিলাম যে লিস্টের শেষ নোডটি তার next node হিসাবে পয়েন্ট করে NULL-কে। আর সার্কুলার লিংকড লিস্টে শেষ নোডটির next node হিসাবে পয়েন্ট করা থাকে head node-কে। নিচের ছবি দেখলেই ব্যাপারটা পরিষ্কার হয়ে যাবে। Circular Singly Linked List এর মধ্যে Singly Linked List এর বৈশিষ্ট্য থাকবে, একই সাথে এটি সার্কুলারও হবে। সার্কেল তৈরি করার জন্যই শেষ নোডের next node হিসাবে পয়েন্ট করা হবে head node-কে।

Circular Singly Linked List
Circular Singly Linked List. Collected from Wikipedia

Advantages of Circular Linked List

১. লিস্টের যে কোনো নোডকে starting node ধরে পুরো লিস্টকে traverse করা যায়। পুরো লিস্টটা একটা traverse করা তখনই শেষ হবে যখন starting node টা দ্বিতীয় বার visited হবে।

২. Circular Linked List দিয়ে Queue ইমপ্লিমেন্ট করা যায়। এতে front, rear দুইটা আলাদা পয়েন্টার রাখার দরকার হয় না। সার্কুলার লিংকড লিস্টের লাস্ট নোডটায় সব সময় ডেটা push হবে। আর pop করতে হবে last node এর পরের নোড থেকে (অর্থাৎ head node থেকে)।

৩. ধরো কতগুলো কাজের একটা লিস্ট আছে। এই কাজগুলোকে নির্দিষ্ট সময় পরপর রিপিট করা দরকার। এধরনের কেসে সার্কুলার লিংকড লিস্ট ব্যবহার করা যায়।

যেমনঃ Multiplayer game হিসাবে তুমি একটা লুডু গেম বানাতে চাও। সেখানে কিন্তু ২, ৩ বা ৪ জন প্লেয়ার থাকতে পারে। তাদের সবার খেলার ‘দান’ (turn) কিন্তু রিপিটেডলি চলতেই থাকবে। এটা করতে চাইলে তোমাকে circular singly linked list ব্যবহার করতে হবে।

আরেকটা উদাহরণ দেই। আমাদের কম্পিউটারে অনেকগুলো অ্যাপ্লিকেশন বা সফটওয়্যার এক সাথে রান করতে থাকে। তুমি ব্রাউজারে এই লেখাটি পড়ছো, ঘড়িটা তোমাকে সময় দেখাচ্ছে, মিডিয়া প্লেয়ারে কোনো একটা অডিও চলছে। এই সবগুলো কাজ আমাদের কাছে মনে হচ্ছে এক সাথে হচ্ছে। মনে হচ্ছে সবগুলো কাজ পিসির প্রসেসর at a time করে যাচ্ছে। আসলে তা না। প্রসেসর কয়েক মিলি সেকেন্ড বা কয়েক ন্যানো সেকেন্ড তোমার ব্রাউজারকে প্রসেস করছে, কয়েক ন্যানো সেকেন্ড ঘড়িকে প্রসেস করছে, কয়েক ন্যানো সেকেন্ড মিডিয়া প্লেয়ারকে প্রসেস করছে। এরপর আবার ব্রাউজার, আবার ঘড়ি, আবার মিডিয়া প্লেয়ার… এভাবে একটার পর একটা কাজ হচ্ছে। লিস্টের সবগুলো কাজ এক দফা প্রসেস হলে আবার লিস্টের শুরু থেকে প্রসেস করা হচ্ছে। উপরের ছবির প্রথম নোডটাকে ব্রাউজার, দ্বিতীয় নোডটাকে ঘড়ি আর তৃতীয় নোডটাকে মিডিয়া প্লেয়ার ধরে চিন্তা করো। দেখো তারা কিন্তু ঘুরতেই থাকবে। এই ধরনের repeated কাজের লিস্ট থাকলে এসব ক্ষেত্রে Circular Linked List ব্যবহার করা যায়।

Operations of Circular Linked List

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

  1. Insert node at list (Position: head, tail and middle)
  2. Delete node from list (Position: head, tail and middle)
  3. Traverse the list (Print the full list)

Insert a node at Circular Linked List

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

Insert node at the head

চারটা স্টেপে কাজটা করতে পারি। যথাঃ

  1. নতুন একটা নোড তৈরি করে সেটার next pointer হিসাবে initially নিজেকেই পয়েন্ট করে রাখা
  2. নতুন নোডের next pointer এর মান update করা। next pointer হবে head node
  3. tail node এর next pointer এর মান আপডেট করা। next pointer পয়েন্ট করবে নতুন নোডকে
  4. head node এর মান আপডেট করা। এটি এখন পয়েন্ট করবে নতুন তৈরি করা নোডকে
void insert_at_head(int number)
{
    node *newNode = (node *) malloc(sizeof(node));
    newNode->number = number;
    newNode->next = newNode;

    if(head==NULL){
        head = newNode;
        tail = newNode;
    }
    else{
        newNode->next = head;
        tail->next = newNode;
        head = newNode;
    }
}

head ও tail দুটি global pointer type variable. উপরের ফাংশনটার মাধ্যমে একটা integer type number আমাদের সার্কুার লিংকড লিস্টের শুরুতে যোগ করতে পারব। যেহেতু নতুন একটা নোড যুক্ত হবে তাই শুরুতেই একটা নতুন নোড বানিয়ে নিলাম। এর pointer of next node হিসাবে তার নিজের memory address-ই assign করা হয়েছে। অর্থাৎ এই মুহূর্তে নতুন নোডটি নিজেই নিজেকে পয়েন্ট করে আছে।

এরপর চেক করা হচ্ছে head-টা NULL কিনা। যদি NULL হয় এর মানে লিস্টটা এখনো empty. তাই এর head ও tail উভয়েই newNode এর রেফারেন্স অ্যাসাইন করা হল। অর্থাৎ লিস্টে একটা নোড আছে। এটাই head, এটাই tail. আর যদি লিস্টটা ফাঁকা না হয় তাহলে নতুন নোডটাকে head এর আগের পজিশনো বসিয়ে তাকে head বানিয়ে দিতে হবে। এই কাজটা করার জন্য newNode এর next node হিসাবে পয়েন্ট করানো হচ্ছে head-কে। tail->next কিন্তু এখনো head-ই আছে। তাই পরের লাইনে tail->next হিসাবে পয়েন্ট করা হয়েছে newNode-কে। List এর শুরুর track রাখার জন্য যেই head node রাখা হয়েছে শেষ লাইনে তার মানটা আপডেট করা হলো head = newNode করার মাধ্যমে।

Insert node at the tail

নিচের স্টেপগুলো ফলো করে কোনো সার্কুলার লিংকড লিস্টের end position এ একটা নোড যুক্ত করা যায়।

  1. নতুন একটা নোড বানানো (newNode)। এর next pointer হিসাবে নিজেকেই পয়েন্ট করা (newNode->next = newNode)
  2. head নোডের রেফারেন্স দ্বারা newNode এর next pointer এর মান আপডেট করা (newNode->next = head)
  3. tail node এর next pointer এর মান newNode এর রেফারেন্স দিয়ে আপডেট করা (tail->next = newNode)
void insert_at_tail(int number)
{
    node *newNode = (node *) malloc(sizeof(node));
    newNode->number = number;
    newNode->next = newNode;

    if(head==NULL){
        head = newNode;
        tail = newNode;
    }
    else{
        tail->next = newNode;
        newNode->next = head;
        tail = newNode;
    }
}

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

Insert node at the middle

head – tail বাদে লিস্টের মাঝামাঝি পর্যায়ের যে কোনো পজিশনে কোনো নোড যুক্ত করতে চাইলে নিচের স্টেপগুলো ফলো করা যায়। এখানো নোড এড করা হচ্ছে লিস্টের নোডগুলোর পজিশন নাম্বার অনুসারে। তোমার দরকারের ভিত্তিতে এটা নিজের মত করে কাস্টমাইজড করে নিতে হবে। যেমন তোমার দরকার হতে পারে যেই নোডের ডেটার নাম্বারের ভ্যালু ৫০১ সেই নোডের পরে নতুন একটা নোড যোগ করা। অথবা, অমুক মেমরি লোকেশনে যেই নোডটা আছে তার পরে নতুন একটা নোড যোগ করাইত্যাদি। এই উদাহরণে নোডের ক্রম নাম্বার অনুযায়ী নতুন নোড যুক্ত করা হচ্ছে। স্টেপগুলো হচ্ছেঃ

  1. নতুন একটা নোড তৈরি করা (newNode)
  2. desired position এর নোড (current node) ও তার আগের নোডটা (temp node) খুঁজে বের করা
  3. temp node এর next pointer এর মান newNode দ্বারা update করা (temp->next = newNode)
  4. newNode এর next pointer এর মান current node এর মেমরি অ্যাড্রেস দ্বারা আপডেট করা (newNode->next = current)
void insert_at_middle(int number, int position)
{
    if(position==1){
        insert_at_head(number);
        return;
    }
    else if(position>1 && head!=NULL){
        node *current = head;
        node *temp = (node *) malloc(sizeof(node));
        int count = 0;

        do{
            count++;
            temp = current;
            current = current->next;
        }   while(current->next != head && count<position-1);

        if(count==position-1){
            if(temp==tail)
                insert_at_tail(number);
            else{
                node *newNode = (node *) malloc(sizeof(node));
                newNode->number = number;

                temp->next = newNode;
                newNode->next = current; 
                //you can also write: newNode->next = current;
                //Both are same
            }
            return;
        }
    }
    printf("Position does not exist!\n");
}

উক্ত ফাংশনের শুরুতে চেক করা হয়েছে পজিশন 1 কিনা। যদি পজিশন 1 হয় তাহলে front এ কোনো নোড যুক্ত করার ফাংশনটা কল করে দেয়া হয়েছে। এরপর ভিতরে Loop চালিয়ে কাংখিত পজিশনের নোড (current) ও তার আগের পজিশনের নোড (temp) বের করা হয়েছে। যদি desired position-টি লিস্টের সর্বশেষ নোড হয় তাহলে তাহলে end position এ কোনো নোড যুক্ত করার ফাংশন কল করা হয়েছে। অন্যথায় else{} ব্লকের ভিতরে নতুন নোডটিকে যোগ করা হয়েছে। নতুন নোড যোগ করার আগে temp এর next pointer পয়েন্ট করে ছিল current নোডকে। আমাদের উদ্দেশ্য হচ্ছে current নোডের স্থলে newNode কে বসানো। তাই temp এর next pointer এর মান আপডেট করা হয়েছে newNode এর মেমরি অ্যাড্রেস দিয়ে (temp->next = current) আর newNode এর next pointer এর মান আপডেট করা হয়েছে current node এর মেমরি অ্যাড্রেস দিয়ে (newNode->next = current). current এর পরিবর্তে এখানে temp->next-ও লিখা যায়। কারণ temp->next আসলে current node এর মেমরি অ্যাড্রেসই hold করে।

Delete a node from a Circular Linked List

Insert এর মত delete এর ক্ষেত্রেও তিন রকম নোড ডিলেট করা যায়। Head node, tail node ও মাঝের পজিশনের কোনো নোডকে ডিলেট করা যায়।

Delete head of a Circular Linked List

লিস্টের head কে ডিলেট করার অর্থ হচ্ছে নতুন head হবে পুরাতন head এর next pointer. অর্থাৎ head = head->next; আর tail এর next pointer নতুন head দিয়ে আপডেট করতে হবে (tail->next = head->next). temp node লিস্টের পুরাতন head-কে পয়েন্ট করে ছিল। যেহেতু এটা ডিলেট করতে হবে তাই মেমরিতে এর অস্তিত্ব রেখে দিয়ে লাভ নাই। তাই নিচের ফাংশনের শেষ লাইনে free(temp) করার মাধ্যমে মেমরিতে দখল করে রাখা স্পেস remove করে দেয়া হল।

void delete_head(){
    if(head==NULL)  return;

    node *temp = head;
    tail->next = head->next;
    head = head->next;

    free(temp);
}

Delete tail of a Circular Linked List

লিস্টের tail node কে ডিলেট করতে হলে tail এর previous node অর্থাৎ যেই নোডটা tail-কে পয়েন্ট করে আছে সেই নোডটিকে খুঁজে বের করতে হবে। নিচের কোডে লুপ ঘুরিয়ে কাজটা করা হয়েছে। current ও temp নামের দুইটা নোড নেয়া হয়েছে। লুপ শেষ হলে current node এ পাওয়া যাবে List এর end node. আর temp node এ পাওয়া যাবে end node এর আগের নোড।

আমাদের কাজটা হবে temp node এর next pointer এর মান head node দ্বারা আপডেট করে দেয়া (temp->next = head)। তাহলে temp node আর current node (end node of the list)-কে পয়েন্ট করবে না। পয়েন্ট করবে head node-কে। তাহলে current নোডটা লিস্ট থেকে ছিটকে পড়বে। অতপর tail node কে আপডেট করে দিতে হবে temp নোড দ্বারা। কারণ এটিই এখন সর্বশেষ নোড। সব শেষে যথারীতি current node কে free করে দিতে হবে। যেন র‍্যামে জায়গা দখল করে না থাকে।

void delete_tail(){
    if(head==NULL)  return;

    node *temp = head;
    node *current = head;
    while(current->next != head){
        temp = current;
        current = current->next;
    }
    // now, `current` node is the TAIL. `temp` is the previous node of TAIL.
    // `current->next` is HEAD

    temp->next = head; //also can write temp->next = current->next;
    tail = temp;
    free(current);
}

Delete a middle node of a Circular Linked List

Middle position এ insert এর মত একই ভাবে লুপ চালিয়ে desired position খুঁজে বের করতে হবে। যেই নোডটাকে delete করতে হবে নিচের কোড অনুসারে সেটা হচ্ছে current নোড। আর temp হচ্ছে current node এর previous node. ডিলেট করার আগের অবস্থায় temp এর next pointer হচ্ছে current নোড। যেহেতু current কে ডিলেট করতে হবে তাই temp এর next pointer এর মান আপডেট করে দিতে হবে current node এর next pointer এর মাধ্যমে (temp->next = current->next). ফলে current node-কে এখন আর কেউ পয়েন্ট করে রইলো না। এটা লিস্টের বাইরে ছিটকে গেল। কিন্তু এখনো র‍্যামে স্পেস নিয়ে আছে। তাই free(current) করার মাধ্যমে মেমরি থেকেও চিরতরে মুছে ফেলা হল current node এর existence!

void delete_middle(int position){
    if(head==NULL)  return;

    if(position==1){
        delete_head();
        return;
    }

    node *current = head;
    node *temp;
    int count = 0;

    do{
        count++;
        temp = current;
        current = current->next;
    }   while(current->next != head && count<position-1);

    if(count==position-1){
        if(current==tail){
            delete_tail();
            return;
        }

        temp->next = current->next;
        free(current);
        return;
    }

    printf("Position (%d) does not exist!\n", position);
}

Insert এর মতই চেক করা হচ্ছে head অথবা tail-কে ডিলেট করতে চাচ্ছি কিনা। যদি তাই হয় সেক্ষেত্রে শুরুতে বানানো দুইটা ফাংশন কল করে কাজ সারা হয়েছে। কাজ শেষ হবার সাথে সাথেই return কীওয়ার্ড ব্যবহার করে ফাংশনকে ঐখানেই terminated করে দেয়া হয়েছে। Function body’র মোট তিন জায়গায় return করা হয়েছে। এর যে কোনো একটায় function terminated না হলে বুঝতে হবে যেই পজিশন ডিলেট করতে চাওয়া হয়েছে সেই পজিশনটা আসলে লিস্টে নাই। তাই শেষ লাইনে Position does not exist মেসেজ প্রিন্ট করা হয়েছে। Insert at middle position এর ফাংশনেও একই কাজ করা হয়েছে।

Print the full Circular Linked List

পুরো লিস্টটা traverse করার জন্য যে কোনো একটা নোডকে head ধরে সেটা থেকে traverse শুরু করে লিস্টটা ঘুরে ঐ head নোডের আগ পর্যন্ত Loop ঘুরিয়ে traverse করা যায়। আমরা এই পোস্টের ক্ষেত্রে head node কে fixed রেখে কাজ করছি।

void print_list(){
    if(head==NULL)  return;

    node *current = head;
    do{
        printf("%d ", current->number);
        current = current->next;
    }   while(current != head);
    puts("\n");
}

উপরের কোডে দেখা যাচ্ছে head থেকে প্রিন্ট শুরু করা হয়েছে। Loop breaking condition এ দেয়া হয়েছে যে, যতক্ষণ পর্যন্ত current node এর মান head না হয় ততক্ষণ লুপ ঘুরে ঘুরে নোডের ডেটা প্রিন্ট করবে। যখন current == head হয়ে যাবে তখন বুঝা যাবে যে লিস্টের সবগুলো নোড একবার করে ভিজিট করে আবার head নোডে ভিজিট করা হয়েছে। তখন লুপ ব্রেক করবে।

উপরের সবগুলো অপারেশনের সোর্সকোড একত্রে পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে

আশা করি পুরো ব্যাপারটা বুঝতে পেরেছ। কোথাও যদি বুঝতে অসুবিধা হয় ধরে নিব আমার বর্ণনার সাবলীলতার দুর্বলতার জন্যেই এমনটা হয়েছে। টু দি পয়েন্টে কমেন্ট করে জানাও। আমি চেষ্টা করব লেখাটা আপডেট করার। ধন্যবাদ।

2 thoughts on “লিংকড লিস্ট – ৫ [Circular Singly Linked List: Insert, Delete and Print]

Leave a Reply

Your email address will not be published. Required fields are marked *