Why Reverse a Doubly Linked List in DSA Python?

The Big Idea

What if you could flip a chain of data links in one smooth move instead of untangling each link by hand?

The Scenario

Imagine you have a paper chain made of linked rings. You want to flip the order of the rings so the last one becomes first and the first one becomes last.

Doing this by hand means unhooking each ring and reattaching it in reverse order. It's slow and easy to make mistakes.

The Problem

Manually reversing a chain of rings is tiring and error-prone. You might lose track of which ring goes where or accidentally break the chain.

Similarly, manually reversing a doubly linked list by moving each node one by one is slow and confusing because you must carefully update two links per node.

The Solution

Reversing a doubly linked list swaps the links in one pass. Each node's next and previous pointers are swapped, flipping the list efficiently without breaking it.

This method is fast, clean, and safe, like flipping the whole chain at once instead of unhooking rings.

Before vs After

✗ Before

current = head
reversed_list = None
while current:
    # manually detach and reattach nodes
    current = current.next

✓ After

current = head
while current:
    current.next, current.prev = current.prev, current.next
    head = current
    current = current.prev

What It Enables

This lets you quickly reverse the order of data in a list, enabling easy backward traversal and new ways to process information.

Real Life Example

Think of a music playlist where you want to play songs in reverse order without creating a new list. Reversing the doubly linked list of songs lets you do this instantly.

Key Takeaways

Manual reversal is slow and error-prone.

Swapping next and prev pointers reverses the list efficiently.

Enables quick backward traversal and flexible data processing.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To change the direction of traversal so the last node becomes the first

B. To delete all nodes from the list

C. To sort the nodes in ascending order

D. To convert it into a singly linked list

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes with pointers to both previous and next nodes, allowing traversal in both directions.

2. Step 2: Purpose of reversing

   Reversing swaps the previous and next pointers of each node, making the last node the new head and changing traversal direction.

3. Final Answer:

   To change the direction of traversal so the last node becomes the first -> Option A

4. Quick Check:

   Reversing swaps pointers to reverse traversal [OK]

Hint: Reversing swaps previous and next pointers [OK]

Common Mistakes:

• Thinking reversing deletes nodes
• Confusing reversing with sorting
• Assuming it converts to singly linked list

2. Which of the following is the correct way to swap the next and prev pointers of a node curr in Python?

easy

A. curr.next = curr.prev; curr.prev = curr.next

B. curr.next, curr.prev = curr.prev, curr.next

C. curr.prev = curr.next; curr.next = curr.prev

D. curr.next = curr.next; curr.prev = curr.prev

Solution

1. Step 1: Understand Python tuple unpacking

   Using a, b = b, a swaps values of a and b simultaneously without temporary variable.

2. Step 2: Apply to pointers

   Swapping curr.next and curr.prev correctly uses curr.next, curr.prev = curr.prev, curr.next.

3. Final Answer:

   curr.next, curr.prev = curr.prev, curr.next -> Option B

4. Quick Check:

   Tuple unpacking swaps pointers correctly [OK]

Hint: Use tuple unpacking to swap pointers in one line [OK]

Common Mistakes:

• Assigning sequentially causing both to be same
• Not swapping both pointers
• Using incorrect order in assignment

3. Given the doubly linked list: 1 <-> 2 <-> 3 <-> null, what will be the list after reversing it using the standard reverse algorithm?

medium

A. 3 <-> 2 <-> 1 <-> null

B. 1 <-> 2 <-> 3 <-> null

C. null <-> 3 <-> 2 <-> 1

D. 3 -> 2 -> 1 -> null (singly linked list)

Solution

1. Step 1: Original list traversal

   The list is 1 <-> 2 <-> 3 <-> null, head at 1, tail at 3.

2. Step 2: Reverse pointers

   Swapping next and prev pointers reverses the list, making 3 the new head and 1 the new tail.

3. Final Answer:

   3 <-> 2 <-> 1 <-> null -> Option A

4. Quick Check:

   Reversed list order is 3, 2, 1 [OK]

Hint: Reversed list order is original tail to head [OK]

Common Mistakes:

• Confusing original order with reversed
• Misplacing null pointer
• Assuming singly linked list after reverse

4. What is the error in this code snippet for reversing a doubly linked list?

def reverse(head):
    curr = head
    while curr:
        curr.next = curr.prev
        curr.prev = curr.next
        curr = curr.prev
    return head

medium

A. The code correctly reverses the list

B. The loop condition should be while curr.next

C. Pointers are not swapped simultaneously causing incorrect links

D. The function should return curr instead of head

Solution

1. Step 1: Analyze pointer swapping

   Assigning curr.next = curr.prev then curr.prev = curr.next sequentially overwrites curr.next before using it, losing original value.

2. Step 2: Effect on traversal

   Because pointers are not swapped simultaneously, traversal using curr = curr.prev fails and links become incorrect.

3. Final Answer:

   Pointers are not swapped simultaneously causing incorrect links -> Option C

4. Quick Check:

   Swap pointers simultaneously to avoid overwriting [OK]

Hint: Swap pointers in one line to avoid overwriting [OK]

Common Mistakes:

• Swapping pointers in two separate assignments
• Returning old head instead of new head
• Incorrect loop condition

5. You have a doubly linked list with nodes containing integer values. After reversing it, you want to print the list from the new head to the end. Which of the following code snippets correctly prints the reversed list?

hard

A. curr = reversed_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.prev
print('null')

B. curr = reversed_head
while curr.prev:
print(curr.data, end=' <-> ')
curr = curr.prev
print('null')

C. curr = original_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.next
print('null')

D. curr = reversed_head
while curr:
print(curr.data, end=' <-> ')
curr = curr.next
print('null')

Solution

1. Step 1: Identify traversal direction after reversing

   After reversing, the new head points to the start of the reversed list, and traversal should use next pointers to move forward.

2. Step 2: Correct printing loop

   Starting from reversed_head, printing curr.data and moving with curr = curr.next prints the list in correct order until curr is null.

3. Final Answer:

   curr = reversed_head while curr: print(curr.data, end=' <-> ') curr = curr.next print('null') -> Option D

4. Quick Check:

   Traverse reversed list using next pointers from new head [OK]

Hint: Print using next pointers from new head after reverse [OK]

Common Mistakes:

• Using prev pointer to traverse forward
• Starting from original head after reverse
• Loop condition stopping early