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

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

একটি ডাবলি লিঙ্কড লিস্ট একটি সিকোয়েন্সিয়ালি লিঙ্কড রেকর্ডের সেট যা নোড বলা হয়। প্রতিটি নোডে তিনটি ফিল্ড থাকে: একটি ডেটা ফিল্ড এবং দুটি লিংক ফিল্ড; নোডের সিকোয়েন্সে পূর্বের এবং পরবর্তী নোডের রেফারেন্স।

সোর্টেড ডাবলি লিঙ্কড লিস্টের ক্ষেত্রে, সোর্টেড ডেটা ফিল্ডের মান অনুযায়ী লিঙ্কড লিস্ট সোর্টেড থাকে।

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

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

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

#include 
using namespace std;

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

int c = 0;

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

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

void display_tail(int i) {
    nod *t = tail; int m = 0;
    while (m <= i) { cout << t->d << "\t"; t = t->p; m++; }
    cout << endl;
}

int main() {
    int i = 0, n, a, ch;
    cout << "enter the no of nodes\n"; cin >> n;
    while (i < n) {
        cout << "\nenter value of node\n"; cin >> a;
        createnode(a); i++;
    }
    cout << "\nsorting Doubly Linked List head first\n"; display_head(n);
    cout << "\nsorting Doubly Linked List tail first\n"; display_tail(n);
}

enter the no of nodes 5
enter value of node 7
enter value of node 4
enter value of node 6
enter value of node 2
enter value of node 1
sorting Doubly Linked List head first
1 2 4 6 7 1
sorting Doubly Linked List tail first
7 6 4 2 1 7