Reverse Doubly Linked List : Algorithm and Program

Reversing a Doubly Linked List means changing the direction of the pointers in list so that the first node becomes the last and the last node becomes the first. In a doubly linked list, each node has two pointers one pointing to the next node and the other pointing to the previous node. To reverse the list, we go through each node and simply swap these two pointers. After swapping all the nodes, we update the head pointer to point to the new first node, which was originally the last node. This process allows us to reverse the list efficiently without creating any new nodes or using extra memory.

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);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Reverse the Doubly linked list
void reverseDoublyLinkedList(Node** head) {
    Node *temp = NULL;
    Node *current = *head;

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

    if (temp != NULL) {
        *head = temp->prev;
    }
}

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

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    printf("Doubly Linked List Before Reverse: ");
    printDoublyLinkedList(head);
    
    reverseDoublyLinkedList(&head);
    printf("Doubly Linked List After Reverse: ");
    printDoublyLinkedList(head);

    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;

The above code defines the structure of a node in a doubly circular linked list. Each node contains three key parts: an int data field that stores the actual value of the node, a struct Node* next pointer that points to the next node in the list for forward traversal, and a struct Node* prev pointer that points to the previous node for backward traversal. These three components together allow the list to be doubly linked, so traversal is possible in both directions, and when used in a circular list, the first and last nodes are connected to form a continuous loop.

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;
}

The above code defines a function createNode that creates a new node for a doubly circular linked list. It first allocates memory for the new node using malloc and initializes the node’s data field with the given value. The next and prev pointers are set to NULL since the node is not yet connected to the list. Finally, the function returns a pointer to this newly created node, ready to be inserted into the list.

3. Inserting at the End of the List

void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

The above code defines a function insertAtEnd that inserts a new node at the end of a doubly linked list. It first creates a new node using createNode with the given data. If the list is empty, the new node becomes the head. Otherwise, it traverses the list from the head to find the last node and then links the new node after it. The next pointer of the last node is set to the new node, and the prev pointer of the new node points back to the last node, maintaining the doubly linked structure.

4. Reversing the Doubly Linked List

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

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

    if (temp != NULL) {
        *head = temp->prev;
    }
}

The above code defines a function reverseDoublyLinkedList that reverses a doubly linked list. It uses a pointer current to traverse the list and a temporary pointer temp to help swap the links. For each node, it swaps the next and prev pointers, effectively reversing the direction of the list. After processing all nodes, it updates the head to point to the new first node, ensuring that the reversed list starts correctly. This reverses the list in-place while maintaining the doubly linked structure.

5. Printing the Doubly Linked List

void printDoublyLinkedList(Node* head) {
    Node *temp = head; 
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

The above code defines a function printDoublyLinkedList that prints all the elements of a doubly linked list. It uses a temporary pointer temp to traverse the list starting from the head. For each node, it prints the value stored in the data field and moves to the next node using the next pointer. The traversal continues until temp becomes NULL, indicating the end of the list, after which it prints a newline to complete the output.

6. Main Function

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    printf("Doubly Linked List Before Reverse: ");
    printDoublyLinkedList(head);
    
    reverseDoublyLinkedList(&head);
    printf("Doubly Linked List After Reverse: ");
    printDoublyLinkedList(head);

    return 0;
}

The above main function demonstrates how to use a doubly linked list and reverse it. It starts by creating an empty list with head = NULL. Then, it inserts six nodes with values 10, 20, 30, 40, 50, and 60 at the end of the list using insertAtEnd. Next, it prints the original list using printDoublyLinkedList, showing the order of nodes before reversal. After that, it calls reverseDoublyLinkedList to reverse the list in-place and prints the reversed list again. This shows the elements in the opposite order, confirming that the reversal function works correctly.

Time & Space Complexity

Time Complexity

Space Complexity