C program to reverse a doubly linked list

Required knowledge

Algorithm to reverse a doubly linked list

Algorithm to reverse a doubly linked list
%% Input : head {Pointer to first node of the list}
         last {Pointer to last node of the list}
Begin:
    current ← head;
    While (current != NULL) do
        temp ← current.next;
        current.next ← current.prev;
        current.prev ← temp;
        
        current ← temp;
    End while
    temp ← head;
    head ← last;
    last ← temp;
End

Steps to reverse a doubly linked list

To reverse the list we start with the first node. Say a pointer current keeps track of the current node. Now initially current points to head node.

Swap the previous and next pointer fields of current node.

Move the position of current pointer to its next node. In general, now current.prev holds the address of next node.

Repeat Step 2-3 until current pointer becomes NULL.

When, the current pointer becomes NULL then the list will look something like.

Finally, swap the head and last pointers and you are done.

Now, if you compare the above image to the below given image you will find both are similar linked list.

Program

/**
 * C program to reverse a Doubly linked list
 */

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


/*
 * Basic structure of Node
 */
struct node {
    int data;
    struct node * prev;
    struct node * next;
}*head, *last;



/*
 * Functions used in this program
 */
void createList(int n);
void displayList();
void reverseList();


int main()
{
    int n, data, choice=1;

    head = NULL;
    last = NULL;

    /*
     * Runs forever until user chooses 0
     */
    while(choice != 0)
    {
        printf("============================================\n");
        printf("DOUBLY LINKED LIST PROGRAM\n");
        printf("============================================\n");
        printf("1. Create List\n");
        printf("2. Reverse List\n");
        printf("3. Display list\n");
        printf("0. Exit\n");
        printf("--------------------------------------------\n");
        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch(choice)
        {
            case 1:
                printf("Enter the total number of nodes in list: ");
                scanf("%d", &n);
                createList(n);
                break;
            case 2:
                reverseList();
                break;
            case 3:
                displayList();
                break;
            case 0:
                break;
            default:
                printf("Error! Invalid choice. Please choose between 0-3");
        }

        printf("\n\n\n\n\n");
    }

    return 0;
}



/**
 * Creates a doubly linked list of n nodes.
 *
 * @n Number of nodes to be created
 */
void createList(int n)
{
    int i, data;
    struct node *newNode;

    if(n >= 1)
    {
        /*
         * Creates and links the head node
         */
        head = (struct node *)malloc(sizeof(struct node));

        printf("Enter data of 1 node: ");
        scanf("%d", &data);

        head->data = data;
        head->prev = NULL;
        head->next = NULL;

        last = head;

        /*
         * Creates and links rest of the n-1 nodes
         */
        for(i=2; i<=n; i++)
        {
            newNode = (struct node *)malloc(sizeof(struct node));

            printf("Enter data of %d node: ", i);
            scanf("%d", &data);

            newNode->data = data;
            newNode->prev = last; //Links new node with the previous node
            newNode->next = NULL;

            last->next = newNode; //Links previous node with the new node
            last = newNode; //Makes new node as last/previous node
        }

        printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");
    }
}



/**
 * Displays the content of the list from beginning to end
 */
void displayList()
{
    struct node * temp;
    int n = 1;

    if(head == NULL)
    {
        printf("List is empty.\n");
    }
    else
    {
        temp = head;
        printf("DATA IN THE LIST:\n");

        while(temp != NULL)
        {
            printf("DATA of %d node = %d\n", n, temp->data);

            n++;

            /* Moves the current pointer to next node */
            temp = temp->next;
        }
    }
}



/**
 * Reverses the order of the doubly linked list
 */
void reverseList()
{
    struct node *current, *temp;

    current = head;
    while(current != NULL)
    {
        /*
         * Swap the previous and next address fields of current node
         */
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;

        /* Move the current pointer to next node which is stored in temp */
        current = temp;
    }
    
    /* 
     * Swap the head and last pointers
     */
    temp = head;
    head = last;
    last = temp;

    printf("LIST REVERSED SUCCESSFULLY.\n");
}