Question

/*

print_reverse function that prints the nodes in reverse order

if the list is empty print nothing

*/

include <bits/stdc++.h>

using namespace std;

class Node{

    public:

    int data;

    Node *next;

    Node *prev;

    Node(int d, Node *p=NULL, Node *n=NULL){

        data = d;

        prev = p;

        next = n;

    }

};

class DLL{

    public:

    Node *head;

    DLL(){head=NULL;}

    void push(int d){

        Node *pNode = new Node(d,NULL,head);

        if (head != NULL)

            head->prev = pNode;

        head = pNode;

    }

    void print_forward(){

        Node *pCurr = head;

        while (pCurr != NULL){

            cout << pCurr->data << endl;

            pCurr = pCurr->next;            

        }

    }

    void print_reverse(){

        // YOUR CODE HERE

    }

};

void main_body() {

    DLL myList;

    myList.push(2);

    myList.push(1);

    myList.push(5);

    myList.push(6);

    myList.print_reverse();

}

int main()

{

    main_body();

    return 0;

}

Answer 1

The function print_reverse() can be defined as follows:

• Create a node tail and assign head to it.
• Now using a while loop, traverse to the end of the list and find the tail of the list.
• Now using another while, traverse the list in backwards from the tail using the previous pointer until the next of tail is null.
• In the end, print the final node.

The C++ program with the function definition of function print_reverse() is as follows:

#include <bits/stdc++.h>
using namespace std;

//definition of class Node
class Node{

    public:

    int data;

    Node *next;

    Node *prev;

    Node(int d, Node *p=NULL, Node *n=NULL){

        data = d;

        prev = p;

        next = n;

    }

};

//definition of class linked list
class DLL{

    public:

    Node *head;

    DLL(){head=NULL;}

    void push(int d){

        Node *pNode = new Node(d,NULL,head);

        if (head != NULL)

            head->prev = pNode;

        head = pNode;

    }

    void print_forward(){

        Node *pCurr = head;

        while (pCurr != NULL){

            cout << pCurr->data << endl;

            pCurr = pCurr->next;            

        }

    }

    //function print_reverse()
    //this function will reverse the list in reverse
    //using the previous pointer traverse the list from tail
    void print_reverse()
    {
    Node* tail = head;   //initialize tail to head
    
    while (tail->next != NULL)    //find the tail
    { 
        tail = tail->next; 
    } 
  
    // Traversing linked list from tail to head (in reverse)
    while (tail != head) 
    { 
        cout << tail->data << " ";  //print the data
        tail = tail->prev;          //go backwards using previous pointer
    } 
    cout << tail->data << endl;     //in the end print the last

    }

};

void main_body() {

    DLL myList;

    myList.push(2);

    myList.push(1);

    myList.push(5);

    myList.push(6);
    
    myList.print_reverse();

}

int main()

{

    main_body();

    return 0;

}

The sample run: