We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Reverse a Doubly Linked List
Last updated:
In this tutorial we are going to talk about how to reverse a doubly linked list using the Java program.
In order to reverse a doubly linked list, we need to iterate through the list while swapping the next and previous pointers of each node. Once we reach the end of the list, the head pointer will point to the last node of the list.
Let's understand the reverse of a doubly linked list with the given example below:
Example: Reverse a Doubly Linked List in Java
Class: Node
Node.java
public class Node {
int data; // Data stored in the node
Node prev; // Reference to the next node in the list
Node next; // Reference to the previous node in the list
// Constructor to initialize a new node with data
Node(int new_data) {
data = new_data;
prev = null;
next = null;
}
}
Class: ReverseDoublyLinkedList
ReverseDoublyLinkedList.java
// Java program to reverse a doubly linked list using recursion approach
public class ReverseDoublyLinkedList {
static Node head;
// Method to insert a node in doubly linked list
static void insertNode(int data) {
Node newNode = new Node(data);
Node last = head;
if (head == null) {
head = newNode;
return;
}
while (last.next != null) {
last = last.next;
}
last.next = newNode;
newNode.prev = last;
}
// Method to reverse a doubly linked list using recursive approach
static Node reverseList(Node node) {
// If node is null that means list is empty
if (node == null)
return null;
// Swap the next and previous pointers
Node temp = node.prev;
node.prev = node.next;
node.next = temp;
// If prev is null after swap, this is the new head
if (node.prev == null) {
return node;
}
// Recurse for the next node
return reverseList(node.prev);
}
// Method to print a list
static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Insert node into a doubly linked list
insertNode(10);
insertNode(20);
insertNode(30);
insertNode(40);
insertNode(50);
System.out.println("Original doubly linked list:");
printList(head);
// Reverse the doubly linked list
head = reverseList(head);
System.out.println("Reversed doubly linked list:");
printList(head);
}
}
here n means the total number of nodes in a doubly linked list.
Frequently Asked Questions (FAQ)
Q1. How do you reverse a doubly linked list?
Swap the prev and next references of every node. The last node processed becomes the new head:
ReverseDoubly.java
static Node reverse(Node head) {
Node current = head;
Node newHead = head;
while (current != null) {
Node temp = current.prev;
current.prev = current.next;
current.next = temp;
newHead = current;
current = current.prev; // prev now holds the old next
}
return newHead;
}
It runs in O(n) time and O(1) space.
Q2. Why do we move to current.prev instead of current.next after swapping?
After the swap, current.prev holds what used to be current.next. Moving to current.prev therefore continues forward through the original list.
Q3. How is reversing a doubly linked list different from reversing a singly linked list?
In a singly linked list you must track the previous node yourself and rewrite one link per node. In a doubly linked list each node already knows both neighbours, so you only swap its two links. Both are O(n).
Q4. If the list keeps head and tail references, what else must change?
Swap the head and tail references after reversing the links, because the old tail is now the first node and the old head is now the last.
Q5. Write a recursive Java method to reverse a doubly linked list.
ReverseRecursive.java
static Node reverse(Node node) {
if (node == null) {
return null;
}
Node temp = node.next;
node.next = node.prev;
node.prev = temp;
if (node.prev == null) {
return node; // this was the last node: new head
}
return reverse(node.prev);
}
Q6. Can you reverse a doubly linked list by swapping data instead of links?
Yes. Use one pointer from the head and one from the tail and swap their values until they meet:
ReverseBySwappingData.java
static void reverseData(Node head, Node tail) {
Node left = head, right = tail;
while (left != right && left.prev != right) {
int temp = left.data;
left.data = right.data;
right.data = temp;
left = left.next;
right = right.prev;
}
}
This is simple, but swapping links is preferred when nodes hold large objects or are referenced elsewhere.
Q7. What are the edge cases when reversing?
An empty list returns null.
A one-node list stays the same.
The caller must store the returned new head.
Q8. How do you verify that the reversal worked?
Print the list forward from the new head and backward from the new tail. The forward output should be the old backward output. Also check that the new head's prev is null.
Q9. Do you need to reverse a doubly linked list to print it backward?
No. You can print it backward without changing it by starting at the tail and following prev. Reverse the list only when its actual order must change.
Q10. What is the time and space complexity of each approach?
Swapping links iteratively: O(n) time, O(1) space.
Recursive reversal: O(n) time, O(n) stack space.
Swapping data with two pointers: O(n) time, O(1) space.
