Doubly Linked List: Program to reverse a doubly linked list

Write a program to reverse a doubly linked list

A doubly linked list is a type of linked list that consist of nodes and bi-directional edges

• There are 2 edges/links between any two nodes - lets call them 'next' & 'prev'
• 'next' pointer points to next node and 'prev' pointer points to the previous node
• These bi-directional edges help us to navigate forward and backward in a linked list

Approach

Basic idea for reversing a doubly linked list is to swap 'previous' and 'next' links of nodes

Algorithm

1. Create two pointers say current and temp and set current on the head node
2. While current is not NULL, perform the following steps
   • Set temp on current.next
   • Set current.next as current.prev
   • Set current.prev as temp
   • set current as current.next
   • If current and current.next is not NULL, then set head on current

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

Java Code

import java.util.*;

class ReverseDLL{
     
        class Node {
    
            int data;
            Node next, prev;
         
            Node(int data) {
                this.data = data;
                this.next = null;
                this.prev = null;
            }
        }
    
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = temp.prev = null;
            head = temp;
            last = head;
     
            for (int i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                temp.prev = last;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" <-> ", allNodesList));
        }
     
        public void reverseDLL() {
            Node current, temp;
            current = head;
            while (current != null) {
                temp = current.next;
                current.next = current.prev;
                current.prev = temp;
                current = current.prev;
                if (current != null && current.next == null) {
                    head = current;
                }
            }
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 10, 30, 50, 70, 90 };
            int numberOfNodes = 5;
            // initialising object of linkedlist class
            ReverseDLL dll = new ReverseDLL();
            dll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given Double Linked List ");
            dll.printLinkedlist();
            dll.reverseDLL();
            System.out.println("Reversed Double Linked List ");
            dll.printLinkedlist();
     
        }
    
 }

Output

Given Double Linked List
10 <-> 30 <-> 50 <-> 70 <-> 90
Reversed Double Linked List
90 <-> 70 <-> 50 <-> 30 <-> 10