Why Doubly Linked List Over Singly Linked List in DSA Rust - Why It Works

Concept Flow - Why Doubly Linked List Over Singly Linked List

Start with Singly Linked List

↓

Can only move forward

↓

Operations like backward traversal or easy deletion

↓

Hard or inefficient

↓

Use Doubly Linked List

↓

Nodes have prev and next pointers

↓

Can move forward and backward easily

↓

Efficient deletion and traversal both ways

↓

More memory used but more flexible

Shows the flow from singly linked list limitations to doubly linked list advantages with backward links.

Execution Sample

DSA Rust

1. Create singly linked list: 1 -> 2 -> 3 -> null
2. Try to delete node 2
3. Need previous node to update next pointer
4. Singly list: must traverse from head
5. Doubly linked list: direct access to prev pointer

Shows how deletion is harder in singly linked list and easier in doubly linked list due to prev pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create singly linked list	1 -> 2 -> 3	head -> 1, 1.next -> 2, 2.next -> 3, 3.next -> null	1 -> 2 -> 3 -> null
2	Delete node 2 in singly list	1 -> 2 -> 3	Traverse from head to find node before 2	1 -> 2 -> 3 -> null
3	Update 1.next to 3	1 -> 3	1.next -> 3	1 -> 3 -> null
4	Create doubly linked list	1 <-> 2 <-> 3	head -> 1, 1.next -> 2, 2.prev -> 1, 2.next -> 3, 3.prev -> 2	1 <-> 2 <-> 3 -> null
5	Delete node 2 in doubly list	1 <-> 2 <-> 3	2.prev.next -> 3, 3.prev -> 1	1 <-> 3 -> null
6	Traversal backward from 3	1 <-> 3	3.prev -> 1	3 -> 1 -> null
7	End	1 <-> 3	No changes	1 <-> 3 -> null

💡 Deletion and backward traversal are easier in doubly linked list due to prev pointers.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	Final
head	points to node 1	points to node 1	points to node 1	points to node 1	points to node 1	points to node 1
node1.next	node 2	node 2	node 3	node 3	node 3	node 3
node2.prev	null (singly list)	null	null	node 1	node 1	null (deleted)
node2.next	node 3	node 3	node 3	node 3	node 3	null (deleted)
node3.prev	null (singly list)	null	null	node 1	node 1	node 1

Key Moments - 3 Insights

Why do we need to traverse from head to delete a node in singly linked list?

Because singly linked list nodes only have next pointers, to update the previous node's next pointer, we must find it by starting at head (see execution_table step 2 and 3).

How does having a prev pointer in doubly linked list help deletion?

Prev pointer lets us directly access the previous node to update its next pointer without traversal (see execution_table step 5).

Why does doubly linked list use more memory?

Each node stores an extra pointer (prev), increasing pointer storage compared to singly linked list.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what pointer change happens to delete node 2 in singly linked list?

A node 3.next is updated to null

B node 2.prev is updated to node 1

C node 1.next is updated to node 3

D head is updated to node 2

💡 Hint

Check the Pointer Changes column at step 3 in execution_table.

At which step does the doubly linked list show backward traversal?

A Step 5

B Step 6

C Step 2

D Step 7

💡 Hint

Look for 'Traversal backward' in the Operation column in execution_table.

If doubly linked list nodes did not have prev pointers, which step would fail?

A Step 5 deletion in doubly list

B Step 3 deletion in singly list

C Step 1 creation of singly list

D Step 7 end

💡 Hint

See how deletion in doubly list uses prev pointer in step 5.

Concept Snapshot

Doubly Linked List nodes have two pointers: next and prev.
This allows traversal forward and backward.
Deletion is easier because prev pointer gives direct access to previous node.
Singly Linked List only has next pointer, so backward traversal or deletion needs traversal from head.
Doubly Linked List uses more memory but is more flexible for operations needing backward access.

Full Transcript

This visual execution shows why doubly linked lists are preferred over singly linked lists for certain operations. Singly linked lists only have next pointers, so to delete a node, we must find the previous node by starting at the head and traversing. This is shown in steps 2 and 3 where deletion requires traversal. Doubly linked lists add a prev pointer to each node, allowing direct access to the previous node. This makes deletion and backward traversal easier and more efficient, as shown in steps 5 and 6. The tradeoff is that doubly linked lists use more memory because of the extra pointer. Overall, doubly linked lists provide more flexibility for operations that need backward movement or easy node removal.

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