Why Doubly Linked List Over Singly Linked List in DSA Java - 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 by two-way couplers, so you can walk from any car to the next or previous one. A singly linked list is like a train where you can only walk 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 in doubly linked list than singly linked list

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

Singly: Head -> [1] -> [2] -> [3] -> null
Doubly: null ← [1] ↔ [2] ↔ [3] -> null

Why: We need the previous node to change its next pointer to skip node 2

Step 2: In singly linked list, traverse from head to find node 1 (previous node)

Singly: Head -> [1] -> [2] -> [3] -> null
Doubly: null ← [1] ↔ [2] ↔ [3] -> null

Why: Singly list has no backward pointer, so we must start from head

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

Singly: Head -> [1] -> [2] -> [3] -> null
Doubly: null ← [1] ↔ [3] -> null

Why: Doubly list has previous pointer, so no need to find node 1 by traversal

Step 4: In singly linked list, update node 1's next pointer to node 3 to remove node 2

Singly: Head -> [1] -> [3] -> null
Doubly: null ← [1] ↔ [3] -> null

Why: We must manually skip node 2 by changing next pointer of node 1

Result:

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

Annotated Code

DSA Java

class Node {
    int data;
    Node next;
    Node prev; // only for doubly linked list
    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    Node head;

    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; // advance curr to last node
        }
        curr.next = newNode; // link new node at end
        newNode.prev = curr; // link back pointer
    }

    void deleteNode(int key) {
        Node curr = head;
        while (curr != null && curr.data != key) {
            curr = curr.next; // find node to delete
        }
        if (curr == null) return; // node not found

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

        if (curr.next != null) {
            curr.next.prev = curr.prev; // bypass curr in backward link
        }
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(1);
        dll.append(2);
        dll.append(3);
        System.out.print("Before deletion: ");
        dll.printList();
        dll.deleteNode(2);
        System.out.print("After deletion: ");
        dll.printList();
    }
}

while (curr.next != null) { curr = curr.next; // advance curr to last node }

advance curr to last node to append new node

curr.next = newNode; // link new node at end newNode.prev = curr; // link back pointer

connect new node forward and backward pointers

while (curr != null && curr.data != key) { curr = curr.next; // find node to delete }

search for node with given key

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

update previous node's next pointer or head if deleting first node

if (curr.next != null) { curr.next.prev = curr.prev; // bypass curr in backward link }

update next node's prev pointer to bypass current node

Output

Before deletion: 1 -> 2 -> 3 -> null

After deletion: 1 -> 3 -> null

Complexity Analysis

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

Space: O(1) because we only use a few pointers regardless of list size

vs Alternative: Compared to singly linked list, doubly linked list allows deletion without traversing to find previous node, saving time in some cases

Edge Cases

Deleting head node

Head pointer updates correctly and prev pointer of new head is null

DSA Java

else {
    head = curr.next; // deleting head
}

Deleting tail node

Next pointer of previous node is set to null, tail updates correctly

DSA Java

if (curr.next != null) {
    curr.next.prev = curr.prev; // bypass curr in backward link
}

Deleting node not found

No changes made, function returns early

DSA Java

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

When to Use This Pattern

When a problem needs easy backward traversal or quick deletion of a node without searching for its previous node, reach for doubly linked list because it stores backward links.

Common Mistakes

Mistake: Not updating the prev pointer of the next node when deleting a node
Fix: Always update curr.next.prev to curr.prev if curr.next is not null

Mistake: Forgetting to handle deletion of the head node separately
Fix: Check if curr.prev is null and update head pointer accordingly

Summary

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

Use it when you need to move backward easily or delete nodes without searching for previous nodes.

The key insight is that backward pointers save time by avoiding traversal to find previous nodes.

Practice

1. Why might a doubly linked list be preferred over a singly linked list when frequent backward traversal is needed?

easy

A. Because singly linked lists are faster for all operations.

B. Because singly linked lists use less memory.

C. Because doubly linked lists cannot be traversed forward.

D. Because doubly linked lists allow traversal in both directions easily.

Solution

1. Step 1: Understand traversal directions in linked lists

   Singly linked lists allow traversal only in one direction (forward), while doubly linked lists allow traversal both forward and backward.

2. Step 2: Identify the need for backward traversal

   If frequent backward traversal is needed, doubly linked lists are preferred because they have pointers to previous nodes, enabling easy backward movement.

3. Final Answer:

   Because doubly linked lists allow traversal in both directions easily. -> Option D

4. Quick Check:

   Backward traversal = doubly linked list [OK]

Hint: Backward moves need doubly linked list pointers [OK]

Common Mistakes:

• Thinking singly linked lists support backward traversal
• Assuming doubly linked lists cannot go forward
• Confusing memory use with traversal ability

2. Which of the following is the correct way to declare a node in a doubly linked list in Java?

easy

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

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

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

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

Solution

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

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

2. Step 2: Match declaration syntax

   class Node { int data; Node next; Node prev; } correctly declares data, next, and prev pointers with correct names and types.

3. Final Answer:

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

4. Quick Check:

   Node with next and prev pointers = class Node { int data; Node next; Node prev; } [OK]

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

Common Mistakes:

• Omitting prev pointer for doubly linked list
• Using wrong pointer names like 'previous' instead of 'prev'
• Confusing singly linked list node with doubly linked list node

3. What will be the output of the following code snippet that inserts a node at the end of a doubly linked list?

class Node {
  int data;
  Node next, prev;
  Node(int d) { data = d; next = prev = null; }
}

class DoublyLinkedList {
  Node head;
  void append(int new_data) {
    Node new_node = new Node(new_data);
    if (head == null) {
      head = new_node;
      return;
    }
    Node last = head;
    while (last.next != null) last = last.next;
    last.next = new_node;
    new_node.prev = last;
  }
  void printList() {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }
}

public class Main {
  public static void main(String[] args) {
    DoublyLinkedList dll = new DoublyLinkedList();
    dll.append(10);
    dll.append(20);
    dll.append(30);
    dll.printList();
  }
}

medium

A. 10 20 30

B. 30 20 10

C. 10 20

D. Compilation error

Solution

1. Step 1: Trace append method calls

   First append adds 10 as head. Second append adds 20 after 10. Third append adds 30 after 20.

2. Step 2: Trace printList output

   Prints nodes from head forward: 10, then 20, then 30, each followed by a space.

3. Final Answer:

   10 20 30 -> Option A

4. Quick Check:

   Appending nodes prints in insertion order [OK]

Hint: Append adds at end; printList prints forward [OK]

Common Mistakes:

• Confusing print order as reversed
• Assuming append adds at head
• Expecting compilation errors due to syntax

4. Identify the error in the following code snippet that tries to delete the last node of a doubly linked list:

void deleteLast() {
  if (head == null) return;
  Node temp = head;
  while (temp.next != null) {
    temp = temp.next;
  }
  temp.prev.next = null;
}

medium

A. No error; code deletes last node correctly.

B. Loop condition should be temp != null.

C. NullPointerException if list has only one node.

D. temp.prev is never assigned, causing error.

Solution

1. Step 1: Analyze deletion logic

   The code moves temp to last node, then sets temp.prev.next to null to remove last node.

2. Step 2: Check edge case of single node list

   If list has only one node, temp.prev is null, so temp.prev.next causes NullPointerException.

3. Final Answer:

   NullPointerException if list has only one node. -> Option C

4. Quick Check:

   Single node deletion needs special handling [OK]

Hint: Check single node case to avoid null pointer [OK]

Common Mistakes:

• Ignoring single node edge case
• Assuming prev pointer always exists
• Misreading loop condition

5. You need to implement a text editor's undo feature that requires moving backward and forward through changes efficiently. Which linked list type is best and why?

hard

A. Singly linked list, because it uses less memory and is faster.

B. Doubly linked list, because it allows easy backward and forward traversal.

C. Circular singly linked list, because it loops through changes endlessly.

D. Array list, because it supports random access.

Solution

1. Step 1: Understand undo feature requirements

   Undo needs to move backward through changes; redo needs forward movement.

2. Step 2: Choose data structure supporting bidirectional traversal

   Doubly linked list supports moving both backward and forward efficiently, unlike singly linked list.

3. Final Answer:

   Doubly linked list, because it allows easy backward and forward traversal. -> Option B

4. Quick Check:

   Undo/redo needs doubly linked list [OK]

Hint: Undo needs backward moves; doubly linked list fits [OK]

Common Mistakes:

• Choosing singly linked list ignoring backward moves
• Confusing circular list with undo functionality
• Assuming array list is best for undo/redo