.png)
Reverse a Doubly Linked List
Reversing a doubly linked list is a fundamental data structures problem that strengthens understanding of pointer manipulation in both directions. Unlike a singly linked list, each node in a doubly linked list contains two references:
- A pointer to the next node
- A pointer to the previous node
Because of this bidirectional structure, reversing the list becomes conceptually simpler in one sense, but requires careful swapping of both pointers.
This guide covers:
- Problem understanding
- Conceptual foundation
- Iterative approach
- Recursive approach
- Full implementations in C, C++, Java, and Python
- Output examples
- Edge cases
- Complexity analysis
Problem Statement
Given the head pointer of a doubly linked list, reverse the list and return the new head.
Example:
Original list:
10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ NULL
Reversed list:
40 ⇄ 30 ⇄ 20 ⇄ 10 ⇄ NULL
Understanding a Doubly Linked List Structure
Each node contains:
[ prev | data | next ]
Example structure:
NULL ← 10 ⇄ 20 ⇄ 30 → NULL
Key properties:
- head.prev = NULL
- last.next = NULL
- Traversal is possible in both directions
What Does Reversing Mean in a Doubly Linked List?
In a singly linked list, we reverse only the next pointers.
In a doubly linked list, we must swap:
- next pointer
- prev pointer
For every node.
After swapping all pointers, the old tail becomes the new head.
Iterative Approach to Reverse a Doubly Linked List
Core Idea
For each node:
- Swap prev and next
- Move to the previous node (because after swapping, previous becomes next direction)
Algorithm
- If head is NULL → return NULL
- Initialize current = head
- Initialize temp = NULL
- While current is not NULL:
- temp = current.prev
- current.prev = current.next
- current.next = temp
- current = current.prev
- After loop, temp will point to previous node
- New head = temp.prev
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* reverse(struct Node* head) {
struct Node* temp = NULL;
struct 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;
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->prev = NULL; head->next = second;
second->data = 20; second->prev = head; second->next = third;
third->data = 30; third->prev = second; third->next = NULL;
printf("Original List:\n");
printList(head);
head = reverse(head);
printf("Reversed List:\n");
printList(head);
return 0;
}Output:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) {
data = val;
prev = NULL;
next = NULL;
}
};
Node* reverse(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;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " <-> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = new Node(10);
Node* second = new Node(20);
Node* third = new Node(30);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
cout << "Original List:" << endl;
printList(head);
head = reverse(head);
cout << "Reversed List:" << endl;
printList(head);
return 0;
}Output:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
Java Implementation
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
}
}
public class Main {
static Node reverse(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;
return head;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " <-> ");
head = head.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
System.out.println("Original List:");
printList(head);
head = reverse(head);
System.out.println("Reversed List:");
printList(head);
}
}
Output:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def reverse(head):
temp = None
current = head
while current is not None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
if temp is not None:
head = temp.prev
return head
def print_list(head):
while head is not None:
print(head.data, end=" <-> ")
head = head.next
print("NULL")
head = Node(10)
second = Node(20)
third = Node(30)
head.next = second
second.prev = head
second.next = third
third.prev = second
print("Original List:")
print_list(head)
head = reverse(head)
print("Reversed List:")
print_list(head)
Output:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
Recursive Approach to Reverse a Doubly Linked List
Concept
For each node:
- Swap prev and next
- Recursively call reverse on new prev
Base Case:
If head is NULL → return NULL
If head.next is NULL → after swapping, return head
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(n) due to recursion stack
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* reverseRecursive(struct Node* head) {
if (head == NULL)
return NULL;
struct Node* temp = head->next;
head->next = head->prev;
head->prev = temp;
if (head->prev == NULL)
return head;
return reverseRecursive(head->prev);
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->prev = NULL; head->next = second;
second->data = 20; second->prev = head; second->next = third;
third->data = 30; third->prev = second; third->next = NULL;
printf("Original List:\n");
printList(head);
head = reverseRecursive(head);
printf("Reversed List:\n");
printList(head);
return 0;
}Output remains:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) {
data = val;
prev = NULL;
next = NULL;
}
};
// Recursive reverse for Doubly Linked List
Node* reverseRecursive(Node* head) {
if (head == NULL)
return NULL;
Node* temp = head->next;
// Swap next and prev
head->next = head->prev;
head->prev = temp;
// If prev becomes NULL → new head
if (head->prev == NULL)
return head;
return reverseRecursive(head->prev);
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " <-> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = new Node(10);
Node* second = new Node(20);
Node* third = new Node(30);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;
cout << "Original List:" << endl;
printList(head);
head = reverseRecursive(head);
cout << "Reversed List:" << endl;
printList(head);
return 0;
}Output
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
Java Implementation
class Node {
int data;
Node prev;
Node next;
Node(int val) {
data = val;
prev = null;
next = null;
}
}
public class Main {
// Recursive reverse function
static Node reverseRecursive(Node head) {
if (head == null)
return null;
Node temp = head.next;
// Swap next and prev
head.next = head.prev;
head.prev = temp;
// If prev becomes NULL → new head
if (head.prev == null)
return head;
return reverseRecursive(head.prev);
}
// Print list
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " <-> ");
head = head.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
// Create list: 10 <-> 20 <-> 30
Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.prev = head;
second.next = third;
third.prev = second;
System.out.println("Original List:");
printList(head);
head = reverseRecursive(head);
System.out.println("Reversed List:");
printList(head);
}
}Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Recursive reverse function
def reverse_recursive(head):
if head is None:
return None
temp = head.next
# Swap next and prev
head.next = head.prev
head.prev = temp
# If prev becomes None → new head
if head.prev is None:
return head
return reverse_recursive(head.prev)
# Print list
def print_list(head):
while head is not None:
print(head.data, end=" <-> ")
head = head.next
print("NULL")
# Main
if __name__ == "__main__":
# Create list: 10 <-> 20 <-> 30
head = Node(10)
second = Node(20)
third = Node(30)
head.next = second
second.prev = head
second.next = third
third.prev = second
print("Original List:")
print_list(head)
head = reverse_recursive(head)
print("Reversed List:")
print_list(head)Output remains:
Original List:
10 <-> 20 <-> 30 <-> NULL
Reversed List:
30 <-> 20 <-> 10 <-> NULL
Final Comparison
| Approach | Time | Space | Preferred |
|---|---|---|---|
| Iterative | O(n) | O(1) | Yes |
| Recursive | O(n) | O(n) | Learning |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
