Reverse a Doubly Linked List in DSA Typescript - 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 order so the last node becomes the first, and the first becomes the last. This involves swapping the previous and next links for every node. The goal is to traverse the list backward easily after reversal.

Why it matters

Reversing a doubly linked list is a common operation in many programs that need to process data in reverse order efficiently. Without this, reversing data would require extra memory or slow operations. It helps in undo features, navigation systems, and more. Without it, many applications would be less efficient or more complex.

Where it fits

Before learning this, you should understand what a doubly linked list is and how to traverse it. After this, you can learn about more complex linked list operations like sorting, merging, or working with circular doubly linked lists.

Mental Model

Core Idea

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

Think of it like...

Imagine walking down a hallway with doors on both sides. Reversing the list is like turning around and walking back the same way, swapping which door you enter first and last.

Original List:
Head -> [Prev: null | Data | Next] <-> [Prev | Data | Next] <-> ... <-> [Prev | Data | Next: null] <- Tail

After Reversal:
New Head -> [Prev: null | Data | Next] <-> [Prev | Data | Next] <-> ... <-> [Prev | Data | Next: null] <- New Tail

Each node's Prev and Next pointers are swapped.

Build-Up - 6 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 with a head node whose previous pointer is null and ends with a tail node whose next pointer is null. Traversing forward uses next pointers; backward uses previous pointers.

Result

You can visualize and traverse the list from head to tail and tail to head.

Knowing the node structure is essential because reversing means changing these pointers carefully without losing track of nodes.

2

Foundation

Traversing a Doubly Linked List

Concept: Learn how to move through the list forward and backward.

Starting at the head, follow the next pointers to visit each node until you reach null. Similarly, starting at the tail, follow previous pointers backward. This shows the list's double direction nature.

Result

You can visit all nodes in order and reverse order.

Understanding traversal directions helps you see why swapping pointers reverses the list.

3

Intermediate

Swapping Previous and Next Pointers

🤔Before reading on: Do you think swapping pointers in place or creating new nodes is better for reversing? Commit to your answer.

Concept: The key step is to swap each node's previous and next pointers to reverse the direction.

For each node, temporarily store its next pointer. Then set its next pointer to its previous pointer, and its previous pointer to the stored next pointer. Move to the original next node (stored before swapping) and repeat until all nodes are processed.

Result

All nodes have their previous and next pointers swapped, reversing the list's direction.

Swapping pointers in place is efficient and avoids extra memory, but requires careful temporary storage to avoid losing links.

4

Intermediate

Updating the Head Pointer After Reversal

🤔Before reading on: After swapping pointers, should the head remain the same or change? Commit to your answer.

Concept: After reversing pointers, the original tail becomes the new head, so update the head pointer accordingly.

While swapping pointers, keep track of the last processed node. After the loop ends, set the list's head pointer to this node, which is the new start of the reversed list.

Result

The list's head points to the new first node, completing the reversal.

Updating the head is crucial; otherwise, the list would appear empty or incorrect after reversal.

5

Advanced

Implementing Reverse in TypeScript

🤔Before reading on: Do you think reversing modifies the list in place or returns a new list? Commit to your answer.

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

class Node { data: number; prev: Node | null; next: Node | null; constructor(data: number) { this.data = data; this.prev = null; this.next = null; } } class DoublyLinkedList { head: Node | null = null; reverse(): void { let current = this.head; let temp: Node | null = null; while (current !== null) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; } if (temp !== null) { this.head = temp.prev; } } printList(): void { let current = this.head; const result: number[] = []; while (current !== null) { result.push(current.data); current = current.next; } console.log(result.join(' -> ') + ' -> null'); } } // Example usage const list = new DoublyLinkedList(); const nodes = [1, 2, 3, 4, 5].map(n => new Node(n)); for (let i = 0; i < nodes.length; i++) { if (i === 0) list.head = nodes[i]; if (i > 0) { nodes[i].prev = nodes[i - 1]; nodes[i - 1].next = nodes[i]; } } console.log('Original list:'); list.printList(); list.reverse(); console.log('Reversed list:'); list.printList();

Result

Original list: 1 -> 2 -> 3 -> 4 -> 5 -> null Reversed list: 5 -> 4 -> 3 -> 2 -> 1 -> null

Implementing reversal in code solidifies understanding of pointer swaps and head updates, showing the practical effect.

6

Expert

Handling Edge Cases and Performance

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

Concept: Consider what happens when the list is empty or has one node, and understand the time complexity of reversal.

If the list is empty (head is null), reversal does nothing. If it has one node, swapping pointers has no effect but still runs safely. The reversal runs in O(n) time, where n is the number of nodes, because each node is visited once. No extra memory is used, making it efficient.

Result

Reversal works correctly and efficiently for all list sizes, including edge cases.

Knowing edge cases prevents bugs in real systems and understanding complexity helps in performance-sensitive applications.

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 means the direction of traversal flips. The head pointer is updated to the last node processed, which becomes the new start. The process is done in place, so no new nodes or lists are created, preserving memory.

Why designed this way?

Doubly linked lists were designed to allow easy forward and backward traversal. Reversing by swapping pointers leverages this design to flip direction without rebuilding the list. Alternatives like creating a new reversed list would use extra memory and time. This in-place swap is a space-efficient and fast method.

Start:
Head -> [Prev: null | Data | Next] <-> [Prev | Data | Next] <-> ... <-> [Prev | Data | Next: null] <- Tail

Process each node:
For node N:
  temp = N.prev
  N.prev = N.next
  N.next = temp
  move to N.prev (original next)

End:
New Head -> [Prev: null | Data | Next] <-> ... <-> [Prev | Data | Next: null] <- New Tail

Myth Busters - 4 Common Misconceptions

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

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

Reality: Reversing swaps pointers in the existing nodes without creating new nodes.

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

Quick: After reversal, does the head pointer stay the same? Commit yes or no.

Common Belief: The head pointer remains unchanged after reversal.

Reality: The head pointer must be updated to the original tail node, which becomes the new head.

Why it matters: Failing to update the head causes the list to appear empty or broken after reversal.

Quick: Is it safe to swap pointers without temporary storage? Commit yes or no.

Common Belief: You can swap previous and next pointers directly without temporary variables.

Reality: Temporary storage is needed to avoid losing access to nodes during swapping.

Why it matters: Without temporary storage, pointers can be overwritten, causing loss of nodes and corrupting the list.

Quick: Does reversing a doubly linked list change the data inside nodes? Commit yes or no.

Common Belief: Reversing changes the data values inside nodes to reflect new order.

Reality: Reversing only changes pointers; node data remains unchanged.

Why it matters: Misunderstanding this leads to unnecessary data copying or errors in data integrity.

Expert Zone

1

Swapping pointers in place requires careful order of operations to avoid losing node references, especially in languages without automatic memory management.

2

Updating the head pointer after reversal is often overlooked, causing subtle bugs where the list appears empty or traversal fails.

3

In some implementations, reversing can be combined with other operations like insertion or deletion to optimize performance.

When NOT to use

Reversing a doubly linked list is not suitable when the list is immutable or shared across threads without synchronization. In such cases, creating a new reversed copy or using immutable data structures is safer.

Production Patterns

In real systems, reversing doubly linked lists is used in undo-redo stacks, browser history navigation, and playlist management where quick backward traversal is needed. It is often combined with other list operations and carefully tested for edge cases.

Connections

Array Reversal

Similar operation of reversing order but uses index swapping instead of pointer swapping.

Understanding array reversal helps grasp the concept of reversing order, but linked lists require pointer manipulation instead of index swaps.

Undo-Redo Systems

Uses doubly linked lists to move forward and backward through states, relying on reversal concepts for navigation.

Knowing how to reverse and traverse doubly linked lists helps implement efficient undo-redo features in software.

Bidirectional Graph Traversal

Both involve moving in two directions along connections, though graphs are more complex structures.

Understanding doubly linked list reversal aids in grasping bidirectional traversal concepts in graphs, useful in pathfinding and network analysis.

Common Pitfalls

#1 Losing track of nodes by overwriting pointers without temporary storage.

Wrong approach:

while (current !== null) {
current.prev = current.next;
current.next = current.prev;
current = current.prev;
}

Correct approach:

while (current !== null) {
let temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}

Root cause:

Swapping pointers directly without saving one pointer causes loss of reference to the next node.

#2 Not updating the head pointer after reversal.

Wrong approach:

reverse() {
// swap pointers
// but no head update
}

Correct approach:

reverse() {
// swap pointers
if (temp !== null) {
this.head = temp.prev;
}
}

Root cause:

Assuming the head remains the same after reversal leads to broken list traversal.

#3 Trying to reverse an empty list without checking for null.

Wrong approach:

let current = this.head;
while (current.next !== null) { /* swap */ }

Correct approach:

let current = this.head;
while (current !== null) { /* swap */ }

Root cause:

Not handling null head causes runtime errors when list is empty.

Key Takeaways

A doubly linked list stores pointers to both previous and next nodes, allowing two-way traversal.

Reversing a doubly linked list means swapping each node's previous and next pointers in place.

After swapping pointers, the head pointer must be updated to the original tail node to complete reversal.

Reversal runs in linear time and uses no extra memory, making it efficient for real applications.

Careful pointer management and handling edge cases prevent common bugs in reversing doubly linked lists.

Practice

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

easy

A. To sort the nodes in ascending order

B. To reverse the order of nodes so the last becomes first and vice versa

C. To delete all nodes from the list

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.

2. Step 2: Purpose of reversing

   Reversing swaps the direction so the last node becomes the first and the first becomes the last.

3. Final Answer:

   To reverse the order of nodes so the last becomes first and vice versa -> Option B

4. Quick Check:

   Reversing = changing node order [OK]

Hint: Reversing flips the list order, not deleting or sorting [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Assuming it converts to singly linked list

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

easy

A. let temp = node.next; node.next = node.prev; node.prev = temp;

B. node.next = node.next; node.prev = node.prev;

C. node.prev = node.next; node.next = node.prev;

D. let temp = node.prev; node.prev = node.next; node.next = temp.next;

Solution

1. Step 1: Identify correct swapping logic

   Swapping pointers requires a temporary variable to hold one pointer before assignment.

2. Step 2: Check each option

   let temp = node.next; node.next = node.prev; node.prev = temp; correctly uses a temp variable to swap next and prev. Others either assign incorrectly or lose references.

3. Final Answer:

   let temp = node.next; node.next = node.prev; node.prev = temp; -> Option A

4. Quick Check:

   Swap pointers using temp variable [OK]

Hint: Use a temp variable to swap pointers safely [OK]

Common Mistakes:

• Assigning pointers without temp causes data loss
• Mixing up next and prev assignments
• Using incorrect pointer references

3. What will be the output of the following TypeScript code that reverses a doubly linked list?

class Node {
  data: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(data: number) { this.data = data; }
}

function reverse(head: Node | null): Node | null {
  let current = head;
  let temp: Node | null = null;
  while (current !== null) {
    temp = current.prev;
    current.prev = current.next;
    current.next = temp;
    current = current.prev;
  }
  if (temp !== null) {
    head = temp.prev;
  }
  return head;
}

// Create list: 1 <-> 2 <-> 3
const n1 = new Node(1);
const n2 = new Node(2);
n1.next = n2; n2.prev = n1;
const n3 = new Node(3);
n2.next = n3; n3.prev = n2;

const newHead = reverse(n1);

// Print reversed list
let result = [];
let node = newHead;
while (node !== null) {
  result.push(node.data);
  node = node.next;
}
console.log(result);

medium

A. []

B. [1, 2, 3]

C. [3, 2, 1]

D. [3, 1, 2]

Solution

1. Step 1: Trace pointer swaps in the loop

   Each node swaps its next and prev. The loop moves forward using the old next pointer now in prev.

2. Step 2: Update head to new first node

   After loop, head is updated to last node processed, which is node with data 3.

3. Final Answer:

   [3, 2, 1] -> Option C

4. Quick Check:

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

Hint: Reversing swaps pointers and updates head to last node [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing next and prev in loop
• Printing original list order

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

function reverse(head: Node | null): Node | null {
  let current = head;
  while (current !== null) {
    let temp = current.next;
    current.next = current.prev;
    current.prev = temp;
    current = current.next;
  }
  return head;
}

medium

A. The function should return current instead of head

B. The pointers next and prev are swapped incorrectly

C. The loop condition should be current.next !== null

D. The function does not update the head to the new first node after reversal

Solution

1. Step 1: Check pointer swapping logic

   The swapping of next and prev is correct using a temp variable.

2. Step 2: Verify head update after reversal

   The function returns original head without updating it to the new first node, so the reversed list head is incorrect.

3. Final Answer:

   The function does not update the head to the new first node after reversal -> Option D

4. Quick Check:

   Head must update to new first node [OK]

Hint: Always update head to last processed node after reversal [OK]

Common Mistakes:

• Forgetting to update head after reversal
• Returning old head instead of new head
• Incorrect loop condition causing infinite loop

5. Given a doubly linked list with nodes containing integer data, how would you modify the reversal function to also count how many nodes were reversed and return both the new head and the count?

hard

A. Modify the function to use an object return type like { head: Node | null, count: number }, increment count inside the loop, and update head after reversal.

B. Add a global variable to count nodes and return only the new head.

C. Count nodes before reversal and return the count without changing the function.

D. Return an array with the reversed list nodes and count without modifying the reversal logic.

Solution

1. Step 1: Add a counter variable inside the reversal function

   Initialize a count variable to zero and increment it each time a node is processed in the reversal loop.

2. Step 2: Return both new head and count

   After reversal, return an object containing the updated head and the count of nodes reversed.

3. Final Answer:

   Modify the function to use an object return type like { head: Node | null, count: number }, increment count inside the loop, and update head after reversal. -> Option A

4. Quick Check:

   Return head and count together after reversal [OK]

Hint: Use an object return type to return multiple values [OK]

Common Mistakes:

• Using global variables instead of local counters
• Not updating head before returning
• Returning count without reversing