A doubly linked list is a common data structure used in computer science and programming interviews, including many problems on platforms like LeetCode. Unlike a singly linked list, each node in a doubly linked list contains pointers to both its previous and next nodes, allowing traversal in both directions. One of the popular interview challenges involving this structure is to reverse a doubly linked list. Understanding how to reverse it helps improve your grasp of pointers, memory references, and linked list manipulation, all of which are key concepts in data structure and algorithm design.
Understanding the Structure of a Doubly Linked List
Before diving into the reversal process, it’s important to understand how a doubly linked list works. Each node has three main parts
- DataThe value stored in the node.
- Next pointerA reference to the next node in the list.
- Previous pointerA reference to the previous node in the list.
This structure allows easy traversal in both forward and backward directions. The first node, called the head, has its previous pointer set tonull, while the last node, called the tail, has its next pointer set tonull. This bidirectional connection is what distinguishes a doubly linked list from a singly linked one.
Why Reverse a Doubly Linked List?
Reversing a doubly linked list is a classic operation often asked in coding interviews. The problem tests your ability to manipulate pointers efficiently. It’s not only about flipping the order of nodes but also ensuring that every link between them remains consistent and valid after the reversal. In real-world applications, reversing a list can be used for operations such as undo mechanisms, data reordering, or implementing certain algorithms that require backward traversal.
Problem Statement from LeetCode
The typical LeetCode problem statement for reversing a doubly linked list goes like this
Given the head of a doubly linked list, reverse the list and return the head of the reversed list.
This means you need to take the given list, manipulate the pointers, and make sure that after reversal, the head points to the last original node, and the next and previous pointers are swapped properly throughout the list.
Example
Let’s consider a simple example of a doubly linked list
Original list 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5
After reversing the list, it should look like this
Reversed list 5 ⇄ 4 ⇄ 3 ⇄ 2 ⇄ 1
Notice how both the order of elements and the direction of the pointers have changed. Each node’snextandprevpointers are swapped.
Approach to Solve the Problem
Step 1 Traverse the List
Start from the head of the list and iterate through each node. During each iteration, you’ll need to swap thenextandprevpointers for the current node.
Step 2 Swap Pointers
For each node, perform the following operations
temp = node.prev node.prev = node.next node.next = tempThis effectively reverses the direction of the pointers. After swapping, you move to what was previously the previous node, which is now stored innode.prev.
Step 3 Update the Head
When the traversal is complete, theheadof the reversed list should point to the last node of the original list. You can detect the new head because, at the end of the loop,node.prevwill benull.
Code Implementation
Here’s a simple implementation in Python that demonstrates how to reverse a doubly linked list
class Node def __init__(self, data) self.data = data self.next = None self.prev = None def reverseDoublyLinkedList(head) current = head temp = None 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 headThis code works by iterating through each node, swapping itsprevandnextpointers, and then moving to the next node, which is now accessible throughcurrent.prev. Once the traversal is done,temp.prevpoints to the new head of the reversed list.
Time and Space Complexity
The time complexity of reversing a doubly linked list isO(n), wherenis the number of nodes in the list. This is because we visit each node exactly once. The space complexity isO(1), as we only use a constant amount of extra space (a few temporary variables) to perform the reversal.
Common Mistakes and Pitfalls
- Forgetting to update the head pointer after the reversal.
- Incorrectly swapping
nextandprevpointers, which can cause circular references or broken links. - Not handling empty lists or lists with a single node properly.
Always test your code with edge cases such as
- An empty list (head is
null). - A list with only one node.
- A list with multiple nodes.
Testing the Function
To confirm that your implementation works, you can create a small test setup that constructs a doubly linked list, prints it before and after reversal, and checks whether the pointers are correctly updated.
def printList(head) current = head while current print(current.data, end= ) current = current.next print() # Example usage head = Node(1) node2 = Node(2) node3 = Node(3) head.next = node2 node2.prev = head node2.next = node3 node3.prev = node2 print(Original List) printList(head) head = reverseDoublyLinkedList(head) print(Reversed List) printList(head)Running this will display the original and reversed lists, allowing you to verify the correctness of your function.
Alternative Methods
While the iterative approach is the most common and efficient, there are other ways to reverse a doubly linked list. For instance, you can use recursion, though it’s generally less memory-efficient because it adds function calls to the call stack. However, understanding multiple approaches helps in strengthening your algorithmic thinking.
Practical Applications
Reversing a doubly linked list might seem like an academic exercise, but it has practical relevance. Many real-world programs, especially those involving data navigation like music playlists, undo-redo systems, and navigation history in web browsers, internally rely on doubly linked lists. The ability to reverse or traverse backward efficiently makes this data structure useful for such scenarios.
Reversing a doubly linked list is a fundamental yet insightful coding exercise that appears frequently in LeetCode problems and technical interviews. It tests your understanding of pointer manipulation and helps you gain confidence in working with linked data structures. By practicing this problem, you also build a solid foundation for more advanced linked list algorithms such as merging, sorting, and detecting cycles. Once you grasp this concept, similar problems become much easier to handle in future coding challenges.