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.


Required knowledge

Basic C programming, 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 can be various ways to reverse a doubly linked list. Here I am using the simplest approach to reverse the 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.
Reversing of a doubly linked list step 1
Swap the previous and next pointer fields of current node.
Reversing of a doubly linked list step 2
Move the position of current pointer to its next node. In general, now current.prev holds the address of next node.
Reversing of a doubly linked list step 3
Repeat Step 2-3 until current pointer becomes NULL.
When, the current pointer becomes NULL then the list will look something like.
Reversing of a doubly linked list step 4
Finally, swap the head and last pointers and you are done.
Reversing of a doubly linked list step 5
Now, if you compare the above image to the below given image you will find both are similar linked list.
Reversing of a doubly 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");
} 

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 ;)
Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment