Why Doubly Linked List Over Singly Linked List in DSA C++ - Why It Works

Concept Flow - Why Doubly Linked List Over Singly Linked List

Start with Singly Linked List

↓

Can only move forward

↓

Operations like Insert/Delete at end or middle require traversal from head

↓

Limitations: No backward traversal, inefficient for some operations

↓

Introduce Doubly Linked List

↓

Each node has prev and next pointers

↓

Can move forward and backward

↓

Insert/Delete easier at both ends and middle

↓

More flexible but uses extra memory for prev pointer

Shows the flow from singly linked list limitations to doubly linked list advantages with backward traversal and easier operations.

Execution Sample

DSA C++

struct Node {
  int data;
  Node* prev;
  Node* next;
};
// Insert at end in doubly linked list

This code snippet shows a doubly linked list node structure and hints at insertion at the end.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = nullptr	null
2	Insert node 10 at end	10	head -> newNode(10), newNode.prev = nullptr, newNode.next = nullptr	10 <-> null
3	Insert node 20 at end	10 -> 20	newNode(20).prev = node(10), node(10).next = newNode(20), newNode(20).next = nullptr	10 <-> 20 <-> null
4	Traverse forward from head	10 -> 20	current moves: 10 -> 20	Visited nodes: 10, 20
5	Traverse backward from tail	10 -> 20	current moves: 20 -> 10	Visited nodes: 20, 10
6	Delete node 20	10	node(10).next = nullptr, node(20) removed	10 <-> null
7	Insert node 5 at beginning	5 -> 10	newNode(5).next = node(10), node(10).prev = newNode(5), head = newNode(5), newNode(5).prev = nullptr	5 <-> 10 <-> null
8	Attempt backward traversal in singly linked list (not possible)	10 -> 20	No prev pointer, cannot move backward	Only forward traversal possible
9	End	5 -> 10	No changes	5 <-> 10 <-> null

💡 Operations stop after demonstrating insertion, traversal, deletion, and backward traversal advantages of doubly linked list.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 7	Final
head	nullptr	node(10)	node(10)	node(10)	node(5)	node(5)
node(10).prev	N/A	nullptr	nullptr	nullptr	node(5)	node(5)
node(10).next	N/A	nullptr	node(20)	nullptr	nullptr	nullptr
node(20).prev	N/A	N/A	node(10)	deleted	N/A	N/A
node(20).next	N/A	N/A	nullptr	deleted	N/A	N/A

Key Moments - 3 Insights

Why can't we traverse backward in a singly linked list?

Because singly linked list nodes only have a 'next' pointer, no 'prev' pointer to go backward. See execution_table step 8 where backward traversal is not possible.

How does having a 'prev' pointer make deletion easier?

With 'prev' pointer, we can directly access the previous node to update its 'next' pointer during deletion without traversing from head. Refer to step 6 where node 20 is deleted easily.

Does doubly linked list use more memory than singly linked list?

Yes, because each node stores an extra 'prev' pointer. This trade-off gives more flexibility as shown in the visual states.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which nodes are visited during backward traversal?

A 10 then 20

B 20 then 10

C Only 10

D No nodes visited

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 5 showing current moves 20 -> 10.

At which step is the 'prev' pointer first used to insert a node?

A Step 3

B Step 2

C Step 7

D Step 6

💡 Hint

Look at step 3 where newNode(20).prev = node(10) is set.

If we remove the 'prev' pointer from nodes, which operation becomes impossible as shown in the table?

A Forward traversal

B Insertion at end

C Backward traversal

D Deletion at head

💡 Hint

Refer to step 8 where backward traversal is not possible without 'prev' pointer.

Concept Snapshot

Doubly Linked List nodes have two pointers: prev and next.
Allows traversal forward and backward.
Insertion and deletion easier at both ends and middle.
Uses more memory than singly linked list.
Better for operations needing backward access.

Full Transcript

A singly linked list has nodes with only a next pointer, so you can only move forward. This limits operations like backward traversal or easy deletion of nodes without starting from the head. A doubly linked list adds a prev pointer to each node, allowing movement both forward and backward. This makes insertion and deletion at both ends or in the middle easier and more efficient. However, it uses extra memory for the prev pointer. The execution steps show inserting nodes, traversing forward and backward, deleting nodes, and how the pointers change. Backward traversal is impossible in singly linked lists because nodes lack the prev pointer. The trade-off is between memory use and flexibility.

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