﻿ C++ - Reverse doubly linked list

# 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> // Including input-output stream header file

using namespace std; // Using standard namespace

// A doubly linked list node
struct Node {
string data; // Data field to store string data
struct Node* next; // Pointer to the next node
struct Node* prev; // Pointer to the previous node
};

// Function to append data at the front of the doubly linked list
void append_data(Node** head, string new_data)
{
// Create a new node and allocate memory.
struct Node* newNode = new Node;

// Assign data to the 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 the new node
if ((*head) != NULL)
(*head)->prev = newNode;

// Head points to new node
(*head) = newNode;
}

// Function to reverse a doubly linked list
void reverse(Node** head)
{
struct Node* tmp = NULL; // Temporary node for swapping
struct Node* currNode = *head; // Current node to traverse the list

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 the swap
currNode = currNode->prev;
}
// If tmp is not NULL, then head needs to be updated
if (tmp != NULL)
*head = tmp->prev;
}

// Function to 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 << " "; // Displaying data in forward direction
last_node = head;
head = head->next;
}
cout << "\nTraversal in Reverse direction:\n";
while (last_node != NULL) {
cout << " " << last_node->data << " "; // Displaying data in reverse direction
last_node = last_node->prev;
}
}

// Main program
int main() {
/* Start with the empty list */
struct Node* head = NULL; // Initializing the head of the linked list as NULL
append_data(&head, "Red"); // Appending "Red" at the front of the list
append_data(&head, "Green"); // Appending "Green" at the front of the list
append_data(&head, "White"); // Appending "White" at the front of the list
append_data(&head, "Orange"); // Appending "Orange" at the front of the list
cout<<"Doubly linked list is as follows: ";
displayDlList(head); // Displaying the doubly linked list
reverse(&head); // Reversing the doubly linked list
cout<<"\n\nReverse Doubly linked list: ";
displayDlList(head); // Displaying the reversed doubly linked list
return 0; // Returning from the main function
}
``````

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:

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?

﻿

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/cpp-exercises/linked_list/cpp-linked-list-exercise-16.php