Reverse Doubly Linked List : Algorithm and Program

by

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

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);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    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;
    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;
    }
}
  • 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) {
    Node *temp = 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() {
    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 main function initially creates an empty doubly linked list.
  • Nodes with values from 10 to 60 are added to the end of the list.
  • The list is printed using printList(head), showing the order of elements before reversal.
  • The list is then reversed using reverseDoublyLinkedList(&head).
  • Finally, the reversed list is printed, showing the new order of elements.

In this article we learnt the creation, manipulation, and reversal of a doubly linked list in a clear and structured manner.