Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में डबल लिंक्ड सर्कुलर सूचियाँ


सर्कुलर लिंक्ड सूची लिंक्ड सूची का एक रूपांतर है जिसमें पहला तत्व अंतिम तत्व की ओर इशारा करता है और अंतिम तत्व पहले तत्व की ओर इशारा करता है। सिंगली लिंक्ड सूची और डबल लिंक्ड सूची दोनों को सर्कुलर लिंक्ड सूची में बनाया जा सकता है।

डबल लिंक्ड सूची में, अंतिम नोड का अगला पॉइंटर पहले नोड की ओर इशारा करता है और पहले नोड का पिछला पॉइंटर अंतिम नोड की ओर इशारा करता है जिससे दोनों दिशाओं में सर्कुलर बनता है।

C++ में डबल लिंक्ड सर्कुलर सूचियाँ

उपरोक्त चित्रण के अनुसार, निम्नलिखित महत्वपूर्ण बिंदुओं पर विचार किया जाना चाहिए।

  • डबल लिंक्ड सूची में अंतिम लिंक का अगला सूची के पहले लिंक की ओर इशारा करता है।
  • पहले लिंक का पिछला डबल लिंक्ड सूची के अंतिम की ओर इशारा करता है।

एल्गोरिदम

displayForward(): Begin
    ptr := head
    जबकि ptr := null, करें
        print ptr->key, ptr->data
        ptr := ptr->next
    किया
End

displayBackward(): Begin
    ptr := last
    जबकि ptr := null, करें
        print ptr->key, ptr->data
        ptr := ptr->prev
    किया
End

insertFirst(key, data): Begin
    कुंजी और डेटा के साथ नया नोड बनाएं
    यदि सूची खाली है, तो
        last := node
    अन्यथा
        head->prev := node
    अंत यदि
    node->next := head
    head := node
End

insertLast(key, data): Begin
    कुंजी और डेटा के साथ नया नोड बनाएं
    यदि सूची खाली है, तो
        last := node
    अन्यथा
        last->next := node
        node->prev := last
    अंत यदि
    last := node
End

insertAfter(key, newKey, data): Begin
    current := head
    यदि head null है, तो false लौटाएं
    जबकि current की कुंजी key नहीं है, करें
        यदि current->next null नहीं है, तो
            false लौटाएं
        अन्यथा
            current := current का next
        अंत यदि
    किया
    newKey और data के साथ नया नोड बनाएं
    यदि current = last, तो
        node का next := null
        last := node
    अन्यथा
        node का next := current का next
        current के next का prev := node
    अंत यदि
    node का prev := current
    current का next := node
    true लौटाएं
End

deleteFirst(): Begin
    tempNode := head
    यदि head का next null है, तो
        last := null
    अन्यथा
        head के next का prev := null
    अंत यदि
    head := head का next
    tempNode लौटाएं
End

deleteLast(): Begin
    tempNode := last
    यदि head का next null है, तो
        head := null
    अन्यथा
        last के prev का next := null
    अंत यदि
    last := last का prev
    tempNode लौटाएं
End

deleteNode(key): Begin
    curr := head और prev := null
    यदि head null है, तो
        null लौटाएं
    अंत यदि
    जबकि curr की कुंजी key के समान नहीं है, करें
        यदि curr का next null है, तो
            null लौटाएं
        अन्यथा
            prev := curr
            curr := curr का next
        अंत यदि
    किया
    यदि curr head है, तो head := head का next, अन्यथा prev के curr का next = curr का next
    यदि curr last है, तो last := curr का prev, अन्यथा curr के next का prev = curr का prev
    curr लौटाएं
End

उदाहरण

#include <iostream>
using namespace std;

class node {
public:
    int data;
    int key;
    node *next;
    node *prev;
};

// यह लिंक हमेशा पहले लिंक की ओर इशारा करता है
node *head = NULL;
// यह लिंक हमेशा अंतिम लिंक की ओर इशारा करता है
node *last = NULL;
node *current = NULL;

// सूची खाली है या नहीं
bool isEmpty() {
    return head == NULL;
}

int length() {
    int length = 0;
    node *current;
    for (current = head; current != NULL; current = current->next) {
        length++;
    }
    return length;
}

// सूची को पहले से अंत तक प्रदर्शित करें
void displayForward() {
    // शुरुआत से शुरू करें
    node *ptr = head;
    // सूची के अंत तक नेविगेट करें
    printf("\n[ ");
    while (ptr != NULL) {
        printf("(%d,%d) ", ptr->key, ptr->data);
        ptr = ptr->next;
    }
    printf(" ]");
}

// सूची को अंत से पहले तक प्रदर्शित करें
void displayBackward() {
    // अंत से शुरू करें
    node *ptr = last;
    // सूची की शुरुआत तक नेविगेट करें
    printf("\n[ ");
    while (ptr != NULL) {
        // डेटा प्रिंट करें
        printf("(%d,%d) ", ptr->key, ptr->data);
        // अगले आइटम पर जाएं
        ptr = ptr->prev;
    }
}

// लिंक को पहले स्थान पर डालें
void insertFirst(int key, int data) {
    // एक लिंक बनाएं
    node *link = new node();
    link->key = key;
    link->data = data;
    if (isEmpty()) {
        // इसे अंतिम लिंक बनाएं
        last = link;
    } else {
        // पहले prev लिंक को अपडेट करें
        head->prev = link;
    }
    // इसे पुराने पहले लिंक की ओर इंगित करें
    link->next = head;
    // पहले को नए पहले लिंक की ओर इंगित करें
    head = link;
}

// लिंक को अंतिम स्थान पर डालें
void insertLast(int key, int data) {
    // एक लिंक बनाएं
    node *link = new node();
    link->key = key;
    link->data = data;
    if (isEmpty()) {
        // इसे अंतिम लिंक बनाएं
        last = link;
    } else {
        // लिंक को नया अंतिम लिंक बनाएं
        last->next = link;
        // पुराने अंतिम नोड को नए लिंक के prev के रूप में चिह्नित करें
        link->prev = last;
    }
    // अंतिम को नए अंतिम नोड की ओर इंगित करें
    last = link;
}

// पहला आइटम हटाएं
node* deleteFirst() {
    // पहले लिंक का संदर्भ सहेजें
    node *tempLink = head;
    // यदि केवल एक लिंक है
    if (head->next == NULL) {
        last = NULL;
    } else {
        head->next->prev = NULL;
    }
    head = head->next;
    // हटाए गए लिंक को लौटाएं
    return tempLink;
}

// अंतिम स्थान पर लिंक हटाएं
node* deleteLast() {
    // अंतिम लिंक का संदर्भ सहेजें
    node *tempLink = last;
    // यदि केवल एक लिंक है
    if (head->next == NULL) {
        head = NULL;
    } else {
        last->prev->next = NULL;
    }
    last = last->prev;
    // हटाए गए लिंक को लौटाएं
    return tempLink;
}

// दी गई कुंजी के साथ लिंक हटाएं
node* del(int key) {
    // पहले लिंक से शुरू करें
    node* current = head;
    node* previous = NULL;
    // यदि सूची खाली है
    if (head == NULL) {
        return NULL;
    }
    // सूची के माध्यम से नेविगेट करें
    while (current->key != key) {
        // यदि यह अंतिम नोड है
        if (current->next == NULL) {
            return NULL;
        } else {
            // वर्तमान लिंक का संदर्भ संग्रहीत करें
            previous = current;
            // अगले लिंक पर जाएं
            current = current->next;
        }
    }
    // एक मिलान मिला, लिंक अपडेट करें
    if (current == head) {
        // पहले को अगले लिंक की ओर इंगित करने के लिए बदलें
        head = head->next;
    } else {
        // वर्तमान लिंक को बायपास करें
        current->prev->next = current->next;
    }
    if (current == last) {
        // अंतिम को पिछले लिंक की ओर इंगित करने के लिए बदलें
        last = current->prev;
    } else {
        current->next->prev = current->prev;
    }
    return current;
}

bool insertAfter(int key, int newKey, int data) {
    // पहले लिंक से शुरू करें
    node *current = head;
    // यदि सूची खाली है
    if (head == NULL) {
        return false;
    }
    // सूची के माध्यम से नेविगेट करें
    while (current->key != key) {
        // यदि यह अंतिम नोड है
        if (current->next == NULL) {
            return false;
        } else {
            // अगले लिंक पर जाएं
            current = current->next;
        }
    }
    // एक लिंक बनाएं
    node *newLink = new node();
    newLink->key = newKey;
    newLink->data = data;
    if (current == last) {
        newLink->next = NULL;
        last = newLink;
    } else {
        newLink->next = current->next;
        current->next->prev = newLink;
    }
    newLink->prev = current;
    current->next = newLink;
    return true;
}

int main() {
    insertFirst(1, 10);
    insertFirst(2, 20);
    insertFirst(3, 30);
    insertFirst(4, 1);
    insertFirst(5, 40);
    insertFirst(6, 56);
    printf("\nसूची (पहले से अंत): ");
    displayForward();
    printf("\n");
    printf("\nसूची (अंत से पहले): ");
    displayBackward();
    printf("\nसूची, पहला रिकॉर्ड हटाने के बाद: ");
    deleteFirst();
    displayForward();
    printf("\nसूची, अंतिम रिकॉर्ड हटाने के बाद: ");
    deleteLast();
    displayForward();
    printf("\nसूची, कुंजी(4) के बाद सम्मिलित करें: ");
    insertAfter(4, 7, 13);
    displayForward();
    printf("\nसूची, कुंजी(4) हटाने के बाद: ");
    del(4);
    displayForward();
}

आउटपुट

सूची (पहले से अंत): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
सूची (अंत से पहले): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
सूची, पहला रिकॉर्ड हटाने के बाद: [ (5,40) (4,1) (3,30) (2,20) (1,10) ]
सूची, अंतिम रिकॉर्ड हटाने के बाद: [ (5,40) (4,1) (3,30) (2,20) ]
सूची, कुंजी(4) के बाद सम्मिलित करें: [ (5,40) (4,1) (7,13) (3,30) (2,20) ]
सूची, कुंजी(4) हटाने के बाद: [ (5,40) (7,13) (3,30) (2,20) ]

  1. C++ में मल्टीलेवल लिंक्ड सूची को समतल करना C++ में मल्टीलेवल लिंक्ड सूची को समतल करना

    इस समस्या में, हमें एक मल्टीलेवल लिंक्ड सूची दी गई है। हमारा कार्य मल्टीलेवल लिंक्ड सूची को समतल करने के लिए एक प्रोग्राम बनाना है। समतल करने का ऑपरेशन इस तरह से किया जाता है कि पहले स्तर के नोड्स पहले लिंक्ड सूची में आएंगे और फिर दूसरे स्तर के नोड्स आएंगे। मल्टीलेवल लिंक्ड सूची एक बहुआयामी डेटा संर

  1. C++ में दो लिंक्ड लिस्ट का इंटरसेक्शन C++ में दो लिंक्ड लिस्ट का इंटरसेक्शन

    लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है। मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है।

  1. C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें

    हमें नोड्स के साथ एक सर्कुलर लिंक्ड लिस्ट दी गई है और कार्य सर्कुलर लिंक्ड लिस्ट में मौजूद नोड्स की संख्या की गणना करना है। सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट का एक प्रकार है जिसमें पहला तत्व अंतिम तत्व की ओर इंगित करता है और अंतिम तत्व पहले तत्व की ओर इंगित करता है। सिंगली लिंक्ड लिस्ट और डबली लिं