w3resource

C++ Linked List Exercises: Reverse doubly linked list

C++ Linked List: Exercise-16 with Solution

Write a C++ program to create a doubly linked list of n nodes and display it in reverse order.

Test Data:
Doubly linked list is as follows:
Traversal in Forward direction:
Orange White Green Red
Traversal in Reverse direction:
Red Green White Orange
Reverse Doubly linked list:
Traversal in Forward direction:
Red Green White Orange
Traversal in Reverse direction:
Orange White Green Red

Sample Solution:

C++ Code:

#include <iostream>

using namespace std;
  
// A doubly linked list node
struct Node {
   string data;
   struct Node* next;
   struct Node* prev;
};

  
//Append node at the front of the list
void append_data(Node** head, string new_data)
{
   //Create a new node and allocate memory.
   struct Node* newNode = new Node;
  
   //assign data to new node
   newNode->data = new_data;
  
   // A new node has been added with the name head and the previous node 
   // set to null, since it is being added at the front.
   newNode->next = (*head);
   newNode->prev = NULL;
  
   //previous head is new node
   if ((*head) != NULL)
   (*head)->prev = newNode;
  
   //head points to new node
   (*head) = newNode;
}

void reverse(Node** head)
{
    struct Node* tmp = NULL;
    struct Node* currNode = *head;
 
    while (currNode != NULL) {
    	//Swap this node’s next and prev references
        tmp = currNode->prev;
        currNode->prev = currNode->next;
        currNode->next = tmp;
        //The next node is now the prev node because of swap
        currNode = currNode->prev;
    }
     if (tmp != NULL)
        *head = tmp->prev;
}


// Following function display contents of the doubly linked list
void displayDlList(Node* head)
{
    Node* last_node;
    cout << "\n\nTraversal in Forward direction:\n";
    while (head != NULL) {
        cout << " " << head->data << " ";
        last_node = head;
        head = head->next;
    }
    cout << "\nTraversal in Reverse direction:\n";
    while (last_node != NULL) {
        cout << " " << last_node->data << " ";
        last_node = last_node->prev;
    }
}
  
//main program
int main() {
   /* Start with the empty list */
   struct Node* head = NULL;
   append_data(&head, "Red");
   append_data(&head, "Green");
   append_data(&head, "White");
   append_data(&head, "Orange");
   cout<<"Doubly linked list is as follows: ";  
   displayDlList(head);
   reverse(&head);
   cout<<"\n\nReverse Doubly linked list: ";
   displayDlList(head);
   return 0;
}

Sample Output:

Doubly linked list is as follows:

Traversal in Forward direction:
 Orange  White  Green  Red
Traversal in Reverse direction:
 Red  Green  White  Orange

Reverse Doubly linked list:

Traversal in Forward direction:
 Red  Green  White  Orange
Traversal in Reverse direction:
 Orange  White  Green  Red

Flowchart:

Flowchart: Reverse doubly linked list.
Flowchart: Reverse doubly linked list.

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Create and display a doubly linked list.
Next C++ Exercise: Count number of nodes in a doubly linked list.

What is the difficulty level of this exercise?



Share this Tutorial / Exercise on : Facebook and Twitter

C++ Programming: Tips of the Day

How to replace all occurrences of a character in string?

std::string doesn't contain such function but you could use stand-alone replace function from algorithm header.

#include <algorithm>
#include <string>

void some_func() {
  std::string s = "example string";
  std::replace( s.begin(), s.end(), 'x', 'y'); // replace all 'x' to 'y'
}

Ref: https://bit.ly/3niU71x