Reverse a Doubly Linked List in DSA C - 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. Sometimes, users want to reverse the order of songs in their playlist.

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

📋 What You'll Learn

Create a doubly linked list with exactly 3 nodes containing the songs: "Song1", "Song2", "Song3" in that order

Create a pointer variable called head that points to the first node

Create a pointer variable called temp for swapping nodes during reversal

Write a function called reverseList that reverses the doubly linked list by swapping the next and prev pointers of each node

Print the reversed list starting from the new head using the printList function

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, browsers, and other apps where users navigate forward and backward through items.

💼 Career

Understanding linked lists and how to reverse them is a common interview question and helps in managing complex data structures efficiently.

1

Create the doubly linked list with 3 songs

Create a struct called Node with char* data, Node* next, and Node* prev. Then create 3 nodes with data "Song1", "Song2", and "Song3". Link them to form a doubly linked list. Create a pointer head that points to the first node.

DSA C

// Define struct Node and create 3 nodes linked as doubly linked list
// Your code here

Hint

Remember to link the nodes both ways: next and prev.

2

Add a pointer variable temp for swapping

Inside main, declare a pointer variable called temp of type Node* and initialize it to NULL.

DSA C

#include 
#include 

typedef struct Node {
    char* data;
    struct Node* next;
    struct Node* prev;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));

    head->data = "Song1";
    head->next = second;
    head->prev = NULL;

    second->data = "Song2";
    second->next = third;
    second->prev = head;

    third->data = "Song3";
    third->next = NULL;
    third->prev = second;

    Node* temp = NULL; // Your code here

    return 0;
}

Hint

Declare Node* temp = NULL; inside main.

3

Write the reverseList function to reverse the doubly linked list

Write a function called reverseList that takes a pointer head of type Node* and returns the new head after reversing the list. Inside the function, use a pointer temp to swap the next and prev pointers of each node. Update head to the last node after reversal. Call reverseList from main and update head.

DSA C

#include 
#include 

typedef struct Node {
    char* data;
    struct Node* next;
    struct Node* prev;
} Node;

Node* reverseList(Node* head) {
    // Your code here
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));

    head->data = "Song1";
    head->next = second;
    head->prev = NULL;

    second->data = "Song2";
    second->next = third;
    second->prev = head;

    third->data = "Song3";
    third->next = NULL;
    third->prev = second;

    Node* temp = NULL;

    // Call reverseList and update head
    // Your code here

    return 0;
}

Hint

Swap next and prev for each node. Move current to prev after swapping. Update head to last node.

4

Print the reversed doubly linked list

Write a function called printList that takes head and prints the list data separated by arrows like: Song3 <-> Song2 <-> Song1. Call printList(head) from main after reversing the list.

DSA C

Hint

Traverse from head and print each node's data. Print <-> between nodes.

Practice

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

easy

A. To convert it into a singly linked list

B. To delete all nodes from the list

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

D. To sort the list in ascending order

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 direction so the last node becomes the first and vice versa.

3. Final Answer:

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

4. Quick Check:

   Reverse = last becomes first [OK]

Hint: Reversing flips start and end nodes [OK]

Common Mistakes:

• Thinking reversing deletes nodes
• Confusing reversing with sorting
• Assuming it changes list type

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

easy

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

B. node->next = node->prev; node->prev = node->next;

C. node->prev = node->next; node->next = node->prev;

D. temp = node->next; node->next = node->prev; node->prev = temp;

Solution

1. Step 1: Use a temporary variable to hold one pointer

   Store node->next in temp to avoid losing its value.

2. Step 2: Swap pointers correctly

   Assign node->next to node->prev, then node->prev to temp.

3. Final Answer:

   temp = node->next; node->next = node->prev; node->prev = temp; -> Option D

4. Quick Check:

   Swap pointers using temp variable [OK]

Hint: Always use temp variable to swap pointers safely [OK]

Common Mistakes:

• Swapping without temp loses pointer data
• Assigning both pointers to same value
• Mixing order of assignments

3. Given the following doubly linked list nodes and code snippet, what will be the new head node's data after reversal?

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

// List: 1 <-> 2 <-> 3 <-> NULL
struct Node* head = node1; // node1->data = 1

// Reversal code snippet:
struct Node* current = head;
struct Node* temp = NULL;
while (current != NULL) {
  temp = current->prev;
  current->prev = current->next;
  current->next = temp;
  current = current->prev;
}
if (temp != NULL) {
  head = temp->prev;
}

medium

A. 1

B. 3

C. 2

D. NULL

Solution

1. Step 1: Trace pointer swaps in the loop

   Each node swaps its next and prev pointers, moving current backward through original list.

2. Step 2: Update head after loop

   After loop, head is set to temp->prev, which points to original last node (data 3).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   New head = original tail = 3 [OK]

Hint: New head is original tail after reversal [OK]

Common Mistakes:

• Not updating head pointer after reversal
• Confusing prev and next pointers
• Assuming head remains same

4. Identify the error in the following code snippet that attempts to reverse a doubly linked list:

void reverse(struct Node** head_ref) {
  struct Node* current = *head_ref;
  struct Node* temp = NULL;
  while (current != NULL) {
    temp = current->next;
    current->next = current->prev;
    current->prev = temp;
    current = current->prev;
  }
  if (temp != NULL) {
    *head_ref = temp->prev;
  }
}

medium

A. temp should store current->prev instead of current->next

B. current should move to current->next instead of current->prev

C. The head pointer update is incorrect

D. No error, code is correct

Solution

1. Step 1: Verify pointer swaps

   The next/prev swaps correctly reverse directions as current traverses the original next chain (now in prev).

2. Step 2: Analyze temp assignment

   Temp should store current->prev before swapping, not current->next, to avoid losing pointer.

3. Final Answer:

   temp should store current->prev instead of current->next -> Option A

4. Quick Check:

   Correct temp assignment preserves traversal [OK]

Hint: Temp must hold current->prev before swapping pointers [OK]

Common Mistakes:

• Incorrect head pointer update logic
• Moving current incorrectly after swap
• Not updating head pointer properly

5. You have a doubly linked list with nodes containing integer data. After reversing the list using the standard pointer swap method, which of the following statements is TRUE about the list's traversal?

hard

A. Traversing from the new head using next pointers visits nodes in original reverse order

B. Traversing from the new head using prev pointers visits nodes in original order

C. Traversing from the original head using next pointers visits nodes in reversed order

D. Traversing from the new head using next pointers visits nodes in original order

Solution

1. Step 1: Understand reversal effect on pointers

   Reversing swaps next and prev pointers, so next pointers now point backward in original list.

2. Step 2: Analyze traversal from new head

   Starting at new head, following next pointers visits nodes in original reverse order.

3. Final Answer:

   Traversing from the new head using next pointers visits nodes in original reverse order -> Option A

4. Quick Check:

   Next pointers after reverse = original prev [OK]

Hint: Next pointers after reverse follow original prev links [OK]

Common Mistakes:

• Assuming next pointers still go forward after reverse
• Confusing traversal directions
• Thinking original head remains start