# Reverse Doubly Linked List : Algorithm and Program

In this tutorial we will learn how to perform reverse on doubly linked list.

## Algorithm for Reversing a Doubly Linked List

1. Initialize Pointers:
• Start with two pointers: `current` pointing to the `head` of the list, and `temp`, initially set to `NULL`. `current` will be used to traverse the list, and `temp` will be used for swapping pointers.
2. Traverse the List:
• Loop through the list using the `current` pointer. This iteration continues until `current` becomes `NULL`, indicating the end of the list has been reached.
3. Swap Next and Prev Pointers:
• Within each iteration of the loop, perform the following steps on the `current` node:
• Set `temp` to the `prev` pointer of `current`. This temporarily stores the previous node.
• Swap the pointers: Set the `prev` pointer of `current` to its `next` pointer.
• Then, set the `next` pointer of `current` to `temp` (which was the original `prev` pointer).
• This swapping reverses the direction of the links for the current node.
4. Move to the Next Node:
• After swapping the pointers of the current node, move to the next node in the list (which, after swapping, is the previous node). This is done by setting `current` to `current->prev`.
5. Update the Head of the List:
• After the loop completes (when `current` is `NULL`), check if `temp` is not `NULL`. If it’s not, it means the list was not empty, and `temp` is now pointing to the new last node of the list.
• Set the `head` of the list to `temp->prev`. Since the list is reversed, `temp->prev` is actually the new first node of the list.
6. Completion:
• The list is now completely reversed, with the head pointing to what was originally the last node of the list.

## Program to Reverse Doubly Linked List

``````#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node Node;

// Create a new node
Node *createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Insert at the end of Doubly linked list
void insertAtEnd(Node** head, int data) {
Node *newNode = createNode(data);
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}

// Reverse the Doubly linked list
Node *temp = NULL;

while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

if (temp != NULL) {
}
}

// Print the Doubly linked list
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

int main() {
printf("Doubly Linked List Before Reverse: ");

printf("Doubly Linked List After Reverse: ");

return 0;
}
``````

Output

``````Doubly Linked List Before Reverse: 10 20 30 40 50 60
Doubly Linked List After Reverse: 60 50 40 30 20 10 ``````

### Step-by-Step Explanation of the Program

#### 1. Defining the Node Structure

``````struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node Node;``````

This part of the code defines the structure of a doubly linked list node, which contains:

• `int data`: The data stored in the node.
• `struct Node* next`: A pointer to the next node in the list.
• `struct Node* prev`: A pointer to the previous node in the list.

#### 2. Creating a New Node

``````Node *createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}``````
• This function creates a new node with the given data.
• It allocates memory for the node and initializes the `data`, `next`, and `prev` fields.
• The `next` and `prev` pointers are set to `NULL`, indicating that the node is not linked to any other nodes yet.

#### 3. Inserting at the End of the List

``````void insertAtEnd(Node** head, int data) {
Node *newNode = createNode(data);
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
``````
• This function adds a new node to the end of the doubly linked list.
• If the list is empty (`head` is `NULL`), the new node becomes the first (head) node.
• Otherwise, it finds the last node and links the new node after it.

#### 4. Reversing the Doubly Linked List

``````void reverseDoublyLinkedList(Node** head) {
Node *temp = NULL;

while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

if (temp != NULL) {
}
}``````
• This function reverses the doubly linked list.
• It iterates through the list, swapping the `next` and `prev` pointers of each node.
• After the loop, it updates the `head` to point to the new first node (previously the last node).

#### 5. Printing the Doubly Linked List

``````void printDoublyLinkedList(Node* head) {
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}``````
• This function prints the elements of the doubly linked list from the head to the end.
• It traverses the list and prints the data of each node.

#### 6. Main Function

``````int main() {
printf("Doubly Linked List Before Reverse: ");

• The `main` function initially creates an empty doubly linked list.
• The list is printed using `printList(head)`, showing the order of elements before reversal.
• The list is then reversed using `reverseDoublyLinkedList(&head)`.