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 which 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 from the last to the first. A singly linked list is like a train where you can only walk forward.

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

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

Dry Run Walkthrough

Input: list: 1->2->3, need to delete node 2 and then move backward from node 3

Goal: Show how doubly linked list allows easy backward movement and deletion compared to singly linked list

Step 1: Delete node 2 in singly linked list by changing node 1's next to node 3

1 -> [curr->3] -> null

Why: We must find node 1 and change its next pointer to skip node 2

Step 2: Try to move backward from node 3 in singly linked list

1 -> 3 -> null (no backward pointer)

Why: No pointer to go back, so backward movement is impossible

Step 3: Delete node 2 in doubly linked list by changing node 1's next to node 3 and node 3's prev to node 1

1 ↔ [curr->3] ↔ null

Why: We update both next and prev pointers to remove node 2 cleanly

Step 4: Move backward from node 3 to node 1 using prev pointer

1 ↔ 3 ↔ null, curr moves backward to 1

Why: Prev pointer allows easy backward traversal

Result:

Doubly linked list: 1 ↔ 3 ↔ null
Singly linked list: 1 -> 3 -> null (no backward movement possible)

Annotated Code

DSA C#

using System;

class Node {
    public int data;
    public Node next;
    public Node prev; // only used in doubly linked list
    public Node(int d) { data = d; next = null; prev = null; }
}

class DoublyLinkedList {
    public Node head;

    public void Append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.prev = curr; // link back to previous node
    }

    public void Delete(int data) {
        Node curr = head;
        while (curr != null && curr.data != data) {
            curr = curr.next;
        }
        if (curr == null) return; // not found

        if (curr.prev != null) {
            curr.prev.next = curr.next; // bypass curr
        } else {
            head = curr.next; // deleting head
        }
        if (curr.next != null) {
            curr.next.prev = curr.prev; // link back
        }
    }

    public void PrintForward() {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }

    public void PrintBackward() {
        if (head == null) return;
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next; // go to tail
        }
        while (curr != null) {
            Console.Write(curr.data);
            if (curr.prev != null) Console.Write(" -> ");
            curr = curr.prev;
        }
        Console.WriteLine(" -> null");
    }
}

class SinglyLinkedList {
    public Node head;

    public void Append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = newNode;
    }

    public void Delete(int data) {
        if (head == null) return;
        if (head.data == data) {
            head = head.next; // delete head
            return;
        }
        Node curr = head;
        while (curr.next != null && curr.next.data != data) {
            curr = curr.next;
        }
        if (curr.next == null) return; // not found
        curr.next = curr.next.next; // bypass node
    }

    public void PrintForward() {
        Node curr = head;
        while (curr != null) {
            Console.Write(curr.data);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }
}

class Program {
    static void Main() {
        // Singly linked list example
        SinglyLinkedList sList = new SinglyLinkedList();
        sList.Append(1);
        sList.Append(2);
        sList.Append(3);
        sList.Delete(2);
        Console.WriteLine("Singly Linked List after deleting 2:");
        sList.PrintForward();

        // Doubly linked list example
        DoublyLinkedList dList = new DoublyLinkedList();
        dList.Append(1);
        dList.Append(2);
        dList.Append(3);
        dList.Delete(2);
        Console.WriteLine("Doubly Linked List after deleting 2 (forward):");
        dList.PrintForward();
        Console.WriteLine("Doubly Linked List after deleting 2 (backward):");
        dList.PrintBackward();
    }
}

newNode.prev = curr; // link back to previous node

link new node's prev pointer to current tail to enable backward traversal

curr.prev.next = curr.next; // bypass curr

update previous node's next pointer to skip current node for deletion

curr.next.prev = curr.prev; // link back

update next node's prev pointer to skip current node for deletion

curr = curr.next;

advance current pointer forward to traverse list

curr = curr.prev;

move current pointer backward to traverse list in reverse

curr.next = curr.next.next; // bypass node

update next pointer to delete node in singly linked list

Output

Singly Linked List after deleting 2:

1 -> 3 -> null

Doubly Linked List after deleting 2 (forward):

1 -> 3 -> null

Doubly Linked List after deleting 2 (backward):

3 -> 1 -> null

Complexity Analysis

Time: O(n) because we may need to traverse the list to find the node to delete or to reach the tail

Space: O(n) for storing n nodes; doubly linked list uses extra space for prev pointers

vs Alternative: Doubly linked list uses more space but allows backward traversal and easier deletion of nodes without needing to track previous nodes during traversal, unlike singly linked list

Edge Cases

empty list

delete does nothing, print shows empty

DSA C#

if (head == null) return; // not found

delete head node

head pointer updates to next node correctly

DSA C#

if (head.data == data) { head = head.next; return; }

delete node not in list

no change to list

DSA C#

if (curr == null) return; // not found

When to Use This Pattern

When a problem needs easy backward traversal or deletion without extra traversal, reach for doubly linked list because it stores pointers both ways.

Common Mistakes

Mistake: Trying to move backward in singly linked list which has no prev pointer
Fix: Use doubly linked list which has prev pointers for backward movement

Mistake: Not updating both next and prev pointers when deleting a node in doubly linked list
Fix: Always update both next and prev pointers to maintain list integrity

Summary

Doubly linked list allows traversal in both directions and easier node deletion.

Use it when you need to move backward or delete nodes without extra traversal.

The key is storing pointers to both next and previous nodes for flexible navigation.

Practice

1. Why might you choose a doubly linked list over a singly linked list in a program?

easy

A. Because it allows traversal in both directions easily

B. Because it uses less memory than singly linked list

C. Because it is simpler to implement

D. Because it only stores one pointer per node

Solution

1. Step 1: Understand traversal capabilities

   A doubly linked list stores two pointers per node: one to the next node and one to the previous node, allowing movement forward and backward.

2. Step 2: Compare with singly linked list

   A singly linked list stores only one pointer per node, allowing traversal only in one direction (forward).

3. Final Answer:

   Because it allows traversal in both directions easily -> Option A

4. Quick Check:

   Traversal both ways = A [OK]

Hint: Doubly means two directions for easy backward moves [OK]

Common Mistakes:

• Thinking doubly linked list uses less memory
• Assuming singly linked list supports backward traversal
• Confusing simplicity with functionality

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

easy

A. public class Node { public int data; public Node next; }

B. public class Node { public int data; public Node next; public Node prev; }

C. public class Node { public int data; public Node prev; }

D. public class Node { public int data; public Node previous; }

Solution

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

   A doubly linked list node must have a pointer to the next node and a pointer to the previous node.

2. Step 2: Check each option for correct pointers

   public class Node { public int data; public Node next; public Node prev; } declares both next and prev pointers, matching the doubly linked list requirements.

3. Final Answer:

   public class Node { public int data; public Node next; public Node prev; } -> Option B

4. Quick Check:

   Two pointers (next, prev) = C [OK]

Hint: Doubly linked list node has next and prev pointers [OK]

Common Mistakes:

• Missing the prev pointer for doubly linked list
• Using incorrect pointer names like previous instead of prev
• Confusing singly linked list node with doubly linked list node

3. Consider the following C# code snippet for a doubly linked list:

Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);

head.next = second;
second.prev = head;
second.next = third;
third.prev = second;

// Now move backward from third node
Node current = third;
while (current != null) {
    Console.Write(current.data + " -> ");
    current = current.prev;
}
Console.WriteLine("null");

What will be the printed output?

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null

D. 3 -> null

Solution

1. Step 1: Understand the list connections

   The nodes are connected as 1 <-> 2 <-> 3, with prev and next pointers set correctly.

2. Step 2: Trace backward traversal from third node

   Starting at node with data 3, moving prev goes to 2, then 1, then null, printing each data value.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Backward traversal prints 3,2,1 [OK]

Hint: Backward traversal prints nodes in reverse order [OK]

Common Mistakes:

• Confusing forward and backward traversal output
• Forgetting to print 'null' at the end
• Assuming singly linked list traversal

4. The following code attempts to insert a new node after a given node in a doubly linked list. What is the bug?

void InsertAfter(Node prevNode, int newData) {
    if (prevNode == null) return;
    Node newNode = new Node(newData);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;
}

medium

A. It incorrectly assigns newNode.prev

B. It does not create the new node correctly

C. It does not check if prevNode is null

D. It does not update the prev pointer of the next node

Solution

1. Step 1: Analyze pointer updates after insertion

   The new node's next pointer is set to prevNode's next, and prevNode's next is updated to newNode, but the next node's prev pointer is not updated.

2. Step 2: Identify missing update for next node's prev pointer

   Without updating newNode.next.prev to point back to newNode, the list's backward links break.

3. Final Answer:

   It does not update the prev pointer of the next node -> Option D

4. Quick Check:

   Missing next node's prev update = A [OK]

Hint: Always update both next and prev pointers when inserting [OK]

Common Mistakes:

• Forgetting to update next node's prev pointer
• Assuming newNode.prev is enough
• Ignoring null checks for next node

5. You want to implement a feature that frequently deletes nodes from the middle of a linked list and also needs to traverse backward efficiently. Which linked list type is best and why?

hard

A. Singly linked list, because it uses less memory

B. Array list, because it supports random access

C. Doubly linked list, because it allows backward traversal and easy node deletion

D. Circular singly linked list, because it loops infinitely

Solution

1. Step 1: Consider deletion and traversal requirements

   Deleting nodes from the middle requires access to previous nodes to update pointers, and backward traversal needs two-way links.

2. Step 2: Match requirements with linked list types

   Doubly linked lists store both next and prev pointers, enabling efficient backward traversal and easy deletion without full traversal.

3. Final Answer:

   Doubly linked list, because it allows backward traversal and easy node deletion -> Option C

4. Quick Check:

   Backward traversal + easy deletion = D [OK]

Hint: Use doubly linked list for easy backward moves and deletions [OK]

Common Mistakes:

• Choosing singly linked list despite backward traversal need
• Confusing circular list benefits
• Ignoring memory vs functionality trade-offs