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

গত পর্বের Circular Singly Linked List এর মতই এই পর্বের Circular Doubly Linked List. তুমি যদি লিংকড লিস্টের আগের পর্বগুলো বুঝে থাকো তাহলে এই পর্বটা বুঝতে খুব একটা কষ্ট হবে না। এই পর্বটি বুঝার জন্য তোমার singly linked list, doubly linked list ও circular singly linked list বুঝতে হবে। এই তিনটির সমন্বয়েই বলতে পারো এই ডেটা স্ট্রাকচারটি গঠিত। তাই ধরেই নিচ্ছি তুমি আগের টপিকগুলো আমার পূর্বের পোস্টগুলো থেকে বা অন্য কোনো রিসোর্স থেকে শিখে নিয়েছ। সে জন্য অনেক ব্যাখ্যাই খুব বেশি ডিটেইলসে দিব না।

Circular Doubly Linked List এমন একটা লিংকড লিস্ট যাতে দুটি বৈশিষ্ট্য আছে। প্রথমত এটা একটা circular (singly) linked list এবং দ্বিতীয়ত এটা একটা doubly linked list. এই circular আর doubly দুইটা লিস্টের বৈশিষ্ট্যকে এক সাথে করে বানানো হয়েছে circular doubly linked list.

Circular Linked List এর বৈশিষ্ট্য হচ্ছে এটা সার্কুলার। অর্থাৎ এর শেষ প্রান্ত বলে কিছু নাই। শেষ প্রান্তে গিয়ে পরের নোডে যেতে চাইলে সে তোমাকে head node এর কাছে পাঠিয়ে দিবে। তুমি চাইলে চড়কির মত এই লিস্টের মধ্যে ভনভন করে ঘুরতে পারো (multiplayer লুডু খেলার মত। চারজনই একের পর এক ছক্কা দিয়ে চালতে থাকে)। আর doubly linked list হচ্ছে এমন একটা লিস্ট যার একটা শুরু ও শেষ আছে (সার্কুলার নয়। শেষ নোডটি next pointer হিসাবে NULL-কে পয়েন্ট করে থাকে)। এর বিশেষ বৈশিষ্ট্য হচ্ছে এর head থেকে tail এর দিকে যেমন traverse করা যায়, একই ভাবে tail থেকে head এর দিকেও traverse করা যায়। অর্থাৎ ছোট বেলার ‘উভমুখী বিক্রিয়া’র মত একটা বিষয়।

Applications of Circular Doubly Linked List

• Repeated task নিয়ে কাজ করার ক্ষেত্রে যদি forward-backward দুই দিকেই traverse করার দরকার হয় একই সাথে যদি লিস্টটাকে সার্কুলারও করতে হয় সেক্ষেত্রে এই ডেটা স্ট্রাকচারটা দরকার হয়। যেমনঃ মিডিয়া প্লেয়ার অ্যাপ্লিকেশনে অডিও বা ভিডিওগুলো সামনে-পিছনে ইচ্ছা মত প্লে করা যায়। পুরো লিস্ট প্লে হলে আবার শুরু থেকে প্লে হয়। তার মানে আমরা যদি ডেস্কটপ, মোবাইল বা ওয়েবে যদি media player App বানাতে চাই তাহলে সেখানে circular doubly linked list ডেটা স্ট্রাকচার নিয়ে কাজ করতে হবে।
• অনলাইন শপিংয়ের ক্ষেত্রে shopping cart ম্যানেজ করার জন্য এই ডেটা স্ট্রাকচার ব্যবহৃত হয়।

Advantages of Circular Doubly Linked List

• লিস্টের যে কোনো নোডকে শুরুর নোড ধরে পুরো লিস্টে traverse করা যায়। শুধু খেয়াল রাখতে হবে যেই নোড থেকে শুরু করা হয়েছিল সেটায় দ্বিতীয় বার ভিজিট করলে যেন traverse operation terminated হয়।
• লিস্টের শুরু থেকে শেষের দিকে ও শেষ থেকে শুরুর দিকে traverse করা যায়।
• Constant time এ [ O(1) ] head থেকে tail এবং tail থেকে head এর মধ্যে সুইচ করা যায়।
• Advanced কিছু Data Structures এর মাধ্যমে implement করা যায়। যেমনঃ Fibonacci Heap.

Disadvantages of Circular Doubly Linked List

• প্রতিটা নোডের previous pointer স্টোর করার জন্য একটু বেশি খরচ হয়।
• বেশ কিছু পয়েন্টার হ্যান্ডেল করতে হয় যে কোনো অপারেশনেই। লিস্টে একটা নোড ঢুকলে বা ডিলেট হলে তার আগের ও পরের উভয় নোডের সাথেই পয়েন্টার কেন্দ্রীক কাজ করতে হয়। তাই খুব সাবধানতা অবলম্বন করতে হয়। নইলে লিস্টের ভিতরের জিনিসপত্রে ভজঘট লেগে যেতে পারে।

Operations of Circular Doubly 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 in Forward order (Print the full list)
4. Traverse the list in Backward/Reverse order (Print the full list)

Insert node at Circular Doubly Linked List

Insert node at head: নতুন একটা নোড লিস্টের front এ add করতে চাইলে নিচের কাজগুলো করতে হবেঃ

1. নতুন একটা নোড বানিয়ে (newNode) এর next ও previous pointer এ তার নিজের মেমরি অ্যাড্রেসই অ্যাসাইন করে দেয়া
2. newNode এর next pointer-টি পয়েন্ট করবে head-কে।
3. newNode এর previous pointer-টি পয়েন্ট করবে tail-কে।
4. head এর previous pointer এখন পর্যন্ত tail-কে পয়েন্ট করে আছে। কিন্তু head এর আগে এখন newNode বসেছে। তাই head এর previous pointer পয়েন্ট করবে newNode-কে।
5. tail এর next pointer এখন পর্যন্ত head কে পয়েন্ট করে আছে। কিন্তু নতুন head হতে যাচ্ছে newNode. তাই tail এর next pointer পয়েন্ট করবে newNode-কে
6. লিস্টের নতুন head এখন newNode. তাই head-কে আপডেট করতে হবে newNode দিয়ে।

void insert_at_head(int number){
    node *newNode = (node *) malloc(sizeof(node));

    newNode->number = number;
    newNode->next = newNode;
    newNode->previous = newNode;

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

Insert node at tail: নতুন একটা নোড লিস্টের end এ add করতে চাইলে নিচের কাজগুলো করতে হবেঃ

1. নতুন একটা নোড বানিয়ে (newNode) এর next ও previous pointer এ তার নিজের মেমরি অ্যাড্রেসই অ্যাসাইন করে দেয়া
2. এখন tail->next পয়েন্ট করে আছে head কে। যেহেতু tail এ নতুন একটা নোড newNode যোগ হবে তাই এটিই হবে নতুন tail. তাই বর্তমান tail এর next pointer পয়েন্ট করবে newNode কে।
3. newNode যেহেতু হতে যাচ্ছে নতুন tail, তাই এর next pointer পয়েন্ট করবে head কে।
4. newNode এর previous pointer পয়েন্ট করবে বর্তমান tail কে।
5. উপরের চারটি ধাপ অতিক্রম করলে newNode লিস্টের শেষে বসে যাবে। এখন এটা যেহেতু নতুন tail, তাই tail node কে আপডেট করে দিতে হবে newNode দিয়ে।
6. এখন পর্যন্ত head এর previous pointer পয়েন্ট করে আছে পুরাতন tail-কে। যেহেতু tail আপডেট হয়েছে সেহেতু head এর previous pointer-ও আপডেট করতে হবে updated tail দিয়ে। তুমি চাইলে head->previous = newNode; এভাবেও লিখতে পার।

void insert_at_tail(int number){
    node *newNode = (node *) malloc(sizeof(node));

    newNode->number = number;
    newNode->next = newNode;
    newNode->previous = newNode;

    if(head==NULL){
        head = newNode;
        tail = newNode;
    } else{
        tail->next = newNode;
        newNode->next = head;
        newNode->previous = tail;
        tail = newNode;
        head->previous = tail; //can also write `head->previous = newNode`
    }
}

Insert node at middle: নতুন একটা নোড লিস্টের মাঝের যে কোনো পজিশনে add করতে চাইলে নিচের কাজগুলো করতে হবেঃ

1. List এ নোডের order অনুযায়ী desired position এর নোড (current) ও তার আগের নোড (temp) বের করা। নতুন নোডটি (newNode) বসবে temp আর current এর মাঝে।
2. temp এর next pointer পয়েন্ট করবে newNode-কে।
3. newNode এর next pointer পয়েন্ট করবে current node-কে।
4. newNode এর previous pointer পয়েন্ট করবে temp node-কে।
5. current node এর previous pointer পয়েন্ট করবে newNode-কে।

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;
                newNode->previous = temp;
                current->previous = newNode;
            }
            return;
        }
    }

    printf("Position does not exist!\n");
}

Delete node from Circular Doubly Linked List

Delete head node: Circular doubly linked list এর head node-কে ডিলেট করার জন্য নিচের স্টেপগুলো ফলো করতে হবেঃ

1. head যেই নোডকে পয়েন্ট করে আছে temp-ও সেটিকে পয়েন্ট করে আছে।
2. যেহেতু head-কে ডিলেট করতে চাই, সুতরাং head->next যেই নোডকে পয়েন্ট করে আছে সেটিই হবে নতুন head।
3. নতুন যেই নোডটি head এ assign হল তার previous node কিন্তু পয়েন্ট করে আছে আগের head-কে। তাই নতুন head এর previous pointer কে আপডেট করতে হবে tail দিয়ে।
4. tail এর next pointer পয়েন্ট করে ছিল আগের head-কে। head যেহেতু আপডেট হয়েছে তাই tail এর next pointer-ও নতুন head দিয়ে আপডেট করতে হবে
5. temp আগের head-কে পয়েন্ট করে ছিল। এটাকে যেহেতু ডিলেট করছি তাই মেমরি থেকে এটাকে মুছে ফেলতে হবে [free(temp)].

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

    node *temp = head;

    head = head->next;
    head->previous = tail;
    tail->next = head;

    free(temp);
}

Delete tail node: Circular doubly linked list এর tail node-কে ডিলেট করার জন্য নিচের স্টেপগুলো ফলো করতে হবেঃ

1. temp পয়েন্ট করবে tail node-কে।
2. নতুন tail হবে tail->previous.
3. নতুন tail এর next pointer এখন পয়েন্ট করে আছে পুরাতন tail-কে। এটা আপডেট করতে হবে head দিয়ে।
4. head এর previous pointer পয়েন্ট করে আছে পুরাতন tail-কে। একে নতুন tail দিয়ে আপডেট করতে হবে।

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

    node *temp = tail;

    tail = tail->previous;
    tail->next = head;
    head->previous = tail;

    free(temp);
}

Delete any middle position node: Circular doubly linked list এর মাঝামাঝি যে কোনো পজিশনের node-কে ডিলেট করার জন্য নিচের স্টেপগুলো ফলো করতে হবেঃ

1. Desired position এর নোডটি খুঁজে বের করতে হবে (current node).
2. current নোডের আগের নোডটির next pointer পয়েন্ট করবে current এর next pointer-কে। ফলে current node কে কোনো নোডই এখন আর next pointer হিসাবে পয়েন্ট করছে না।
3. current এর পরের নোডটি কিন্তু এখনো previous pointer হিসাবে current-কে পয়েন্ট করে আছে। কিন্তু একে পয়েন্ট করে রাখা যাবে না। পয়েন্ট করতে হবে current এর আগের নোডকে।
4. এখন কোনো নোডই next বা previous পয়েন্টার হিসাবে current node-কে পয়েন্ট করছে না। তার মানে এটা লিস্ট থেকে ছিটকে পড়েছে। কিন্তু এখনো মেমরিতে স্পেস দখল করে আছে। তাই current node কে free করে দিতে হবে।

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

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

    node *current = head;
    int count = 0;

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

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

        current->previous->next = current->next;
        current->next->previous = current->previous;
        free(current);

        return;
    }

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

Print Circular Doubly Linked List in Forward order

head node থেকে প্রিন্ট করা শুরু করতে হবে। যতক্ষণ না আবার head node পাওয়া যায় ততক্ষণ প্রিন্টের কাজ চলতে থাকবে।

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

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

Print Circular Doubly Linked List in Reverse order

tail node থেকে প্রিন্ট করা শুরু করতে হবে। যতক্ষণ না আবার tail node পাওয়া যায় ততক্ষণ প্রিন্টের কাজ চলতে থাকবে।

void print_reverse_order(){
    if(head==NULL)  return; // also can check `tail==NULL`

    node *current = tail;
    do{
        printf("%d ", current->number);
        current = current->previous;
    }   while(current != tail);
}

সম্পূর্ণ সোর্সকোডটি পাওয়া যাবে আমার গিটহাব রিপোজিটরিতে।