Why Doubly Linked List Over Singly Linked List in DSA Rust - 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.

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

Doubly Linked List:
null ← [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 makes backward movement and deletion easier than singly linked list

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

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

Why: We must find node 1 to change its next pointer because singly linked list has no backward link

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

head -> [1] -> [3] -> null
No backward pointer from [3]

Why: Singly linked list nodes do not have previous pointers, so backward move is impossible

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

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

Why: Doubly linked list allows direct access to previous node to update pointers

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

null ← [1] ↔ [3] -> null
Current at [3] ↑ move prev -> [1] ↑

Why: Doubly linked list nodes have prev pointers enabling backward traversal

Result:

Doubly linked list after deletion and backward move:
null ← [1] ↔ [3] -> null
Backward move successful

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct SinglyNode {
    val: i32,
    next: Option<Rc<RefCell<SinglyNode>>>,
}

#[derive(Debug)]
struct DoublyNode {
    val: i32,
    next: Option<Rc<RefCell<DoublyNode>>>,
    prev: Option<Rc<RefCell<DoublyNode>>>,
}

// Delete node with value 2 in singly linked list
fn delete_singly(head: &Option<Rc<RefCell<SinglyNode>>>, val: i32) -> Option<Rc<RefCell<SinglyNode>>> {
    let mut dummy = Rc::new(RefCell::new(SinglyNode { val: 0, next: head.clone() }));
    let mut curr = dummy.clone();
    while let Some(next_node) = curr.borrow().next.clone() {
        if next_node.borrow().val == val {
            // Skip node with val
            curr.borrow_mut().next = next_node.borrow().next.clone();
            break;
        }
        curr = next_node;
    }
    dummy.borrow().next.clone()
}

// Delete node with value 2 in doubly linked list
fn delete_doubly(head: &Option<Rc<RefCell<DoublyNode>>>, val: i32) -> Option<Rc<RefCell<DoublyNode>>> {
    let mut curr = head.clone();
    while let Some(node) = curr.clone() {
        if node.borrow().val == val {
            let prev = node.borrow().prev.clone();
            let next = node.borrow().next.clone();
            if let Some(p) = prev {
                p.borrow_mut().next = next.clone();
            }
            if let Some(n) = next {
                n.borrow_mut().prev = prev.clone();
            }
            // If deleting head
            if prev.is_none() {
                return next;
            }
            break;
        }
        curr = node.borrow().next.clone();
    }
    head.clone()
}

fn print_singly(head: &Option<Rc<RefCell<SinglyNode>>>) {
    let mut curr = head.clone();
    while let Some(node) = curr {
        print!("{} -> ", node.borrow().val);
        curr = node.borrow().next.clone();
    }
    println!("null");
}

fn print_doubly_forward(head: &Option<Rc<RefCell<DoublyNode>>>) {
    let mut curr = head.clone();
    while let Some(node) = curr {
        print!("{} -> ", node.borrow().val);
        curr = node.borrow().next.clone();
    }
    println!("null");
}

fn print_doubly_backward(tail: &Option<Rc<RefCell<DoublyNode>>>) {
    let mut curr = tail.clone();
    while let Some(node) = curr {
        print!("{} -> ", node.borrow().val);
        curr = node.borrow().prev.clone();
    }
    println!("null");
}

fn main() {
    // Singly linked list: 1->2->3->null
    let node3 = Rc::new(RefCell::new(SinglyNode { val: 3, next: None }));
    let node2 = Rc::new(RefCell::new(SinglyNode { val: 2, next: Some(node3.clone()) }));
    let node1 = Rc::new(RefCell::new(SinglyNode { val: 1, next: Some(node2.clone()) }));
    let head_singly = Some(node1.clone());

    println!("Singly Linked List before deletion:");
    print_singly(&head_singly);

    let head_singly = delete_singly(&head_singly, 2);

    println!("Singly Linked List after deleting 2:");
    print_singly(&head_singly);

    // Doubly linked list: 1<->2<->3
    let node3_d = Rc::new(RefCell::new(DoublyNode { val: 3, next: None, prev: None }));
    let node2_d = Rc::new(RefCell::new(DoublyNode { val: 2, next: Some(node3_d.clone()), prev: None }));
    node3_d.borrow_mut().prev = Some(node2_d.clone());
    let node1_d = Rc::new(RefCell::new(DoublyNode { val: 1, next: Some(node2_d.clone()), prev: None }));
    node2_d.borrow_mut().prev = Some(node1_d.clone());
    let head_doubly = Some(node1_d.clone());

    println!("Doubly Linked List before deletion:");
    print_doubly_forward(&head_doubly);

    let head_doubly = delete_doubly(&head_doubly, 2);

    println!("Doubly Linked List after deleting 2:");
    print_doubly_forward(&head_doubly);

    // Move backward from tail (node 3)
    println!("Doubly Linked List backward from tail:");
    print_doubly_backward(&Some(node3_d.clone()));
}

while let Some(next_node) = curr.borrow().next.clone() { if next_node.borrow().val == val { curr.borrow_mut().next = next_node.borrow().next.clone(); break; } curr = next_node; }

Traverse singly linked list to find node before target and skip target node

while let Some(node) = curr.clone() { if node.borrow().val == val { let prev = node.borrow().prev.clone(); let next = node.borrow().next.clone(); if let Some(p) = prev { p.borrow_mut().next = next.clone(); } if let Some(n) = next { n.borrow_mut().prev = prev.clone(); } if prev.is_none() { return next; } break; } curr = node.borrow().next.clone(); }

Traverse doubly linked list to find target node and update prev and next pointers to remove it

print_doubly_backward(&Some(node3_d.clone()));

Traverse backward from tail using prev pointers

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

Doubly Linked List backward from tail:

3 -> 1 -> null

Complexity Analysis

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

Space: O(n) for storing nodes; pointer updates use O(1) extra space

vs Alternative: Doubly linked list allows backward traversal and easier deletion of nodes when given a pointer to the node, unlike singly linked list which requires traversal from head

Edge Cases

Deleting head node in doubly linked list

Head pointer updates to next node; prev of new head set to None

DSA Rust

if prev.is_none() { return next; }

Deleting node not present

List remains unchanged

DSA Rust

while let Some(node) = curr.clone() { ... curr = node.borrow().next.clone(); }

Backward traversal from tail node

Traverse prev pointers until None

DSA Rust

while let Some(node) = curr { curr = node.borrow().prev.clone(); }

When to Use This Pattern

When a problem needs easy backward traversal or deletion without full traversal, reach for doubly linked list because it has prev pointers enabling these operations efficiently.

Common Mistakes

Mistake: Trying to move backward in singly linked list by accessing a non-existent prev pointer
Fix: Use doubly linked list which has prev pointers for backward traversal

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

Summary

Doubly linked list allows moving forward and backward through nodes easily.

Use it when you need to traverse backward or delete nodes efficiently without starting from head.

The key insight is that having pointers in both directions makes some operations simpler and faster.

Practice

1. Why might a doubly linked list be preferred over a singly linked list in some cases?

easy

A. Because it cannot be used to implement stacks

B. Because it allows traversal in both forward and backward directions

C. Because it only stores one pointer per node

D. Because it uses less memory than singly linked list

Solution

1. Step 1: Understand traversal capabilities

   A singly linked list allows traversal only in one direction, from head to tail.

2. Step 2: Compare with doubly linked list

   A doubly linked list stores two pointers per node, allowing traversal both forward and backward.

3. Final Answer:

   Because it allows traversal in both forward and backward directions -> Option B

4. Quick Check:

   Traversal direction = Both forward and backward [OK]

Hint: Doubly linked lists have two pointers per node [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing pointer count per node
• Assuming singly linked lists allow backward traversal

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

easy

A. struct Node { data: i32, prev: Option, next: Option }

B. struct Node { data: i32, prev: Box<Node> }

C. struct Node { data: i32, next: Option }

D. struct Node { data: i32, next: Node }

Solution

1. Step 1: Identify doubly linked list node fields

   A doubly linked list node must have pointers to both previous and next nodes, usually wrapped in Option and Box for ownership.

2. Step 2: Check each option

   struct Node { data: i32, prev: Option, next: Option } correctly declares both prev and next as Option. Others miss prev or use incorrect types.

3. Final Answer:

   struct Node { data: i32, prev: Option, next: Option } -> Option A

4. Quick Check:

   Prev and next pointers = struct Node { data: i32, prev: Option, next: Option } [OK]

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

Common Mistakes:

• Omitting prev pointer
• Using Box<Node> without Option
• Using next as Node instead of pointer

3. Given this Rust code snippet for a doubly linked list insertion at the end, what will be the printed list after inserting 3 nodes with values 10, 20, 30?

let mut list = DoublyLinkedList::new();
list.push_back(10);
list.push_back(20);
list.push_back(30);
list.print_forward();

medium

A. 10 -> 30 -> 20 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Understand push_back behavior

   push_back adds nodes at the end, so nodes are appended in order 10, then 20, then 30.

2. Step 2: Trace print_forward output

   Printing forward shows nodes from head to tail: 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Insertion order = Printed order [OK]

Hint: push_back appends at tail, print_forward shows head to tail [OK]

Common Mistakes:

• Confusing push_back with push_front
• Printing backward instead of forward
• Mixing node order in output

4. In this Rust doubly linked list code, what is the bug causing incorrect backward traversal?

fn print_backward(&self) {
    let mut current = self.tail.clone();
    while let Some(node) = current {
        print!("{} -> ", node.data);
        current = node.next.clone();
    }
    println!("null");
}

medium

A. Not cloning the tail pointer

B. Printing node.data instead of node.prev

C. Using node.next instead of node.prev for backward traversal

D. Missing a break statement in the loop

Solution

1. Step 1: Analyze traversal direction

   Backward traversal should follow prev pointers, but code uses node.next which goes forward.

2. Step 2: Identify correct pointer usage

   Replacing node.next with node.prev fixes backward traversal.

3. Final Answer:

   Using node.next instead of node.prev for backward traversal -> Option C

4. Quick Check:

   Backward traversal = Use prev pointer [OK]

Hint: Backward traversal uses prev pointer, not next [OK]

Common Mistakes:

• Confusing next and prev pointers
• Not cloning pointers properly
• Printing wrong data fields

5. You want to implement a feature that allows quick removal of a node from the middle of a list without traversing from the head. Why is a doubly linked list better than a singly linked list for this task?

hard

A. Because doubly linked list nodes have pointers to previous nodes, enabling direct access to neighbors

B. Because singly linked lists store extra data for quick removal

C. Because doubly linked lists use less memory, making removal faster

D. Because singly linked lists allow backward traversal

Solution

1. Step 1: Understand node removal requirements

   Removing a node requires updating pointers of its neighbors, including the previous node.

2. Step 2: Compare singly and doubly linked lists

   Singly linked lists lack backward pointers, so to remove a node, you must traverse from head to find the previous node. Doubly linked lists have prev pointers, allowing direct access to neighbors.

3. Final Answer:

   Because doubly linked list nodes have pointers to previous nodes, enabling direct access to neighbors -> Option A

4. Quick Check:

   Prev pointer enables quick removal [OK]

Hint: Prev pointer lets you remove nodes without full traversal [OK]

Common Mistakes:

• Assuming singly linked lists have backward pointers
• Thinking memory usage affects removal speed
• Confusing traversal direction capabilities