Why Doubly Linked List Over Singly Linked List in DSA C++ - Why This Pattern

Mental Model

A doubly linked list lets you move forward and backward easily, unlike a singly linked list that only moves forward.

Analogy: Think of a train with cars connected front and back. You can walk from the first car to the last or go back, but a singly linked list is like a one-way street where you can only go forward.

Singly Linked List:
head -> [1] -> [2] -> [3] -> null

Doubly Linked List:
null ← [1] ↔ [2] ↔ [3] -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, delete node 2

Goal: Show how deleting a middle node is easier with a doubly linked list than with a singly linked list

Step 1: In singly linked list, find node before 2 to delete 2

head -> [1] -> [2] -> [3] -> null

Why: We must find node 1 to change its next pointer to node 3

Step 2: Change node 1's next pointer to node 3

head -> [1] -> [3] -> null

Why: This removes node 2 from the chain

Step 3: In doubly linked list, directly access node 2 and update pointers

null ← [1] ↔ [2] ↔ [3] -> null

Why: We can use node 2's previous and next pointers to remove it easily

Step 4: Set node 1's next to node 3 and node 3's previous to node 1

null ← [1] ↔ [3] -> null

Why: This removes node 2 without needing to find node 1 first

Result:

Singly Linked List after deletion:
head -> [1] -> [3] -> null

Doubly Linked List after deletion:
null ← [1] ↔ [3] -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node for singly linked list
struct SNode {
    int data;
    SNode* next;
    SNode(int val) : data(val), next(nullptr) {}
};

// Node for doubly linked list
struct DNode {
    int data;
    DNode* next;
    DNode* prev;
    DNode(int val) : data(val), next(nullptr), prev(nullptr) {}
};

// Delete node with value val from singly linked list
void deleteSNode(SNode*& head, int val) {
    if (!head) return;
    if (head->data == val) {
        SNode* temp = head;
        head = head->next; // remove head
        delete temp;
        return;
    }
    SNode* curr = head;
    while (curr->next && curr->next->data != val) {
        curr = curr->next; // find node before val
    }
    if (curr->next) {
        SNode* temp = curr->next;
        curr->next = curr->next->next; // bypass node to delete
        delete temp;
    }
}

// Delete node with value val from doubly linked list
void deleteDNode(DNode*& head, int val) {
    DNode* curr = head;
    while (curr && curr->data != val) {
        curr = curr->next; // find node with val
    }
    if (!curr) return; // not found
    if (curr->prev) {
        curr->prev->next = curr->next; // link prev to next
    } else {
        head = curr->next; // update head if first node
    }
    if (curr->next) {
        curr->next->prev = curr->prev; // link next to prev
    }
    delete curr;
}

// Print singly linked list
void printSList(SNode* head) {
    SNode* curr = head;
    while (curr) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout << "null" << endl;
}

// Print doubly linked list
void printDList(DNode* head) {
    DNode* curr = head;
    while (curr) {
        cout << curr->data << " <-> ";
        curr = curr->next;
    }
    cout << "null" << endl;
}

int main() {
    // Singly linked list: 1 -> 2 -> 3 -> null
    SNode* sHead = new SNode(1);
    sHead->next = new SNode(2);
    sHead->next->next = new SNode(3);

    // Doubly linked list: null <- 1 <-> 2 <-> 3 -> null
    DNode* dHead = new DNode(1);
    DNode* d2 = new DNode(2);
    DNode* d3 = new DNode(3);
    dHead->next = d2; d2->prev = dHead;
    d2->next = d3; d3->prev = d2;

    cout << "Singly Linked List before deletion:" << endl;
    printSList(sHead);
    deleteSNode(sHead, 2);
    cout << "Singly Linked List after deleting 2:" << endl;
    printSList(sHead);

    cout << "Doubly Linked List before deletion:" << endl;
    printDList(dHead);
    deleteDNode(dHead, 2);
    cout << "Doubly Linked List after deleting 2:" << endl;
    printDList(dHead);

    return 0;
}

while (curr->next && curr->next->data != val) { curr = curr->next; // find node before val }

advance curr to node before the one to delete in singly linked list

curr->next = curr->next->next; // bypass node to delete

remove node by skipping it in singly linked list

while (curr && curr->data != val) { curr = curr->next; // find node with val }

find node to delete in doubly linked list

curr->prev->next = curr->next; // link prev to next curr->next->prev = curr->prev; // link next to prev

update both previous and next pointers to remove node in doubly linked list

Output

Singly Linked List before deletion:

1 -> 2 -> 3 -> null

Singly Linked List after deleting 2:

1 -> 3 -> null

Doubly Linked List before deletion:

1 <-> 2 <-> 3 <-> null

Doubly Linked List after deleting 2:

1 <-> 3 <-> null

Complexity Analysis

Time: O(n) because in both lists we may need to traverse nodes to find the one to delete

Space: O(1) because deletion uses only a few pointers without extra storage

vs Alternative: Doubly linked list allows deletion without needing to find the previous node separately, making some operations simpler and faster in practice

Edge Cases

Deleting head node

Head pointer updates correctly in both lists

DSA C++

if (head->data == val) {
        SNode* temp = head;
        head = head->next; // remove head

Deleting node not found

No changes happen, function returns safely

DSA C++

if (!curr) return; // not found

Deleting last node

Pointers update correctly to remove last node

DSA C++

if (curr->next) {
        curr->next->prev = curr->prev;

When to Use This Pattern

When you need to move backward and forward in a list or delete nodes easily without searching for previous nodes, reach for doubly linked list because it stores links both ways.

Common Mistakes

Mistake: Trying to delete a node in singly linked list without finding the previous node first
Fix: Always find the node before the one to delete to update its next pointer

Mistake: Not updating both previous and next pointers when deleting in doubly linked list
Fix: Update both prev->next and next->prev pointers to maintain list integrity

Summary

It allows easy backward and forward traversal and simpler node deletion.

Use it when you need to move both ways or delete nodes without extra searching.

The key is that each node knows both its previous and next neighbors.

Practice

1. Why is a doubly linked list preferred over a singly linked list when you need to traverse the list backwards?

easy

A. Because doubly linked lists use less memory than singly linked lists.

B. Because singly linked lists have pointers to previous nodes only.

C. Because doubly linked lists have pointers to both next and previous nodes, allowing backward traversal.

D. Because singly linked lists can only store integer data.

Solution

1. Step 1: Understand pointer directions in linked lists

   Singly linked lists have pointers only to the next node, so you cannot move backwards easily. Doubly linked lists have pointers to both next and previous nodes.

2. Step 2: Identify traversal capability

   Because doubly linked lists have previous pointers, they allow traversal in both directions, including backwards.

3. Final Answer:

   Because doubly linked lists have pointers to both next and previous nodes, allowing backward traversal. -> Option C

4. Quick Check:

   Backward traversal needs previous pointers = A [OK]

Hint: Backward traversal needs previous pointers in nodes [OK]

Common Mistakes:

• Thinking singly linked lists have previous pointers
• Confusing memory usage with traversal ability
• Assuming singly linked lists can traverse backwards

2. Which of the following is the correct way to declare a node structure for a doubly linked list in C++?

easy

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

B. struct Node { int data; Node* prev; };

C. struct Node { int data; Node* next; };

D. struct Node { int data; Node* next; Node* next; };

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have pointers to both the previous and next nodes.

2. Step 2: Match the structure declaration

   struct Node { int data; Node* prev; Node* next; }; declares both Node* prev and Node* next, which is correct. Others miss one pointer or have duplicate pointers.

3. Final Answer:

   struct Node { int data; Node* prev; Node* next; }; -> Option A

4. Quick Check:

   Doubly linked list node needs prev and next pointers = C [OK]

Hint: Doubly linked list nodes have prev and next pointers [OK]

Common Mistakes:

• Missing prev pointer in node structure
• Duplicating next pointer instead of prev
• Confusing singly linked list node with doubly linked list node

3. You need to implement a feature that allows moving both forward and backward through a list of songs in a music player. Why is a doubly linked list a better choice than a singly linked list for this feature?

easy

A. Because singly linked lists use less memory and are faster for this feature.

B. Because singly linked lists automatically reverse the list when needed.

C. Because doubly linked lists can store song metadata directly in nodes.

D. Because doubly linked lists allow efficient backward and forward traversal.

Solution

1. Step 1: Understand traversal needs in music player

   The feature requires moving forward and backward through songs, so traversal in both directions is needed.

2. Step 2: Compare singly and doubly linked lists for traversal

   Singly linked lists only allow forward traversal easily, while doubly linked lists have pointers to previous nodes, enabling backward traversal efficiently.

3. Final Answer:

   Because doubly linked lists allow efficient backward and forward traversal. -> Option D

4. Quick Check:

   Bidirectional traversal needs doubly linked list = B [OK]

Hint: Bidirectional traversal needs doubly linked list [OK]

Common Mistakes:

• Assuming singly linked lists can traverse backward easily
• Confusing memory usage with traversal capability
• Thinking doubly linked lists store metadata differently

4. Consider the following C++ code snippet for a doubly linked list insertion at the end. What will be the output after inserting nodes with values 10 and 20?

medium

A. 10 <-> 20 <-> null

B. 20 <-> 10 <-> null

C. 10 -> 20 -> null

D. null <- 10 <- 20

Solution

1. Step 1: Understand insertion at end in doubly linked list

   Inserting 10 first creates a node with data 10. Inserting 20 next adds it after 10, linking 10's next to 20 and 20's prev to 10.

2. Step 2: Visualize the list after insertions

   The list looks like: 10 <-> 20 <-> null, showing bidirectional links and null at the end.

3. Final Answer:

   10 <-> 20 <-> null -> Option A

4. Quick Check:

   Insertion at end keeps order 10 then 20 = D [OK]

Hint: Insertion at end appends nodes in order [OK]

Common Mistakes:

• Reversing node order after insertion
• Using singly linked list arrow notation
• Ignoring prev pointer links

5. The following code attempts to delete a node from a doubly linked list but causes a runtime error. What is the main issue?

void deleteNode(Node* del) {
  if (del == nullptr) return;
  if (del->prev != nullptr) del->prev->next = del->next;
  if (del->next != nullptr) del->next->prev = del->prev;
  delete del;
}

medium

A. It deletes the node before updating pointers.

B. It does not update the head pointer if the deleted node is the head.

C. It does not check if del is the tail node.

D. It uses incorrect pointer syntax.

Solution

1. Step 1: Analyze pointer updates in deletion

   The code updates previous and next nodes' pointers correctly but does not handle the case when the node to delete is the head (no prev).

2. Step 2: Identify missing head update

   If the node is head, the external head pointer must be updated to del->next, which is missing, causing dangling head pointer and runtime errors.

3. Final Answer:

   It does not update the head pointer if the deleted node is the head. -> Option B

4. Quick Check:

   Head node deletion needs head pointer update = A [OK]

Hint: Always update head if deleting the first node [OK]

Common Mistakes:

• Deleting node before fixing pointers
• Ignoring head pointer update
• Confusing tail node handling with head node