Reverse a Doubly Linked List in DSA Go - Deep Dive

Overview - Reverse a Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node points to both its previous and next node. Reversing it means changing the direction so the last node becomes the first, and all links flip accordingly. This operation rearranges the list without creating new nodes. It helps us traverse the list backward easily after reversal.

Why it matters

Reversing a doubly linked list is important because it allows us to change the order of data efficiently without extra memory. Without this, we would need to create a new list or copy data, which wastes time and space. Many real-world problems like undo features, navigation history, or playlist shuffling rely on reversing linked structures quickly.

Where it fits

Before learning this, you should understand what a doubly linked list is and how to traverse it. After mastering reversal, you can explore more complex linked list operations like sorting, merging, or implementing advanced data structures like deques or LRU caches.

Mental Model

Core Idea

Reversing a doubly linked list means swapping each node's previous and next pointers, then updating the head to the last node.

Think of it like...

Imagine a two-way street where cars can go forward or backward. Reversing the list is like flipping the street signs so all cars must drive in the opposite direction.

Original list:
Head -> [Prev: nil | Data: 1 | Next: 2] <-> [Prev: 1 | Data: 2 | Next: 3] <-> [Prev: 2 | Data: 3 | Next: nil] -> nil

After reversal:
Head -> [Prev: nil | Data: 3 | Next: 2] <-> [Prev: 3 | Data: 2 | Next: 1] <-> [Prev: 2 | Data: 1 | Next: nil] -> nil

Build-Up - 7 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn what a doubly linked list node contains and how nodes connect.

A doubly linked list node has three parts: data, a pointer to the previous node, and a pointer to the next node. The list starts at a head node and ends at a node whose next pointer is nil. You can move forward using next pointers or backward using previous pointers.

Result

You can traverse the list in both directions, accessing all nodes from head to tail or tail to head.

Knowing the two-way links is essential because reversing depends on swapping these pointers correctly.

2

Foundation

Traversing a Doubly Linked List

Concept: Practice moving through the list forward and backward.

Start at the head node. Follow the next pointers to move forward until you reach nil. To move backward, start at the tail node and follow previous pointers until nil. This confirms the list's bidirectional nature.

Result

You can print or access all nodes in order and reverse order.

Understanding traversal directions helps visualize what reversal will change.

3

Intermediate

Swapping Previous and Next Pointers

🤔Before reading on: do you think swapping pointers node-by-node or rearranging links all at once is easier? Commit to your answer.

Concept: Reversal is done by swapping each node's previous and next pointers individually.

For each node, swap its previous and next pointers. This means what was previously the next node becomes the previous, and vice versa. Move through the list using the original next pointer before swapping to avoid losing track.

Result

Each node's direction flips, but the list is not yet connected correctly until the head is updated.

Swapping pointers in place avoids extra memory and keeps the list structure intact during reversal.

4

Intermediate

Updating the Head After Reversal

🤔Before reading on: after swapping pointers, should the head be the original head or the original tail? Commit to your answer.

Concept: After swapping pointers, the head pointer must be updated to the last node processed.

While swapping pointers, keep track of the current node. When you reach the end (nil), the last non-nil node is the new head. Assign the list's head pointer to this node to complete reversal.

Result

The list's head now points to the original tail, making traversal start from the reversed order.

Updating the head is crucial; otherwise, the list appears broken or empty after reversal.

5

Intermediate

Implementing Reversal in Go Code

🤔Before reading on: do you think the reversal function should return the new head or modify the list in place? Commit to your answer.

Concept: Write a Go function that reverses the doubly linked list by swapping pointers and updating the head.

Define a Node struct with Prev, Data, and Next fields. Traverse the list from head, swap Prev and Next for each node, and update head to the last node processed. The function modifies the list in place and returns the new head.

Result

The list is reversed, and the new head points to the original tail node.

Implementing reversal in code solidifies understanding and shows practical application.

6

Advanced

Handling Edge Cases in Reversal

🤔Before reading on: do you think reversing an empty or single-node list changes it? Commit to your answer.

Concept: Consider what happens when the list is empty or has only one node.

If the list is empty (head is nil), reversal does nothing. If there is only one node, swapping pointers has no effect since Prev and Next are nil. The function should handle these cases gracefully without errors.

Result

Reversal returns the same list unchanged for empty or single-node lists.

Handling edge cases prevents runtime errors and ensures robustness.

7

Expert

Optimizing Reversal for Performance

🤔Before reading on: do you think reversal can be done faster than O(n) time? Commit to your answer.

Concept: Reversal must visit each node once, so it runs in linear time. Optimizations focus on minimizing pointer operations and avoiding extra memory.

The reversal algorithm swaps pointers in one pass, using constant extra space. Avoiding temporary variables or multiple traversals improves speed. In concurrent environments, locking may be needed to prevent data races.

Result

Reversal runs efficiently in O(n) time and O(1) space, suitable for large lists.

Understanding time and space complexity helps write scalable and efficient code.

Under the Hood

Each node in a doubly linked list stores two pointers: one to the previous node and one to the next. Reversing swaps these pointers for every node. Internally, this changes the direction of links. The head pointer is updated to the last node processed, which was originally the tail. This in-place pointer swapping avoids creating new nodes or copying data, making reversal memory efficient.

Why designed this way?

Doubly linked lists were designed to allow easy forward and backward traversal. Reversal by swapping pointers leverages this bidirectional nature without extra memory. Alternatives like creating a new reversed list waste space and time. This method is simple, fast, and fits well with pointer-based data structures common in low-level languages like Go.

Start:
Head -> [Prev: nil | Data: 1 | Next: 2] <-> [Prev: 1 | Data: 2 | Next: 3] <-> [Prev: 2 | Data: 3 | Next: nil]

Process each node:
For node with Data=1: swap Prev and Next -> Prev: 2, Next: nil
For node with Data=2: swap Prev and Next -> Prev: 3, Next: 1
For node with Data=3: swap Prev and Next -> Prev: nil, Next: 2

End:
Head -> [Prev: nil | Data: 3 | Next: 2] <-> [Prev: 3 | Data: 2 | Next: 1] <-> [Prev: 2 | Data: 1 | Next: nil]

Myth Busters - 4 Common Misconceptions

Quick: Does reversing a doubly linked list require creating new nodes? Commit yes or no.

Common Belief: Reversing means making a new list with nodes in reverse order.

Reality: Reversal swaps pointers in existing nodes without creating new nodes.

Why it matters: Creating new nodes wastes memory and time, making reversal inefficient.

Quick: After reversal, is the original head still the head? Commit yes or no.

Common Belief: The head node remains the same after reversal.

Reality: The head becomes the original tail node after reversal.

Why it matters: Failing to update the head pointer breaks list traversal and causes bugs.

Quick: Can you reverse a doubly linked list by only swapping next pointers? Commit yes or no.

Common Belief: Swapping only next pointers is enough to reverse the list.

Reality: Both previous and next pointers must be swapped to maintain correct links.

Why it matters: Swapping only one pointer breaks backward traversal and corrupts the list.

Quick: Does reversing a single-node list change it? Commit yes or no.

Common Belief: Reversing a single-node list changes its structure.

Reality: A single-node list remains the same after reversal.

Why it matters: Misunderstanding this leads to unnecessary code complexity and bugs.

Expert Zone

1

Swapping pointers in place requires careful order of operations to avoid losing track of nodes during traversal.

2

In concurrent programs, reversing a doubly linked list needs synchronization to prevent data races and inconsistent states.

3

Memory alignment and cache locality can affect reversal performance in large lists, influencing pointer access speed.

When NOT to use

Reversal is not suitable when the list is immutable or shared across threads without locks. In such cases, creating a new reversed list or using persistent data structures is better. Also, for singly linked lists, reversal requires a different approach since there is no previous pointer.

Production Patterns

Reversal is used in undo-redo stacks, browser history navigation, playlist shuffling, and bidirectional iterators. In databases, doubly linked lists reversed help in reverse scans. Efficient in-place reversal is critical in embedded systems with limited memory.

Connections

Singly Linked List Reversal

Related operation but simpler structure with only next pointers.

Understanding doubly linked list reversal clarifies the added complexity and benefits of having previous pointers.

Undo-Redo Mechanism in Software

Uses doubly linked lists to move backward and forward through states.

Knowing how to reverse doubly linked lists helps implement efficient undo-redo features by changing traversal direction.

Bidirectional Navigation in Web Browsers

Browser history is often a doubly linked list allowing forward and backward navigation.

Reversing such lists can simulate flipping navigation order or resetting history direction.

Common Pitfalls

#1 Losing track of nodes by swapping pointers without saving the next node first.

Wrong approach:

for current := head; current != nil; current = current.Next {
current.Prev, current.Next = current.Next, current.Prev
}

Correct approach:

for current := head; current != nil; {
next := current.Next
current.Prev, current.Next = current.Next, current.Prev
current = next
}

Root cause:

Not saving the next node before swapping causes traversal to fail because pointers change mid-loop.

#2 Not updating the head pointer after reversal.

Wrong approach:

func reverse(head *Node) *Node {
// swap pointers but do not update head
return head
}

Correct approach:

func reverse(head *Node) *Node {
var current = head
var newHead *Node
for current != nil {
current.Prev, current.Next = current.Next, current.Prev
newHead = current
current = current.Prev
}
return newHead
}

Root cause:

Forgetting to assign the new head breaks list access after reversal.

#3 Attempting to reverse an empty list without checking for nil.

Wrong approach:

func reverse(head *Node) *Node {
current := head
for current != nil {
current.Prev, current.Next = current.Next, current.Prev
current = current.Prev
}
return head
}

Correct approach:

func reverse(head *Node) *Node {
if head == nil {
return nil
}
current := head
var newHead *Node
for current != nil {
current.Prev, current.Next = current.Next, current.Prev
newHead = current
current = current.Prev
}
return newHead
}

Root cause:

Not handling nil head can cause runtime errors or incorrect results.

Key Takeaways

Reversing a doubly linked list swaps each node's previous and next pointers and updates the head to the original tail.

This operation is done in place without creating new nodes, making it memory efficient.

Handling edge cases like empty or single-node lists ensures robustness.

Failing to update the head or losing track of nodes during pointer swaps are common mistakes.

Understanding reversal deepens knowledge of pointer manipulation and bidirectional data structures.

Practice

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

easy

A. To sort the list in ascending order

B. To delete all nodes from the list

C. To make the last node the first and the first node the last

D. To add a new node at the end

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.

2. Step 2: Define reversing operation

   Reversing means swapping the previous and next pointers for all nodes, so the last node becomes the first.

3. Final Answer:

   To make the last node the first and the first node the last -> Option C

4. Quick Check:

   Reverse = swap previous and next pointers [OK]

Hint: Reversing swaps next and previous pointers [OK]

Common Mistakes:

• Confusing reversing with sorting
• Thinking reversing deletes nodes
• Assuming reversing adds nodes

2. Which of the following Go code snippets correctly swaps the next and prev pointers of a node curr in a doubly linked list?

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 multiple assignment in Go

   Go allows swapping two variables in one line using multiple assignment.

2. Step 2: Identify correct swap syntax

   The correct way to swap is curr.next, curr.prev = curr.prev, curr.next which exchanges the values.

3. Final Answer:

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

4. Quick Check:

   Swap pointers with multiple assignment [OK]

Hint: Use Go's multiple assignment to swap pointers [OK]

Common Mistakes:

• Assigning one pointer twice without swapping
• Using separate lines causing overwrite
• Not swapping pointers at all

3. Given the following Go code to reverse a doubly linked list, what will be the printed output after reversal?

type Node struct {
    data int
    prev *Node
    next *Node
}

func reverse(head *Node) *Node {
    var temp *Node
    curr := head
    for curr != nil {
        temp = curr.prev
        curr.prev = curr.next
        curr.next = temp
        curr = curr.prev
    }
    if temp != nil {
        head = temp.prev
    }
    return head
}

// List before reversal: 1 <-> 2 <-> 3 <-> nil
// After reversal, print from new head
func printList(head *Node) {
    curr := head
    for curr != nil {
        fmt.Print(curr.data, " <-> ")
        curr = curr.next
    }
    fmt.Println("nil")
}

medium

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

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

C. nil

D. 1 <-> nil

Solution

1. Step 1: Trace pointer swaps in the loop

   Each node swaps its prev and next pointers, moving curr to original next node via curr.prev after swap.

2. Step 2: Update head to last processed node

   After loop, head is set to temp.prev which points to the new first node (original last node).

3. Final Answer:

   3 <-> 2 <-> 1 <-> nil -> Option B

4. Quick Check:

   Reversed list prints nodes in reverse order [OK]

Hint: Reversed list prints nodes backward [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing prev and next pointers
• Printing original list without reversal

4. Identify the bug in this Go function that attempts to reverse a doubly linked list:

func reverse(head *Node) *Node {
    curr := head
    for curr != nil {
        curr.prev, curr.next = curr.next, curr.prev
        curr = curr.next
    }
    return head
}

medium

A. The loop moves curr to curr.next instead of curr.prev after swapping

B. The pointers are not swapped correctly

C. The function does not return the new head

D. The function deletes nodes accidentally

Solution

1. Step 1: Analyze pointer swapping and traversal

   The pointers are swapped correctly, but after swapping, curr.next points to the previous node, so moving curr to curr.next moves backward.

2. Step 2: Identify correct traversal direction

   After swapping, curr should move to curr.prev (original next) to continue forward traversal.

3. Final Answer:

   The loop moves curr to curr.next instead of curr.prev after swapping -> Option A

4. Quick Check:

   Traverse using curr.prev after swap [OK]

Hint: After swap, move curr to curr.prev, not curr.next [OK]

Common Mistakes:

• Moving curr in wrong direction after swap
• Not updating head to new first node
• Swapping pointers incorrectly

5. You have a doubly linked list with nodes containing integers. After reversing it using the standard pointer swap method, you want to find the sum of all nodes at even positions (2nd, 4th, etc.) in the reversed list. Which approach correctly combines reversal and summation?

hard

A. Sum all nodes without reversal

B. Sum nodes at even positions before reversal, then reverse the list

C. Reverse the list and sum nodes at odd positions instead

D. First reverse the list, then traverse from new head summing nodes at even positions

Solution

1. Step 1: Reverse the doubly linked list

   Use pointer swapping to reverse the list so the order is changed.

2. Step 2: Traverse from new head and sum nodes at even positions

   After reversal, positions change, so summing even positions requires traversal from new head counting nodes.

3. Final Answer:

   First reverse the list, then traverse from new head summing nodes at even positions -> Option D

4. Quick Check:

   Reverse first, then sum even positions [OK]

Hint: Reverse first, then sum nodes by position [OK]

Common Mistakes:

• Summing before reversal causing wrong positions
• Summing odd positions instead of even
• Ignoring reversal effect on node order