Algorithm Doubly Linked List Linked List

Reverse a Doubly Linked List

Reverse a Doubly Linked List - Doubly Linked List - A simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers.

Write a C function to reverse a given Doubly Linked List

Doubly Linked List:

Doubly Linked List (DLL) is a list of elements and it varies from Linked List. It allows navigation, either forward or backward when compared to Single Linked List. It has two pointers: previous pointer and next pointer. Every element points to next of the list and previous element in list.

Terms used in doubly linked list:

  • Link
  • Next
  • Prev
  • Linked list

See below diagrams for example.

     (a) Original Doubly Linked List  

Reverse a Doubly Linked List

(b) Reversed Doubly Linked List  

Reverse a Doubly Linked List

Here is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.

C programming:

/* Program to reverse a doubly linked list */
#include <stdio.h>
#include <stdlib.h>
 
/* a node of the doubly linked list */
struct node
{
  int data;
  struct node *next;
  struct node *prev;    
};
 
/* Function to reverse a Doubly Linked List */
void reverse(struct node **head_ref)
{
     struct node *temp = NULL;  
     struct node *current = *head_ref;
      
     /* swap next and prev for all nodes of 
       doubly linked list */
     while (current !=  NULL)
     {
       temp = current->prev;
       current->prev = current->next;
       current->next = temp;              
       current = current->prev;
     }      
      
     /* Before changing head, check for the cases like empty 
        list and list with only one node */
     if(temp != NULL )
        *head_ref = temp->prev;
}     
 
 
 
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
  
    /* put in the data  */
    new_node->data  = new_data;
     
    /* since we are adding at the begining, 
      prev is always NULL */
    new_node->prev = NULL;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);    
 
    /* change prev of head node to new node */
    if((*head_ref) !=  NULL)
      (*head_ref)->prev = new_node ;    
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
 
/* Function to print nodes in a given doubly linked list 
   This function is same as printList() of singly linked lsit */
void printList(struct node *node)
{
  while(node!=NULL)
  {
   printf("%d ", node->data);
   node = node->next;
  }
} 
 
/* Drier program to test above functions*/
int main()
{
  /* Start with the empty list */
  struct node* head = NULL;
  
  /* Let us create a sorted linked list to test the functions
   Created linked list will be 10->8->4->2 */
  push(&head, 2);
  push(&head, 4);
  push(&head, 8);
  push(&head, 10);
  
  printf("\n Original Linked list ");
  printList(head);
  
  /* Reverse doubly linked list */
  reverse(&head);
  
  printf("\n Reversed Linked list ");
  printList(head);           
  
  getchar();
}

Output:

Original Linked list 10 8 4 2 
Reversed Linked list 2 4 8 10

Time Complexity: O(n)

See also  C Programming-Smallest power of 2 greater than or equal to n

We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if size of data item(s) is more.

 

About the author

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment