Skip to main content

Reverse a doubly linked list

A doubly linked list has two pointers in each node. Pointer to previous node and pointer to next node.

We have seen that reversing a singly linked list is not so easy. Because you do not have previous pointer. Since our DLL has previous pointers, its reversal must be easy.

I wrote a program earlier similar to SLL reversal- taking 3 nodes at a time and reversing links of two adjacent nodes. But I came across a better solution.

Just swap the previous link and next link for each node.

 NODEPTR reverse_list(NODEPTR head )
 {
    NODEPTR temp=head; NODEPTR t1;
    while(temp)
    {
       //swap links
       t1 = temp->prev;
       temp->prev = temp->next;
       temp->next = t1;
       //move to next node
       temp = temp->prev;
    }
    if(t1!=NULL)
       head = t1->prev;
    return head; 
}

If there was only one node in the list, then t1 will be NULL and head=t1->prev will crash the program. So verify that t1 is not NULL.

The function with complete program is here.


#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;  
   struct node *prev;  
 };  
 typedef struct node * NODEPTR;   
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->prev = temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR tail, NODEPTR newnode)  
 {  
    if(tail!=NULL)
     tail->next = newnode;  
    newnode->prev = tail;  
    tail = newnode;  
    return tail;  
 } 

void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
 }  
 NODEPTR reverse_list(NODEPTR head )
 {
    NODEPTR temp=head; NODEPTR t1;
    while(temp)
    {
       t1 = temp->prev;
       temp->prev = temp->next;
       temp->next = t1;
       temp = temp->prev;
    }
    if(t1!=NULL)
       head = t1->prev;
    return head; 
}     
int main()  
 {  
     NODEPTR head,tail;  
     NODEPTR newnode;  
     int numnodes,i;  
     //initialize head and tail. Very important!!  
     head = tail = NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);      
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       tail = append_node(tail,newnode);
       if(head==NULL)  
       {  
          head = tail;  
       }  
     }     
     printf("The doubly linked list is ");  
     display_nodes(head); 
    
     head = reverse_list(head); 
     printf("The doubly linked list in reverse is ");  
     display_nodes(head);  
 }

Comments

Post a Comment

Popular posts from this blog

Program to create a Linked List in C

An array is a commonly used data structure in most of the languages. Because it is simple, it needs O(1) time for accessing elements. It is also compact. But an array has a serious drawback - it can not grow or shrink. You need to estimate the array size and define it during compile time. This drawback is not present a linked list. A linked list is a data structure which can grow or shrink dynamically.  A linked list has nodes each of which contain  contain  data and a link to next node . These nodes are dynamically allocated structures. If you need more nodes, you just need to allocate memory for these and link these nodes to the existing list. The nodes of a linked list have to be defined as self-referential structures in C. That is structures with data members and one member which is a pointer to the structure of same type.  This pointer will work as a link to next node. struct node { int data; struct node * next; //pointer to another node }...
1 comment
Read more

Mirror tree

Question : Write a function to mirror a binary tree. The mirror tree will have a left subtree and right subtree swapped. But this has to be done for each and every node. So to convert a tree to its mirror, we can write an algorithm like this               1) mirror left subtree recursively               2) mirror right subtree recursively               3) swap left and right children of the current node. Here is the function for it. void mirror_tree (NODEPTR root) { if (root != NULL ) { NODEPTR temp = root -> left; root -> left = root -> right; root -> right = temp; mirror_tree(root -> left); mirror_tree(root -> right); } }
Post a Comment
Read more

Josephus problem

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...
Post a Comment
Read more