C++ প্রোগ্রাম: সোর্টেড সার্কুলারলি সিঙ্গলি লিঙ্কড লিস্ট বাস্তবায়ন

ডেটা স্ট্রাকচারে, লিঙ্কড লিস্ট হল ডেটা এলিমেন্টের একটি লিনিয়ার সংগ্রহ। একটি লিস্টের প্রতিটি এলিমেন্ট বা নোড দুটি আইটেম নিয়ে গঠিত - ডেটা এবং পরবর্তী নোডের একটি রেফারেন্স। শেষ নোডের রেফারেন্স null থাকে। একটি লিঙ্কড লিস্টের এন্ট্রি পয়েন্টকে লিস্টের হেড বলা হয়।

একটি সিঙ্গলি লিঙ্কড লিস্টে, প্রতিটি নোড লিস্টের কন্টেন্ট এবং পরবর্তী নোডের একটি পয়েন্টার বা রেফারেন্স স্টোর করে। সিঙ্গলি লিঙ্কড লিস্টে পূর্বের নোডের কোনো পয়েন্টার বা রেফারেন্স থাকে না।

যেহেতু এটি একটি সোর্টেড সিঙ্গলি লিঙ্কড লিস্ট, তাই লিঙ্কড লিস্টের ডেটা আইটেমগুলো সবসময় সোর্টেড থাকবে।

নিচে সোর্টেড সার্কুলারলি সিঙ্গলি লিঙ্কড লিস্ট বাস্তবায়নের একটি C++ প্রোগ্রাম দেওয়া হলো।

শুরু
  createnode() ফাংশন লিস্টে নোড ইনসার্ট করতে:
    এটি চেক করে লিস্ট খালি কিনা। যদি খালি হয়, নোডটিকে প্রথম এলিমেন্ট হিসেবে রাখুন এবং হেড আপডেট করুন।
    যদি লিস্ট খালি না হয়,
      এটি একটি newnode তৈরি করে এবং newnode-এর ডেটা ফিল্ডে নম্বর ইনসার্ট করে।
      এখন newnode এমনভাবে ইনসার্ট হবে যাতে লিঙ্কড লিস্ট সোর্টেড থাকে।
      যদি এটি শেষে ইনসার্ট হয়, newnode হেডকে পয়েন্ট করবে।
      যদি newnode প্রথমে ইনসার্ট হয়, লিঙ্কড লিস্ট সেখান থেকে শুরু হবে।
শেষ

শুরু
  display() ফাংশন n সংখ্যক নোডের লিস্ট কন্টেন্ট প্রিন্ট করতে:
    c = 0 ইনিশিয়ালাইজ করুন।
    পয়েন্টার ভেরিয়েবলকে স্টার্ট অ্যাড্রেস দিয়ে ইনিশিয়ালাইজ করুন।
    যতক্ষণ (c <= n)
      নোড ইনফো প্রিন্ট করুন
      পয়েন্টার ভেরিয়েবল আপডেট করুন
      c বাড়ান।
শেষ

#include 
using namespace std;

struct nod {
    int d;
    nod *n;
} *p = NULL, *head = NULL, *q = NULL, *np = NULL;

int c = 0;

void createnode(int n) {
    np = new nod; np->d = n; np->n = NULL;
    if (c == 0) {
        head = np; p = head; p->n = head; c++;
    } else if (c == 1) {
        p = head; q = p;
        if (np->d < p->d) { np->n = p; head = np; p->n = np; }
        else if (np->d > p->d) { p->n = np; np->n = head; }
        c++;
    } else {
        p = head; q = p;
        if (np->d < p->d) {
            np->n = p; head = np;
            do { p = p->n; } while (p->n != q);
            p->n = head;
        } else if (np->d > p->d) {
            while (p->n != head && q->d < np->d) {
                q = p; p = p->n;
                if (p->n == head) { p->n = np; np->n = head; }
                else if (np->d < p->d) { q->n = np; np->n = p; break; }
            }
        }
    }
}

void display(int i) {
    nod *t = head; int c = 0;
    while (c <= i) { cout << t->d << "\t"; t = t->n; c++; }
}

int main() {
    int i = 0, n, a;
    cout << "enter the no of nodes\n"; cin >> n;
    while (i < n) {
        cout << "\nenter value of node\n"; cin >> a;
        createnode(a); i++;
    }
    cout << "sorted circularly singly link list" << endl; display(n);
}

enter the no of nodes 5
enter value of node 6
enter value of node 4
enter value of node 7
enter value of node 3
enter value of node 2
sorted circularly singly link list
2 3 4 6 7 2