Reverse a Doubly Linked List in DSA Python - Build from Scratch

Reverse a Doubly Linked List

📖 Scenario: You are working on a music playlist app. The playlist is stored as a doubly linked list where each node contains a song name. You want to add a feature to reverse the order of songs in the playlist.

🎯 Goal: Build a program that creates a doubly linked list of songs, then reverses the list, and finally prints the reversed playlist.

📋 What You'll Learn

Create a doubly linked list with exactly these songs in order: 'Song1', 'Song2', 'Song3', 'Song4'

Create a variable called head that points to the first node of the doubly linked list

Write a function called reverse_doubly_linked_list(head) that reverses the doubly linked list and returns the new head

Print the reversed doubly linked list in the format: Song4 <-> Song3 <-> Song2 <-> Song1 <-> None

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps where you need to move forward and backward through items efficiently.

💼 Career

Understanding linked lists and how to reverse them is a common interview question and helps build strong problem-solving skills in data structures.

1

Create the doubly linked list with songs

Create a class called Node with attributes data, prev, and next. Then create four nodes with data 'Song1', 'Song2', 'Song3', and 'Song4'. Link them to form a doubly linked list. Finally, create a variable called head that points to the first node.

DSA Python

# Define Node class and create doubly linked list nodes
# Your code here

Hint

Remember to link each node's next and prev attributes to form the doubly linked list.

2

Create a function to reverse the doubly linked list

Define a function called reverse_doubly_linked_list(head) that takes the head of the doubly linked list and reverses the list by swapping the next and prev pointers of each node. The function should return the new head of the reversed list.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')
node4 = Node('Song4')

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3

head = node1

# Define reverse_doubly_linked_list function below
# Your code here

Hint

Swap the prev and next pointers for each node. Move to the original next node by using the updated prev pointer.

3

Reverse the doubly linked list using the function

Call the function reverse_doubly_linked_list(head) and assign its result back to the variable head to update the head to the new reversed list.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')
node4 = Node('Song4')

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3

head = node1

def reverse_doubly_linked_list(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 head

# Call reverse_doubly_linked_list and update head
# Your code here

Hint

Assign the result of reverse_doubly_linked_list(head) back to head.

4

Print the reversed doubly linked list

Write a loop to print the reversed doubly linked list starting from head. Print each node's data followed by ' <-> ' and end with 'None'. The output should look like: Song4 <-> Song3 <-> Song2 <-> Song1 <-> None

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

node1 = Node('Song1')
node2 = Node('Song2')
node3 = Node('Song3')
node4 = Node('Song4')

node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3

head = node1

def reverse_doubly_linked_list(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 head

head = reverse_doubly_linked_list(head)

# Print the reversed doubly linked list
# Your code here

Hint

Use a while loop to traverse from head and print each node's data followed by ' <-> '. End with printing 'None'.

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