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

C++ का उपयोग करके डबल लिंक्ड लिस्ट को रिवर्स करें


इस लेख में हमारे पास एक डबल लिंक्ड लिस्ट है, और हम C++ में डबल लिंक्ड लिस्ट को रिवर्स करने के विभिन्न दृष्टिकोणों की व्याख्या करेंगे। उदाहरण के लिए −

Input : {1, 2, 3, 4} Output : {4, 3, 2, 1}

आम तौर पर एक दृष्टिकोण दिमाग में आता है, लेकिन हम दो दृष्टिकोणों का उपयोग करेंगे − सामान्य और अपरंपरागत दृष्टिकोण।

सामान्य दृष्टिकोण

इस दृष्टिकोण में, हम लिस्ट के माध्यम से जाएंगे, और जैसे-जैसे हम इसके माध्यम से जाते हैं, हम इसे रिवर्स करते हैं।

उदाहरण

#include <bits/stdc++.h> using namespace std; class Node {    public:    int data;    Node *next;    Node *prev; }; void reverse(Node **head_ref) {    auto temp = (*head_ref) -> next;    (*head_ref) -> next = (*head_ref) -> prev;    (*head_ref) -> prev = temp;    if(temp != NULL) {       (*head_ref) = (*head_ref) -> prev;       reverse(head_ref);    }    else       return; } void push(Node** head_ref, int new_data) {    Node* new_node = new Node();    new_node->data = new_data;    new_node->prev = NULL;    new_node->next = (*head_ref);    if((*head_ref) != NULL)       (*head_ref) -> prev = new_node ;    (*head_ref) = new_node; } int main() {    Node* head = NULL;    push(&head, 6);    push(&head, 4);    push(&head, 8);    push(&head, 9);    auto node = head;    cout << "Before\n" ;    while(node != NULL) {       cout << node->data << " ";       node = node->next;    }    cout << "\n";    reverse(&head);    node = head;    cout << "After\n";    while(node != NULL) {       cout << node->data << " ";    node = node->next;    }    return 0; }

आउटपुट

Before 9 8 4 6 After 6 4 8 9

यह दृष्टिकोण O(N) समय जटिलता लेता है जो बहुत अच्छा है क्योंकि यह जटिलता उच्च प्रतिबंधों में प्रदर्शन कर सकती है।

अपरंपरागत दृष्टिकोण

जैसा कि नाम से पता चलता है, यह एक बहुत ही सामान्य दृष्टिकोण नहीं है जो उपयोगकर्ता के दिमाग में आता है, लेकिन हम इस दृष्टिकोण का भी पता लगाएंगे। इस दृष्टिकोण में, हम एक स्टैक बनाएंगे और उसमें डेटा डालते रहेंगे, और पॉप करते समय, हम इसके मानों को बदलने जा रहे हैं।

उदाहरण

#include <bits/stdc++.h> using namespace std; class Node {    public:    int data;    Node *next;    Node *prev; }; void push(Node** head_ref, int new_data) {    Node* new_node = new Node();    new_node->data = new_data;    new_node->prev = NULL;    new_node->next = (*head_ref);    if((*head_ref) != NULL)       (*head_ref) -> prev = new_node ;    (*head_ref) = new_node; } int main() {    Node* head = NULL;    push(&head, 6);    push(&head, 4);    push(&head, 8);    push(&head, 9);    auto node = head;    cout << "Before\n" ;    while(node != NULL) {       cout << node->data << " ";       node = node->next;    }    cout << "\n";    stack<Node*> s;    node = head;    while(node) {       head = node;       s.push(node);       node = node -> next;    }    while(!s.empty()) {       auto x = s.top();       auto temp = x -> prev;       x -> prev = x -> next;       x -> next = temp;       s.pop();    }    node = head;    cout << "After\n";    while(node != NULL) {       cout << node->data << " ";    node = node->next;    }    return 0; }

आउटपुट

Before 9 8 4 6 After 6 4 8 9

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में हम एक स्टैक का उपयोग कर रहे हैं जिसे हम लिस्ट के माध्यम से ट्रैवर्स करते समय भर रहे हैं और फिर हम स्टैक से आइटम पॉप कर रहे हैं और उनके मानों को इस तरह बदल रहे हैं कि लिस्ट रिवर्स हो जाए। इस प्रोग्राम की समय जटिलता O(N) है और यह उच्च प्रतिबंधों के लिए भी उपयुक्त है।

निष्कर्ष

इस लेख में हम स्टैक के साथ या बिना डबल लिंक्ड लिस्ट को रिवर्स करने की समस्या को हल करते हैं। O(N) समय जटिलता में जहां N हमारी लिस्ट का आकार है। हमने इस समस्या के लिए C++ प्रोग्राम और पूर्ण दृष्टिकोण (सामान्य और अपरंपरागत) सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगा होगा।


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

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

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

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

  1. C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार

    हमें डेटा और प्राथमिकता एक पूर्णांक मान के रूप में दी गई है और कार्य दिए गए प्राथमिकता के अनुसार डबल लिंक्ड लिस्ट बनाना और परिणाम प्रदर्शित करना है।कतार एक FIFO डेटा संरचना है जिसमें पहले डाला गया तत्व सबसे पहले हटाया जाता है। प्राथमिकता कतार एक प्रकार की कतार है जिसमें तत्वों को प्राथमिकता के आधार