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.
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:
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;
EndSteps 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.
- 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 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");
}============================================ 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