September 26, 2024

Reverse Doubly Linked List

Problem Statement

You are given a pointer or reference to the doubly linked list’s head node and the task is to reverse a doubly linked list (the order should be reversed). After changing the order, you need to return the pointer or reference to the head node of the reversed doubly linked list.

Refer to the example and explanation section for more details and the approach section to understand how to reverse a doubly linked list.

Example

The given input doubly linked list is :

1 <-> 2 <-> 3 <-> NULL

The user needs to reverse the doubly linked list.

After the reversal, the reverse doubly linked list is the output :

3 <-> 2 <-> 1 <-> NULL

Example Explanation

Before getting into the explanation of the example and how to reverse a doubly linked list, let us first get a brief introduction about the doubly linked lists.

The doubly linked list is a sequential collection of data elements connected via links. The data element of a doubly linked list node contains three parts namely – the data part and two-pointers.

The data part contains the actual data. One of the pointers points to the next element of the doubly linked list and the other pointer points to the previous element of the doubly linked list.

Note :

The previous pointer of the head node of a doubly-linked list points to NULL similarly to the next pointer of the last node of a doubly-linked list points.

Example :

Now, let us take the same example as above and learn how to reverse a doubly linked list. We have drawn the links (pointed by pointers) so that the actual doubly linked list can be visualized easily.

Initially, the first node is 1, and its next pointer points to node-2. The pointer of node-2 points to node-3 and finally, the pointer of node-3 points to NULL. So after the reversal, the last node becomes the first node, the second last node becomes the second node, and so on. Hence after continuing this procedure,

The final output becomes :

3 <-> 2 <-> 1 <-> NULL.

So, we need to return the head pointer which is now pointing to the node-3.

Constraints

The first input is the number of elements present in the doubly linked list i.e. n.
The second input is the sequential set of elements of the doubly linked list.

In some problems, you may find the number of test cases represented by t. So, we only need to call the reverse function t-times.

Approach – 1: Simple Method

Let us learn the most basic approach to reverse a doubly linked list. One of the most basic or brute force solutions can be swapping the previous and next pointer of each node and finally changing the head pointer to the end of the doubly linked list.

Pseudo code can be :

1. Take two-pointers.
2. Let the first pointer point to NULL and the second pointer point to the head node.
3. Using these two pointers swap the next and previous pointer for all nodes of the doubly linked list.
4. At last set the head pointer to the last node of the doubly linked list.

C++ Code :

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

/*
Creating a class-based node to represent one element of the doubly linked list.
*/
class DLL_Node
{
public:
   int data;
   DLL_Node *next;
   DLL_Node *previous;
};

/*
A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
*/
void reverse(DLL_Node **head)
{
   /*
   We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
   */
   DLL_Node *first = NULL;
   DLL_Node *second = *head;

   /*
   We will swap all nodes i.e. until the second pointer is not NULL.
   */
   while (second != NULL)
   {
      first = second->previous;
      second->previous = second->next;
      second->next = first;
      second = second->previous;
   }

   // Finally making the head pointer point to the last node.
   if (first != NULL)
      *head = first->previous;
}

// A function to insert new nodes into the Doubly Linked list.
void insert(DLL_Node **head, int data)
{
   DLL_Node *new_node = new DLL_Node();

   new_node->data = data;
   new_node->previous = NULL;
   new_node->next = (*head);

   if ((*head) != NULL)
      (*head)->previous = new_node;

   (*head) = new_node;
}

// A function to print the nodes of the Doubly Linked list.
void print_DLL(DLL_Node *node)
{
   while (node != NULL)
   {
      cout << node->data << " <--> ";
      node = node->next;
   }
   cout << "NULL";
}

int main()
{
   /*
   Initializing an empty doubly linked list with the head pointer pointing to NULL.
   */
   DLL_Node *head = NULL;

   /*
   Insert values into the doubly linked list using the insert function defined above.
   */
   insert(&head, 1);
   insert(&head, 2);
   insert(&head, 3);
   insert(&head, 4);
   insert(&head, 5);

   /*
   Initially printing the original doubly linked list using the function print_DLL().
   */
   cout << "\nThe initial doubly linked list is: ";
   print_DLL(head);

   /*
   Reversing the doubly linked list by providing the head of the list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
   */
   reverse(&head);

   cout << "\nThe revered doubly linked list is: ";
   print_DLL(head);

   return 0;
}

Java Code :

public class Main {

    // creating a reference of the head.
    static DLLNode head;

    // Creating a class-based node to represent one element of the doubly linked list.
    static class DLLNode {
        int data;
        DLLNode next, previous;

        // Constructor of the Node class
        DLLNode(int data)
        {
            this.data = data;
            next = previous = null;
        }
    }


    /*
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    */
    void reverse()
    {
        /*
        We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
        */
        DLLNode first = null;
        DLLNode second = head;

        /*
        We will swap all nodes i.e. until the second pointer is not NULL.
        */
        while (second != null) {
            first = second.previous;
            second.previous = second.next;
            second.next = first;
            second = second.previous;
        }
        if (first != null) {
            head = first.previous;
        }
    }

    // A function to insert new nodes into the Doubly Linked list.
    void insert(int data)
    {
        DLLNode new_node = new DLLNode(data);

        new_node.previous = null;
        new_node.next = head;

        if (head != null) {
            head.previous = new_node;
        }

        head = new_node;
    }

    // A function to print the nodes of the Doubly Linked list.
    void print_DLL(DLLNode node)
    {
        while (node != null) {
            System.out.print(node.data + " <--> ");
            node = node.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args)
    {
        /*
        Initializing an empty doubly linked list with the head pointer pointing to NULL.
        */
        Main list = new Main();

        /*
        Insert values into the doubly linked list using the insert function defined above.
        */
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);


        System.out.println("\nThe initial doubly linked list is: ");
        list.print_DLL(head);

        /*
        Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
        */
        list.reverse();

        System.out.println("\nThe revered doubly linked list is: ");
        list.print_DLL(head);
    }
}

Python Code :

"""
Creating a class-based node to represent one element of the doubly linked list.
"""


class DLLNode:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


"""
Creating a class that will contain functions of the doubly linked list.
"""


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

    """
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """

    def reverse(self):
        """
        We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
        """
        first = None
        second = self.head

        """
        We will swap all nodes i.e. until the second pointer is not NULL.
        """
        while second is not None:
            first = second.prev
            second.prev = second.next
            second.next = first
            second = second.prev

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

    # A function to insert new nodes into the Doubly Linked list.
    def insert(self, data):
        new_node = DLLNode(data)
        new_node.next = self.head

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

        self.head = new_node

    # A function to print the nodes of the Doubly Linked list.
    def print_DLL(self, node):
        while(node is not None):
            print(node.data, end=' <--> ')
            node = node.next
        print("NULL")


if __name__ == "__main__":
    """
    Initializing an empty doubly linked list with the head pointer pointing to NULL.
    """
    dll = DoublyLinkedList()

    """
    Insert values into the doubly linked list using the insert function defined above.
    """
    dll.insert(1)
    dll.insert(2)
    dll.insert(3)
    dll.insert(4)
    dll.insert(5)

    """
    Initially printing the original doubly linked list using the function print_DLL().
    """
    print("\nThe initial doubly linked list is: ")
    dll.print_DLL(dll.head)

    """
    Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """
    dll.reverse()

    print("\nThe revered doubly linked list is: ")
    dll.print_DLL(dll.head)

Output :

The initial doubly linked list is: 5 <--> 4 <--> 3 <--> 2 <--> 1 <--> NULL
The revered doubly linked list is: 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> NULL

Complexity Analysis

In this brute force approach to reverse a doubly linked list, we are traversing the doubly linked list once. Apart from that, we are not using any extra space rather than two-pointers or references namely – first and second.

Time Complexity :

The time complexity of the above approach is O(n), where n is the number of nodes in the doubly linked list.

Space Complexity :

The space complexity of the above approach is: O(1)

Approach – 2: Using Stack

Another basic approach to reverse doubly linked lists can be using a stack data structure. As we know, the stack has a property that the element which is inserted first gets removed last. So, we can use this property and keep on inserting all the elements of the Doubly Linked List sequentially into the stack, and at the end, we start popping out the elements from the stack to get the reversed order.

Pseudo code can be :

1. Take a stack.
2. Keep on inserting all the elements of the Doubly Linked List sequentially into the stack.
3. Keep on popping the elements from the stack and updating the doubly linked list.

C++ Code :

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

class DLL_Node
{
public:
   int data;
   DLL_Node *next, *previous;

   // A default constructor.
   DLL_Node()
   {
   }

   // A parameterized constructor.
   DLL_Node(int data)
   {
      this->data = data;
      next = previous = NULL;
   }
};

/*
DoublyLinkedList class will inherit the DLL_Node class which contains the data part and pointers. The DoublyLinkedList class contains functions of the doubly linked list.
*/
class DoublyLinkedList: public DLL_Node
{
public:
   // A default constructor.
   DoublyLinkedList()
   {
   }

   DLL_Node *head = NULL;

   /*
   A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
   */
   void reverse()
   {
      /*
      We will take a stack and start inserting elements into the stack. Once all the elements are inserted we can get the elements in the reverse order.
      We will also need a reference or pointer to traverse the doubly linked list.
      */

      stack<int> s;
      DLL_Node *temporary = head;
      while (temporary != NULL)
      {
         s.push(temporary->data);
         temporary = temporary->next;
      }

      temporary = head;
      while (temporary != NULL)
      {
         temporary->data = s.top();
         s.pop();
         temporary = temporary->next;
      }
   }

   // A function to insert new nodes into the Doubly Linked list.
   void insert(int data)
   {
      DLL_Node *node = new DLL_Node(data);

      node->previous = NULL;
      node->next = head;

      if (head != NULL)
      {
         head->previous = node;
      }
      head = node;
   }

   // A function to print the nodes of the Doubly Linked list.
   void print_DLL(DLL_Node *node)
   {
      while (node)
      {
         cout << node->data << " <--> ";
         node = node->next;
      }
      cout << "NULL";
   }
};

int main()
{
   DoublyLinkedList list;

   /*
   Insert values into the doubly linked list using the insert function defined above.
   */
   list.insert(1);
   list.insert(2);
   list.insert(3);
   list.insert(4);
   list.insert(5);

   cout << "\nThe initial doubly linked list is: ";
   list.print_DLL(list.head);

   /*
   Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
   */
   list.reverse();

   cout << "\nThe revered doubly linked list is: ";
   list.print_DLL(list.head);
}

Java Code :

import java.util.*;
public class Main {

    // creating a reference of the head.
    static DLLNode head;

    // Creating a class-based node to represent one element of the doubly linked list.
    static class DLLNode {
        int data;
        DLLNode next, previous;

        // Constructor of the Node class
        DLLNode(int data)
        {
            this.data = data;
            next = previous = null;
        }
    }


    /*
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    */
    void reverse()
    {
        /*
        We will take a stack and start inserting elements into the stack. Once all the elements are inserted we can get the elements in the reverse order.
        We will also need a reference or pointer to traverse the doubly linked list.
        */
        Stack<Integer> stack = new Stack<>();
        DLLNode temporary = head;

        while (temporary != null) {
            stack.push(temporary.data);
            temporary = temporary.next;
        }

        temporary = head;
        while (temporary != null) {
            temporary.data = stack.pop();
            temporary = temporary.next;
        }
    }

    // A function to insert new nodes into the Doubly Linked list.
    void insert(int data)
    {
        DLLNode new_node = new DLLNode(data);

        new_node.previous = null;
        new_node.next = head;

        if (head != null) {
            head.previous = new_node;
        }

        head = new_node;
    }

    // A function to print the nodes of the Doubly Linked list.
    void print_DLL(DLLNode node)
    {
        while (node != null) {
            System.out.print(node.data + " <--> ");
            node = node.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args)
    {
        /*
        Initializing an empty doubly linked list with the head pointer pointing to NULL.
        */
        Main list = new Main();

        /*
        Insert values into the doubly linked list using the insert function defined above.
        */
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);


        System.out.println("\nThe initial doubly linked list is: ");
        list.print_DLL(head);

        /*
        Reversing the doubly linked list by providing the head of the list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
        */
        list.reverse();

        System.out.println("\nThe revered doubly linked list is: ");
        list.print_DLL(head);
    }
}

Python Code :

"""
Creating a class-based node to represent one element of the doubly linked list.
"""


class DLLNode:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


"""
Creating a class that will contain functions of the doubly linked list.
"""


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

    """
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """

    def reverse(self):
        """
        We will take a stack and start inserting elements into the stack. Once all the elements are inserted we can get the elements in the reverse order.
        We will also need a reference or pointer to traverse the doubly linked list.
        """
        stack = []
        temporary = self.head
        while temporary is not None:
            stack.append(temporary.data)
            temporary = temporary.next

        temporary = self.head
        while temporary is not None:
            temporary.data = stack.pop()
            temporary = temporary.next

    # A function to insert new nodes into the Doubly Linked list.
    def insert(self, data):
        new_node = DLLNode(data)
        new_node.next = self.head

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

        self.head = new_node

    # A function to print the nodes of the Doubly Linked list.
    def print_DLL(self, node):
        while(node is not None):
            print(node.data, end=' <--> ')
            node = node.next
        print("NULL")


if __name__ == "__main__":
    """
    Initializing an empty doubly linked list with the head pointer pointing to NULL.
    """
    dll = DoublyLinkedList()

    """
    Insert values into the doubly linked list using the insert function defined above.
    """
    dll.insert(1)
    dll.insert(2)
    dll.insert(3)
    dll.insert(4)
    dll.insert(5)

    """
    Initially printing the original doubly linked list using the function print_DLL().
    """
    print("\nThe initial doubly linked list is: ")
    dll.print_DLL(dll.head)

    """
    Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """
    dll.reverse()

    print("\nThe revered doubly linked list is: ")
    dll.print_DLL(dll.head)

Output :

The initial doubly linked list is: 5 <--> 4 <--> 3 <--> 2 <--> 1 <--> NULL
The revered doubly linked list is: 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> NULL

Complexity Analysis

In this stack-based approach to reverse a doubly linked list, we are traversing the doubly linked list once. Apart from that, we are using extra space in the form of a stack.

Time Complexity :

The time complexity of the above approach is O(n), where n is the number of nodes in the doubly linked list.

Space Complexity :

The space complexity of the above approach is O(n), where n is the size of the stack.

Approach – 3: Recursive Solution

In the recursive approach to reverse the doubly linked list, we will change the previous and next pointer of the current node and pass the rest of the doubly linked list to the recursive function. So, at each recursive call, one of the doubly linked lists is interchanged and we get our desired result.

Pseudo code can be :

1. Check if the doubly linked list is empty or not. If the doubly linked list is empty then stop the recursive call and return the current head.
2. Else, reverse the pointers of the current node and recursively call the reverse function on the next node.

C++ Code :

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

// a node of the doubly linked list
class DLL_Node
{
public:
   int data;
   DLL_Node *next, *previous;
};

// function to create a new node
DLL_Node *create_DLLNode(int data)
{
   DLL_Node *node = new DLL_Node;
   node->data = data;
   node->next = node->previous = NULL;

   return node;
}

// A function to insert new nodes into the Doubly Linked list.
void insert(DLL_Node **head, DLL_Node *node)
{
   node->previous = NULL;
   node->next = (*head);

   if ((*head) != NULL)
      (*head)->previous = node;

   (*head) = node;
}

// A function to print the nodes of the Doubly Linked list.
void print_DLL(DLL_Node *head)
{
   while (head != NULL)
   {
      cout << head->data << " <--> ";
      head = head->next;
   }
   cout << "NULL";
}

/*
A function to reverse the list and returns the head pointer of the reversed doubly linked list.
*/
DLL_Node *reverse_DLL(DLL_Node *node)
{
    if (!node)
        return NULL;

    /*
    reverse the pointers of the current node and recursively call the reverse function on the next node.
    */
    DLL_Node *temporary = node->next;
    node->next = node->previous;
    node->previous = temporary;

    if (!node->previous)
        return node;

    return reverse_DLL(node->previous);
}

int main()
{
   /*
   Initializing an empty doubly linked list with the head pointer pointing to NULL.
   */
   DLL_Node *head = NULL;

   /*
   Insert values into the doubly linked list using the insert function defined above.
   */
   insert(&head, create_DLLNode(1));
   insert(&head, create_DLLNode(2));
   insert(&head, create_DLLNode(3));
   insert(&head, create_DLLNode(4));
   insert(&head, create_DLLNode(5));

   cout << "\nThe initial doubly linked list is: ";
   print_DLL(head);

   /*
   The function will reverse the list and returns the head pointer of the reversed doubly linked list.
   */
   head = reverse_DLL(head);

   cout << "\nThe revered doubly linked list is: ";
   print_DLL(head);

   return 0;
}

Java Code :

class Main {
    // Creating a class-based node to represent one element of the doubly linked list.
    static class DLLNode {
        int data;
        DLLNode next, previous;
    }

    // function to create a new node.
    static DLLNode create_DLLNode(int data) {
        DLLNode new_node = new DLLNode();
        new_node.data = data;
        new_node.next = new_node.previous = null;
        return new_node;
    }

    /*
    A function to reverse the list and returns the head pointer of the reversed doubly linked list.
    */
    static DLLNode reverse_DLL(DLLNode node) {
        if (node == null)
        return null;

        /*
        reverse the pointers of the current node and recursively call the reverse function on the next node.
        */

        DLLNode temporary = node.next;
        node.next = node.previous;
        node.previous = temporary;

        if (node.previous == null)
            return node;

        return reverse_DLL(node.previous);
    }

    // A function to insert new nodes into the Doubly Linked list.
    static DLLNode insert(DLLNode head, DLLNode node) {
        node.previous = null;
        node.next = (head);

        if ((head) != null)
            (head).previous = node;

        (head) = node;
        return head;
    }

    // A function to print the nodes of the Doubly Linked list.
    static void print_DLL(DLLNode node) {
        while (node != null) {
            System.out.print(node.data + " <--> ");
            node = node.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        /*
        Initializing an empty doubly linked list with the head pointer pointing to NULL secondly.
        */
        DLLNode head = null;

        /*
        Insert values into the doubly linked list using the insert function defined above.
        */
        head = insert(head, create_DLLNode(1));
        head = insert(head, create_DLLNode(2));
        head = insert(head, create_DLLNode(3));
        head = insert(head, create_DLLNode(4));
        head = insert(head, create_DLLNode(5));

        System.out.println("\nThe initial doubly linked list is: ");
        print_DLL(head);

        /*
        The function will reverse the list and returns the head pointer of the reversed doubly linked list.
        */
        head = reverse_DLL(head);

        System.out.println("\nThe revered doubly linked list is: ");
        print_DLL(head);
    }
}

Python Code :

"""
Creating a class-based node to represent one element of the doubly linked list.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.previous = None



# function that will create a new node.
def create_node(data):
    node = Node(data)
    return node



# A function to insert new nodes into the Doubly Linked list.
def insert(head, node):
    node.previous = None
    node.next = head

    if (head != None):
        head.previous = node

    head = node
    return head



# A function to print the nodes of the Doubly Linked list.
def print_DLL(head):
    while (head != None):
        print(head.data, end=" <--> ")
        head = head.next
    print("NULL")



"""
A function to reverse the list and returns the head pointer of the reversed doubly linked list.
"""
def reverse_DLL(node):
    if not node:
        return None

    """
    reverse the pointers of the current node and recursively call the reverse function on the next node.
    """

    temporary = node.next
    node.next = node.previous
    node.previous = temporary

    if not node.previous:
        return node

    return reverse_DLL(node.previous)



if __name__ == '__main__':
    """
    Initializing an empty doubly linked list with the head pointer pointing to NULL.
    """

    head = None

    """
    Insert values into the doubly linked list using the insert function defined above.
    """
    head = insert(head, create_node(1))
    head = insert(head, create_node(2))
    head = insert(head, create_node(3))
    head = insert(head, create_node(4))
    head = insert(head, create_node(5))

    print("\nThe initial doubly linked list is: ")
    print_DLL(head)

    """
    The function will reverse the list and returns the head pointer of the reversed doubly linked list.
    """

    head = reverse_DLL(head)

    print("\nThe revered doubly linked list is: ")
    print_DLL(head)

Output :

The initial doubly linked list is: 5 <--> 4 <--> 3 <--> 2 <--> 1 <--> NULL
The revered doubly linked list is: 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> NULL

Complexity Analysis

In this recursive approach to reverse a doubly linked list, we are traversing the doubly linked list once. Apart from that, we are using extra space in the form of a stack.

Time Complexity :

The time complexity of the above approach is O(n), where n is the number of nodes in the doubly linked list.

Space Complexity :

The space complexity of the above approach is O(n) because the recursive solution is using a recursive stack of size n.

Approach – 4 : Iterative Solution

The iterative approach to reverse doubly linked list is similar to the brute force approach . We need to use two pointers to swap the previous and next pointers of each node of the doubly linked list.

Pseudo code can be :

1. Take two pointers, the first pointer pointing to NULL and the second pointer pointing to the head node.
2. Using these two pointers swap the next and previous pointers for all nodes of the doubly linked list.
4. At last set the head pointer to the last node of the doubly linked list.

C++ Code :

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

/*
Creating a class-based node to represent one element of the doubly linked list.
*/
class DLL_Node
{
public:
   int data;
   DLL_Node *next;
   DLL_Node *previous;
};

/*
A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
*/
void reverse(DLL_Node **head)
{
   /*
   We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
   */
   DLL_Node *first = NULL;
   DLL_Node *second = *head;

   /*
   We will swap all nodes i.e. until the second pointer is not NULL.
   */
   while (second != NULL)
   {
      first = second->previous;
      second->previous = second->next;
      second->next = first;
      second = second->previous;
   }

   // Finally making the head pointer point to the last node.
   if (first != NULL)
      *head = first->previous;
}

// A function to insert new nodes into the Doubly Linked list.
void insert(DLL_Node **head, int data)
{
   DLL_Node *new_node = new DLL_Node();

   new_node->data = data;
   new_node->previous = NULL;
   new_node->next = (*head);

   if ((*head) != NULL)
      (*head)->previous = new_node;

   (*head) = new_node;
}

// A function to print the nodes of the Doubly Linked list.
void print_DLL(DLL_Node *node)
{
   while (node != NULL)
   {
      cout << node->data << " <--> ";
      node = node->next;
   }
   cout << "NULL";
}

int main()
{
   /*
   Initializing an empty doubly linked list with the head pointer pointing to NULL.
   */
   DLL_Node *head = NULL;

   /*
   Insert values into the doubly linked list using the insert function defined above.
   */
   insert(&head, 1);
   insert(&head, 2);
   insert(&head, 3);
   insert(&head, 4);
   insert(&head, 5);

   /*
   Initially printing the original doubly linked list using the function print_DLL().
   */
   cout << "\nThe initial doubly linked list is: ";
   print_DLL(head);

   /*
   Reversing the doubly linked list by providing the head of the list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
   */
   reverse(&head);

   cout << "\nThe revered doubly linked list is: ";
   print_DLL(head);

   return 0;
}

Java Code :

public class Main {

    // creating a reference of the head.
    static DLLNode head;

    // Creating a class-based node to represent one element of the doubly linked list.
    static class DLLNode {
        int data;
        DLLNode next, previous;

        // Constructor of the Node class
        DLLNode(int data)
        {
            this.data = data;
            next = previous = null;
        }
    }


    /*
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    */
    void reverse()
    {
        /*
        We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
        */
        DLLNode first = null;
        DLLNode second = head;

        /*
        We will swap all nodes i.e. until the second pointer is not NULL.
        */
        while (second != null) {
            first = second.previous;
            second.previous = second.next;
            second.next = first;
            second = second.previous;
        }
        if (first != null) {
            head = first.previous;
        }
    }

    // A function to insert new nodes into the Doubly Linked list.
    void insert(int data)
    {
        DLLNode new_node = new DLLNode(data);

        new_node.previous = null;
        new_node.next = head;

        if (head != null) {
            head.previous = new_node;
        }

        head = new_node;
    }

    // A function to print the nodes of the Doubly Linked list.
    void print_DLL(DLLNode node)
    {
        while (node != null) {
            System.out.print(node.data + " <--> ");
            node = node.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args)
    {
        /*
        Initializing an empty doubly linked list with the head pointer pointing to NULL.
        */
        Main list = new Main();

        /*
        Insert values into the doubly linked list using the insert function defined above.
        */
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);


        System.out.println("\nThe initial doubly linked list is: ");
        list.print_DLL(head);

        /*
        Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
        */
        list.reverse();

        System.out.println("\nThe revered doubly linked list is: ");
        list.print_DLL(head);
    }
}

Python Code :

"""
Creating a class-based node to represent one element of the doubly linked list.
"""


class DLLNode:
    # Constructor
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


"""
Creating a class that will contain functions of the doubly linked list.
"""


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

    """
    A function to reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """

    def reverse(self):
        """
        We will take two-pointers. Let the first pointer point to NULL and the second pointer point to the head node. Using this two-pointer, we will swap the next and previous for all nodes of the doubly linked list.
        """
        first = None
        second = self.head

        """
        We will swap all nodes i.e. until the second pointer is not NULL.
        """
        while second is not None:
            first = second.prev
            second.prev = second.next
            second.next = first
            second = second.prev

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

    # A function to insert new nodes into the Doubly Linked list.
    def insert(self, data):
        new_node = DLLNode(data)
        new_node.next = self.head

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

        self.head = new_node

    # A function to print the nodes of the Doubly Linked list.
    def print_DLL(self, node):
        while(node is not None):
            print(node.data, end=' <--> ')
            node = node.next
        print("NULL")


if __name__ == "__main__":
    """
    Initializing an empty doubly linked list with the head pointer pointing to NULL.
    """
    dll = DoublyLinkedList()

    """
    Insert values into the doubly linked list using the insert function defined above.
    """
    dll.insert(1)
    dll.insert(2)
    dll.insert(3)
    dll.insert(4)
    dll.insert(5)

    """
    Initially printing the original doubly linked list using the function print_DLL().
    """
    print("\nThe initial doubly linked list is: ")
    dll.print_DLL(dll.head)

    """
    Reversing the doubly linked list. The function will reverse the list and set the head pointer to the end of the list so that we do not need to return anything.
    """
    dll.reverse()

    print("\nThe revered doubly linked list is: ")
    dll.print_DLL(dll.head)

Output :

The initial doubly linked list is: 5 <--> 4 <--> 3 <--> 2 <--> 1 <--> NULL
The revered doubly linked list is: 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> NULL

Complexity Analysis

In this iterative approach to reverse a doubly linked list, we are traversing the doubly linked list once. Apart from that, we are not using any extra space rather than two-pointers or references namely – first and second.

Time Complexity :

The time complexity of the above approach is O(n), where n is the number of nodes in the doubly linked list.

Space Complexity :

The space complexity of the above approach is O(1).

Conclusion

The doubly linked list is a sequential collection of data elements connected via links.
The data element of a doubly linked list (node) contains three parts namely
the data part and two-pointers. The data part contains the actual data.
One of the pointers points to the next element of the doubly linked list and the other pointer points to the previous element of the doubly linked list.
One of the most basic approaches to reverse a doubly linked list is swapping the previous and next pointer of each node and finally changing the head pointer to the end of the doubly linked list.
Another approach to reverse a doubly linked list is using a stack. We keep on inserting all the elements of the Doubly Linked List sequentially into the stack and at the end, we start popping out the elements from the stack to get the reversed order.
In the recursive approach to reverse a doubly linked list, we change the previous and next pointer of the current node and pass the rest of the doubly linked list to the recursive function.

Author

Sushant Gaurav

View all posts

Reverse Doubly Linked List

Problem Statement

Example

Example Explanation

Constraints

Approach – 1: Simple Method

Complexity Analysis

Approach – 2: Using Stack

Complexity Analysis

Approach – 3: Recursive Solution

Complexity Analysis

Approach – 4 : Iterative Solution

Complexity Analysis

Conclusion

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Reverse Doubly Linked List

Problem Statement

Example

Example Explanation

Constraints

Approach – 1: Simple Method

Complexity Analysis

Approach – 2: Using Stack

Complexity Analysis

Approach – 3: Recursive Solution

Complexity Analysis

Approach – 4 : Iterative Solution

Complexity Analysis

Conclusion

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Featured articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?