Reverse a Doubly Linked List


Linked list is one of the most famous and important data structures asked in most interviews. In this article, we will learn how to reverse a doubly linked list

A doubly linked list is a data structure which contains nodes with points to the previous node as well to the next node.

How to Reverse a Doubly Linked List

In this problem, we will be given a doubly linked list as input, and we need to reverse it such that the pointer currently pointing to the head of the list will point to the tail of the doubly linked list.

According to the problem statement, we will be given a doubly-linked list, and we need to reverse a doubly linked list.

Let’s understand this problem with the help of some examples.

If the given doubly linked list is:

  • According to the problem statement we need to reverse this given doubly linked list such that after reversing the doubly linked list will look like:

Taking another example, if the given list is head -> 1 2 3 5 6 -> NULL.

  • In this case after reversing a doubly linked list our list will look like: head -> 6 5 3 2 1 -> NULL.

Some more examples

Sample Input 1: 1 3 5 7 11 -> NULL.
Sample Output 1: 11 7 5 3 1 -> NULL.

Sample Input 2: 2 3 5 7 11 17 -> NULL.
Sample Output 2: 17 11 7 5 3 2 -> NULL.

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how you can reverse a doubly linked list.

  • If stuck, no problem, we will thoroughly see how we can reverse a doubly linked list in the next section.

Let’s move to the approach section.

Approach 1 : Using 2 Pointers

This approach will be similar to reversing data present in an array.
1) We will initialize 2 pointers, one at starting and the other at the end of the linked list.
2) We will swap the node’s data to which the pointers are pointing.
3) And then, we will move the pointers toward’s each other by one step.
4) We will be performing step 2 and step 3 untill both the pointers do not cross each other or reach at the same position.
5) Finally, when both pointers reaches the same position, our doubly linked list will be fully reversed.

Time Complexity: O(n), 2 traversals will be required in this approach, one to get the address of the last node and another traversal to reverse the list.

Space Complexity: O(1)

The above approach will work fine, but the only issue is that we are traversing the doubly linked list twice. Now we need to ask ourselves one simple question: Do we actually need two list traversals to reverse the doubly linked list.

Is it possible to reverse a doubly linked list in a single traversal?

  • Yes, it is possible, and we will see it in the following approach.

Let’s move to next approach.

Approach 2: Swapping

As we know that in a doubly linked list, we can access the previous as well as the next node of a given node, so it means that we can easily achieve reversal of the list by swapping the previous with next pointers of all nodes iteratively.

Let’s move to the algorithm section to see the above approach in depth.

Algorithm

  • Create a pointer current. Initialize it with the head of the linked list.
  • Create a pointer temp. Initialize it with NULL.
  • Now swap current’s prev and current’s next using pointer temp.
  • Now move current to current’s previous node because after swapping, current’s prev stores the address of current’s next node.
  • Repeat the process till current does not become NULL.

Dry run


Code Implementation 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;
      
     while (current !=  NULL)
     {
       temp = current->prev;
       current->prev = current->next;
       current->next = temp;             
       current = current->prev;
     }     
      
     if(temp != NULL )
        *head_ref = temp->prev;
}    
 
 
 
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
  
    new_node->data  = new_data;
    
    new_node->prev = NULL;
  
    new_node->next = (*head_ref);   
 
    if((*head_ref) !=  NULL)
      (*head_ref)->prev = 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 list */
void printList(struct Node *node)
{
  while(node!=NULL)
  {
   printf("%d ", node->data);
   node = node->next;
  }
}
 
int main()
{
  /* Start with the empty list */
  struct Node* head = NULL;
  
  push(&head, 2);
  push(&head, 7);
  push(&head, 1);
  push(&head, 13);
  push(&head, 17);
  
  printf("\n Initial linked list before reversing: ");
  printList(head);
  
  reverse(&head);
  
  printf("\n Resultant reversed linked list: ");
  printList(head);          
  
  getchar();
}

#include <bits/stdc++.h>
using namespace std;

/* Node structure of a doubly linked list node */
class Node
{
    public:
    int data;
    Node* next;
    Node* prev;
};

/* Using this below function we will be adding a new node at beginning of the list */
void add_at_begin(Node** head, int x)
{
 
    Node* new_node = new Node();

    new_node->data = x;
 
    new_node->prev = NULL;
 
    new_node->next = (*head);
    
    if ((*head) != NULL)
        (*head)->prev = new_node;
 
    (*head) = new_node;
}

/* Using this below function we will be printing the content of the linked list */
void print_list(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << ",";
        node = node->next;
    }
    cout<<endl;
}

/* Using this below function we will be reversing the given doubly linked list */
void reverse_list(Node **head)
{
    Node *temp = NULL;
    Node *current = *head;
    
    while (current != NULL)
    {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;            
        current = current->prev;
    }
     
    if(temp != NULL )
        *head = temp->prev;
}
 
/* Main function */
int main()
{
    Node* head = NULL;
 
    add_at_begin(&head, 17);
    add_at_begin(&head, 13);
    add_at_begin(&head, 1);
    add_at_begin(&head, 7);
    add_at_begin(&head, 2);
 
    cout<<"Initial linked list before reversing: "<<endl;
    print_list(head);

    reverse_list(&head);
    
    cout<<"Resultant reversed linked list: "<<endl;
    print_list(head);
 
    return 0;
}


class DoublyLinkedList {
 
    static Node head;
 
    static class Node {
 
        int data;
        Node next, prev;
 
        Node(int d)
        {
            data = d;
            next = prev = null;
        }
    }
 
    /* Function to reverse a Doubly Linked List */
    void reverse_list()
    {
        Node temp = null;
        Node current = head;
 
        /* 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 = temp.prev;
        }
    }
    /* Function to insert a node at the beginning of the
     * Doubly Linked List */
    void add_at_begin(int new_data)
    {
        Node new_node = new Node(new_data);
 
        new_node.prev = null;
 
        new_node.next = head;
 
        if (head != null) {
            head.prev = new_node;
        }
        head = new_node;
    }
    void print_list(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    public static void main(String[] args)
    {
        DoublyLinkedList list = new DoublyLinkedList();
 
        list.add_at_begin(17);
    	list.add_at_begin(13);
    	list.add_at_begin(1);
    	list.add_at_begin(7);
    	list.add_at_begin(2);
 
        System.out.println("Original linked list ");
        list.print_list(head);
 
        list.reverse_list();
        System.out.println("");
        System.out.println("The reversed Linked List is ");
        list.print_list(head);
    }
}


class Node:
	# Node structure of a doubly linked list node
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None


class DoublyLinkedList:
	def __init__(self):
		self.head = None

	# Function reverse a Doubly Linked List
	def reverse_list(self):
		temp = None
		current = self.head

		while current is not None:
			temp = current.prev
			current.prev = current.next
			current.next = temp
			current = current.prev

		if temp is not None:
			self.head = temp.prev

	# Using this below function we will be adding a new node at beginning of the list
	def add_at_begin(self, x):

		new_node = Node(x)

		new_node.prev = None

		new_node.next = self.head

		if self.head is not None:
			self.head.prev = new_node

		self.head = new_node

	# Using this below function we will be printing the content of the linked list
	def print_list(self, node):
		while(node is not None):
			print(node.data,end=',')
			node = node.next


# main code
dll = DoublyLinkedList()
dll.add_at_begin(17)
dll.add_at_begin(13)
dll.add_at_begin(1)
dll.add_at_begin(7)
dll.add_at_begin(2)

print ("Initial linked list before reversing: ")
dll.print_list(dll.head)

# Reverse doubly linked list
dll.reverse_list()

print ("Resultant reversed linked list: ")
dll.print_list(dll.head)

Output

Initial linked list before reversing:
2,7,1,13,17,
Resultant reversed linked list:
17,13,1,7,2,

Time Complexity: O(n), where n is the number of nodes in the linked list.

So, in this article, we have explained how you can reverse a doubly linked list using different reverse doubly linked list algorithm. This is a basic problem and is good for strengthening your concepts in LinkedList

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What is a doubly linked list?
  2. A doubly linked list is a data structure which contains nodes with points to the previous node as well to the next node.

  3. What is the time complexity for reversing a doubly linked list?
  4. Time Complexity for reversing a doubly linked list is O(1).

  5. Can we reverse a doubly linked list in less than O(N)?
  6. We can reverse a doubly linked list in less than O(N) time as we need to traverse till the end to find the tail node.

Leave a Reply

Your email address will not be published. Required fields are marked *