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

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

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

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

শুরু
  createnode() ফাংশন লিস্টে নোড ইনসার্ট করতে:
    এটি চেক করে লিস্ট খালি কিনা।
    যদি লিস্ট খালি হয়, নোডটিকে প্রথম এলিমেন্ট হিসেবে রাখুন এবং হেড আপডেট করুন।
    নেক্সট পয়েন্টার NULL দিয়ে ইনিশিয়ালাইজ করুন।
    যদি লিস্ট খালি না হয়,
      একটি newnode তৈরি করুন এবং নম্বরটিকে newnode-এর ডেটা ফিল্ডে ইনসার্ট করুন।
      এখন newnode এমনভাবে ইনসার্ট হবে যাতে লিঙ্কড লিস্ট সোর্টেড থাকে।
      যদি এটি শেষে ইনসার্ট হয়, newnode NULL-কে পয়েন্ট করবে।
      যদি 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 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 singly link list
2 3 4 6 7 2