C program to reverse a doubly linked list

Write a C program to create a doubly linked list and reverse the linked list. How to reverse the doubly linked list in C programming. Algorithm to reverse a doubly linked list.

Doubly Linked List
Doubly Linked List
Doubly Linked List Reversed
Doubly Linked List Reversed

Required knowledge

Basic C programming, Functions, Dynamic memory allocation, Doubly linked list

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:
    currenthead;
    While (current != NULL) do
        tempcurrent.next;
        current.nextcurrent.prev;
        current.prevtemp;
        
        currenttemp;
    End while
    temphead;
    headlast;
    lasttemp;
End

Steps to reverse a doubly linked list

There are various methods to reverse a doubly linked list. Here I am using the simplest approach to reverse the list.

  1. 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.

    Reversing doubly linked list step 1

  2. Swap the previous and next pointer fields of current node.

    Reversing doubly linked list step 2

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

    Reversing doubly linked list step 3

  4. Repeat Step 2-3 until current pointer becomes NULL.
  5. When, the current pointer becomes NULL then the list will look something like.

    Reversing doubly linked list step 4

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

    Reversing doubly linked list step 5

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

    Doubly Linked List Reversed

Program to reverse a doubly linked list

/**
 * 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)
    {
        /*
         * Create and link 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;

        /*
         * Create and link 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; // Link new node with the previous node
            newNode->next = NULL;

            last->next = newNode; // Link previous node with the new node
            last = newNode; // Make new node as last/previous node
        }

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


/**
 * Display 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++;

            /* Move pointer to next node */
            temp = temp->next;
        }
    }
}


/**
 * Reverse 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");
}

Output

============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Reverse List
3. Display list
0. Exit
--------------------------------------------
Enter your choice : 1
Enter the total number of nodes in list: 4
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40

DOUBLY LINKED LIST CREATED SUCCESSFULLY





============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Reverse List
3. Display list
0. Exit
--------------------------------------------
Enter your choice : 3
DATA IN THE LIST:
DATA of 1 node = 10
DATA of 2 node = 20
DATA of 3 node = 30
DATA of 4 node = 40





============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Reverse List
3. Display list
0. Exit
--------------------------------------------
Enter your choice : 2
LIST REVERSED SUCCESSFULLY.





============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Reverse List
3. Display list
0. Exit
--------------------------------------------
Enter your choice : 3
DATA IN THE LIST:
DATA of 1 node = 40
DATA of 2 node = 30
DATA of 3 node = 20
DATA of 4 node = 10





============================================
DOUBLY LINKED LIST PROGRAM
============================================
1. Create List
2. Reverse List
3. Display list
0. Exit
--------------------------------------------
Enter your choice : 0

Happy coding 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Follow on: Facebook | Twitter | Google | or

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>