Reversing a doubly linked list involves swapping the next and prev pointers of every node so that the list can be traversed in the opposite direction. This operation is useful in scenarios where backward traversal is needed or when implementing certain algorithms that require reversed lists. Mastering this operation strengthens your understanding of pointer manipulation in doubly linked lists.
Understanding the Problem
The challenge in reversing a doubly linked list lies in correctly swapping each node’s next and prev pointers without losing access to the remaining nodes. After reversal, the head of the list must point to the last node of the original list. Edge cases, such as an empty list or a list with only one node, must be handled properly.
Program 1: Reverse a Doubly Linked List (Iterative Approach)
This program demonstrates how to reverse a doubly linked list in place. It traverses each node, swaps the next and prev pointers, and updates the head to the new first node.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert node at end
void insertAtEnd(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
if (!head) {
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Display backward
void displayBackward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
while (temp->next) temp = temp->next; // Go to last node
printf("Backward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
// Reverse the doubly linked list
void reverseList() {
Node *temp = NULL;
Node *current = head;
while (current) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev; // move to next node (originally prev)
}
if (temp) head = temp->prev; // update head to last node
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
printf("Original List:\n");
displayForward();
displayBackward();
reverseList();
printf("Reversed List:\n");
displayForward();
displayBackward();
return 0;
}This program efficiently reverses the list by swapping pointers without using extra memory. Forward and backward display functions confirm that the list has been reversed correctly.
Program 2: Reverse a Doubly Linked List (Recursive Approach)
This program uses recursion to reverse a doubly linked list. At each recursive call, it swaps the next and prev pointers, and finally updates the head pointer when the recursion reaches the end.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node *head = NULL;
// Insert node at end
void insertAtEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = NULL;
if (!head) {
head = newNode;
return;
}
Node *temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Display forward
void displayForward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
printf("Forward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Display backward
void displayBackward() {
if (!head) {
printf("Doubly Linked List is empty\n");
return;
}
Node *temp = head;
while (temp->next) temp = temp->next; // go to last node
printf("Backward: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\n");
}
// Reverse recursively (no helper)
void reverseListRecursive(Node *current) {
if (!current) return;
// Swap next and prev
Node *temp = current->prev;
current->prev = current->next;
current->next = temp;
// If this is the last node, update head
if (!current->prev) {
head = current;
return;
}
// Recurse with the next node (which is current->prev now)
reverseListRecursive(current->prev);
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);
printf("Original List:\n");
displayForward();
displayBackward();
reverseListRecursive(head);
printf("Reversed List (Recursive):\n");
displayForward();
displayBackward();
return 0;
}This recursive version achieves the same result as the iterative one but relies on function calls instead of loops. It is elegant and demonstrates the power of recursion with careful pointer management.
FAQs
Q1: What is the time complexity of reversing a doubly linked list?
O(n), because each node is visited exactly once.
Q2: Is extra memory required to reverse the list?
No, the reversal is done in place, so space complexity is O(1).
Q3: Can an empty list be reversed?
Yes, the function safely exits if the list is empty.
Q4: Can this approach be used for singly linked lists?
No, singly linked lists require a different method because there is no prev pointer.
Conclusion
Reversing a doubly linked list is a key operation that involves careful manipulation of next and prev pointers. By swapping these pointers for each node and updating the head, the list can be reversed efficiently in place. Mastering this technique is essential for handling complex list operations.
References & Additional Resources
The following books and online resources provide both theoretical foundations and practical examples to help you understand more on the topic.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, critical for linked list operations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of linked lists, dynamic memory allocation, and related algorithms.
- GeeksforGeeks: Doubly Linked List in C – Introduction to concepts, structure, and implementation details of doubly linked lists.
- GeeksforGeeks: Reverse a Doubly Linked List – Step-by-step explanation of reversing operations in a doubly linked list.
- Programiz: Data Structures – Doubly Linked List – Beginner-friendly guide with clear examples for insertion and deletion.
- Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of
malloc(),calloc(),realloc(), andfree()functions for memory management. - C Standard Library Documentation – Memory Management – Official reference for memory allocation and deallocation functions in C.
