WikiGalaxy
Reverse a Doubly Linked List
Concept Overview:
A Doubly Linked List (DLL) is a complex data structure where each node contains pointers to both the next and previous nodes. Reversing a DLL involves swapping the previous and next pointers for each node, effectively reversing the direction of the list.
Step 1: Start at the head of the list.
[Head] <-> [Node1] <-> [Node2] <-> [Node3] <-> [Tail]
Step 2: Swap the next and previous pointers for each node.
[Head] <-> [Node1] <-> [Node2] <-> [Node3] <-> [Tail]
Step 3: Continue until all nodes are reversed.
[Tail] <-> [Node3] <-> [Node2] <-> [Node1] <-> [Head]
Step 4: Update the head to be the last processed node.
[New Head] <-> [Node3] <-> [Node2] <-> [Node1] <-> [Old Head]
class Node {
int data;
Node next;
Node prev;
Node(int d) { data = d; }
}
class DoublyLinkedList {
Node head;
void reverse() {
Node temp = null;
Node current = head;
// Swap next and prev for all nodes
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
// Before changing head, check for the cases like empty list
// and list with only one node
if (temp != null) {
head = temp.prev;
}
}
}
Detailed Explanation:
The algorithm starts at the head of the list and iteratively swaps the next and previous pointers of each node. Once all nodes have been processed, the head of the list is updated to the last node encountered, which is the new head of the reversed list.
Console Output:
Reversed List: [Tail] <-> [Node3] <-> [Node2] <-> [Node1] <-> [Head]
Key Points:
1. The reversal process involves iterating through the list and swapping the next and prev pointers for each node.
2. Care must be taken to handle edge cases such as empty lists or lists with a single node.
3. The algorithm runs in O(n) time complexity, where n is the number of nodes in the list.
