Delete from Beginning of Doubly Linked List in DSA C++ - Execution Trace

Concept Flow - Delete from Beginning of Doubly Linked List

Start at head

↓

Check if head is null?

Yes→List empty, nothing to delete

No↓

Move head to head.next

↓

If new head not null, set new head.prev = null

↓

Old head node removed

↓

Done

Start at the head node, check if list is empty. If not, move head to next node and update pointers to remove old head.

Execution Sample

DSA C++

struct Node {
  int data;
  Node* prev;
  Node* next;
};

void deleteBeginning(Node*& head) {
  if (!head) return;
  Node* temp = head;
  head = head->next;
  if (head) head->prev = nullptr;
  delete temp;
}

Deletes the first node of a doubly linked list by moving head and updating pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list: 10 <-> 20 <-> 30	10 <-> 20 <-> 30	head → node(10)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Check if head is null (No)	10 <-> 20 <-> 30	No change	Same as step 1
3	Set temp = head (node 10)	10 <-> 20 <-> 30	temp → node(10)	Same as step 1
4	Move head to head.next (node 20)	10 <-> 20 <-> 30	head → node(20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:10│←── │ prev:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
5	If head not null, set head.prev = null	20 <-> 30	node(20).prev = ∅	┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
6	Delete old head node (node 10)	20 <-> 30	temp deleted	Same as step 5
7	End of deletion	20 <-> 30	head → node(20)	┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ prev:∅ │←── │ prev:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head

💡 Deletion ends after head moves and old head is removed

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
head	node(10)	node(10)	node(20)	node(20)	node(20)
temp	null	node(10)	node(10)	node(10)	deleted
node(20).prev	node(10)	node(10)	node(10)	null	null

Key Moments - 3 Insights

Why do we set head.prev to null after moving head?

Because the new head node should not point back to the old node which is removed. See execution_table step 5 where head.prev changes from node(10) to null.

What happens if the list is empty when we try to delete?

The function returns immediately without changes. See execution_table step 2 where head is checked for null and no deletion occurs.

Why do we delete the old head node after moving head?

To free memory and avoid dangling pointers. The old head is stored in temp and deleted at step 6 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of head after step 4?

A node with data 20

B node with data 10

C node with data 30

D null

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 4 in execution_table

At which step does the head.prev pointer get set to null?

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table for when head.prev changes

If the list was empty initially, what would happen at step 2?

A head moves to next node

B temp is set to head

C Function returns without deletion

D Old head node is deleted

💡 Hint

Refer to the 'Operation' and 'Nodes in List' columns at step 2 in execution_table

Concept Snapshot

Delete from Beginning of Doubly Linked List:
- Check if list is empty (head == null)
- Move head to head.next
- Set new head.prev to null if head not null
- Delete old head node to free memory
- List shrinks by one node at front

Full Transcript

This visualization shows how to delete the first node from a doubly linked list. We start at the head node and check if the list is empty. If not, we save the old head in a temporary pointer, move head to the next node, and update the new head's prev pointer to null. Then we delete the old head node to free memory. The execution table tracks each step, pointer changes, and the visual state of the list. Key moments clarify why we update pointers and handle empty lists. The quiz tests understanding of pointer updates and edge cases.

Practice

1. What happens to the head pointer when you delete the first node from a doubly linked list?

easy

A. It points to the last node

B. It becomes null immediately

C. It moves to the second node in the list

D. It remains pointing to the deleted node

Solution

1. Step 1: Understand the head pointer role

   The head points to the first node in the doubly linked list.

2. Step 2: After deletion, update the head pointer

   When the first node is deleted, the head must point to the next node, which becomes the new first node.

3. Final Answer:

   It moves to the second node in the list -> Option C

4. Quick Check:

   Head points to new first node after deletion [OK]

Hint: Head always moves to next node after deleting first [OK]

Common Mistakes:

• Not updating head pointer after deletion
• Setting head to null without checking list size
• Leaving head pointing to deleted node

2. Which of the following is the correct syntax to delete the first node in a doubly linked list in C++?

easy

A. head = head->next; delete head->prev; head->prev = nullptr;

B. Node* temp = head; head = head->next; head->prev = nullptr; delete temp;

C. head->prev = nullptr; delete head; head = head->next;

D. delete head; head = head->next; head->prev = nullptr;

Solution

1. Step 1: Store current head in temp

   We save the current first node in a temporary pointer to delete it safely after updating head.

2. Step 2: Update head and fix previous pointer

   Set head to the next node, then set head->prev to nullptr to detach the old first node.

3. Step 3: Delete the old first node

   Finally, delete the node stored in temp to free memory.

4. Final Answer:

   Node* temp = head; head = head->next; head->prev = nullptr; delete temp; -> Option B

5. Quick Check:

   Proper order: save, update, fix pointers, delete [OK]

Hint: Save head first, update pointers, then delete saved node [OK]

Common Mistakes:

• Deleting head before updating pointers
• Not setting head->prev to nullptr
• Accessing head->prev when head is nullptr

3. What will be the output of the following code snippet after deleting the first node?

struct Node {
  int data;
  Node* prev;
  Node* next;
};

Node* head = new Node{1, nullptr, nullptr};
Node* second = new Node{2, head, nullptr};
head->next = second;

// Delete from beginning
Node* temp = head;
head = head->next;
head->prev = nullptr;
delete temp;

// Print list
Node* curr = head;
while(curr != nullptr) {
  std::cout << curr->data << " ";
  curr = curr->next;
}

medium

A. 1 2

B. No output (runtime error)

C. 1

D. 2

Solution

1. Step 1: Initial list setup

   List has two nodes: 1 (head) -> 2. Head points to node with data 1.

2. Step 2: Delete first node and update pointers

   Head moves to second node (data 2), and its prev is set to nullptr. The first node is deleted.

3. Step 3: Print remaining list

   Only node with data 2 remains, so output is "2".

4. Final Answer:

   2 -> Option D

5. Quick Check:

   After deletion, list starts at 2 [OK]

Hint: After deleting head, print starts from new head [OK]

Common Mistakes:

• Printing deleted node's data
• Not updating head->prev to nullptr
• Assuming both nodes print after deletion

4. Identify the error in the following code that deletes the first node of a doubly linked list:

void deleteBeginning(Node*& head) {
  if (head == nullptr) return;
  delete head;
  head = head->next;
  if (head != nullptr) head->prev = nullptr;
}

medium

A. Deleting head before updating head pointer causes undefined behavior

B. Missing check if head->next is nullptr

C. head->prev should be set to head->next

D. No error, code works fine

Solution

1. Step 1: Analyze deletion order

   The code deletes head first, then tries to access head->next, which is invalid after deletion.

2. Step 2: Correct order to avoid undefined behavior

   First save head->next in a temp pointer, update head, then delete old node.

3. Final Answer:

   Deleting head before updating head pointer causes undefined behavior -> Option A

4. Quick Check:

   Accessing deleted memory causes error [OK]

Hint: Always update pointers before deleting nodes [OK]

Common Mistakes:

• Deleting node before updating pointers
• Accessing deleted node's members
• Not checking for empty list

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. After deleting the first node twice from the beginning, what will be the printed list?

hard

A. 30 <-> 40

B. 20 <-> 30 <-> 40

C. 10 <-> 20 <-> 30 <-> 40

D. 40

Solution

1. Step 1: Initial list nodes

   List is 10 <-> 20 <-> 30 <-> 40, head points to 10.

2. Step 2: First deletion

   Delete node 10, head moves to 20, set head->prev = nullptr. List now: 20 <-> 30 <-> 40.

3. Step 3: Second deletion

   Delete node 20, head moves to 30, set head->prev = nullptr. List now: 30 <-> 40.

4. Final Answer:

   30 <-> 40 -> Option A

5. Quick Check:

   Two deletions remove first two nodes [OK]

Hint: Each deletion moves head to next node [OK]

Common Mistakes:

• Deleting only once instead of twice
• Not updating head->prev after second deletion
• Printing old list without deletions