Reverse a Doubly Linked List

Today we will be discussing how to reverse a doubly linked list. But if you are new to doubly linked list then please refer to this link where I have explained everything about doubly linked list from basic to advance.
Reversing a doubly linked list is a tricky problem which is asked in many interviews. In a doubly linked list every node has 2 pointers - one pointing to next node and the other one pointing to previous node. Many students forget the fact that doubly linked list is a special type of linked list which can be reversed much easier than a singly linked list.

Procedure

1. First we will make a linked list.

2. Then we just have to iterate the doubly linked list till the end but make sure to initialize the previous pointer of the first node to NULL because after reversing the list the first node will become the last node and last node must point to NULL.

3. When we reach the last node we assign head pointer the address of last node .

4. Now you can iterate the list from head and instead of using next pointer to iterate the list use previous pointer to iterate the list and you will get the list in reverse order.

Code

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* next;
    struct node* prev;
};
struct node* head=NULL;

class linked
{
public:
    void insert(int x)
    {
        struct node* temp=new node();
        temp->data=x;
        temp->next=NULL;
        temp->prev=NULL;
        if(head==NULL)
        {
            head=temp;
        }
        else
        {
            struct node* temp1=head;
            while(temp1->next!=NULL)
            {
                temp1=temp1->next;
            }
            temp1->next =temp;
            temp->prev =temp1;
            temp->next=NULL;

        }
    }

    void reverse()
    {
        struct node* temp=head;
        temp->prev=NULL;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        head=temp;

        temp=head;
        cout<<"reversed doubly linked list: ";
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->prev;
        }
        cout<<endl;
    }

    void disp()
    {
        struct node* temp=head;
        cout<<"original linked list: ";
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(1);
    l.insert(2);
    l.insert(4);
    l.insert(5);
    l.insert(6);
    l.insert(8);
    l.insert(9);
    l.insert(18);
    l.disp();
    l.reverse();
    return 0;
}

Explanation of Code

1. First we will write a simple code of doubly linked list which will have 2 functions:

- insert() - which will insert elements in the doubly linked list.
- disp() - which will display the doubly linked list.

2. Insert some values in the doubly linked list.

3. Now we have created a function named reverse() for reverse the doubly linked list.

4. First we have created a pointer to node named temp initialized to head of the list.

5. Then we have initialized the previous of temp to NULL because after reversing the list this node will become the last node of the list so its prev should be initialized to NULL.

temp->prev=NULL;

6. Then have iterated the list till the last node.

while(temp->next!=NULL)
{
temp=temp->next;
}

7. Then we have assigned head pointer the address of temp because after reversing the list the last node will be the first node and first node's address is contained in head pointer.

head=temp;

8. Next we have printed the data of list but in the loop we have used prev pointer to access the next node because in a doubly list we have 2 pointers for every node so we can traverse it from both the ends.

while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->prev;
}

Reverse a Doubly Linked List

Procedure

Code

Explanation of Code

Contact Form