Delete from Beginning of Doubly Linked List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has two links: one to the next node and one to the previous node. This allows moving forward and backward through the list.

beginner

What happens when you delete the first node in a doubly linked list?

The first node is removed, the head pointer moves to the second node, and the new first node's previous link is set to NULL.

beginner

Why do we set the previous pointer of the new head to NULL after deletion?

Because the new head is now the first node, it should not point back to any node before it, so its previous pointer must be NULL.

beginner

What should you check before deleting the first node in a doubly linked list?

Check if the list is empty (head is NULL). If empty, no deletion is possible.

intermediate

Show the C code snippet to delete the first node of a doubly linked list.

if (head == NULL) return; Node* temp = head; head = head->next; if (head != NULL) head->prev = NULL; free(temp);

What pointer must be updated after deleting the first node in a doubly linked list?

A The head pointer and the new head's previous pointer

B Only the tail pointer

C Only the new head's next pointer

D No pointers need updating

After deleting the first node, the head pointer moves to the next node, and the new head's previous pointer must be set to NULL.

What should you do if the doubly linked list is empty when trying to delete the first node?

A Do nothing, as there is no node to delete

B Create a new node

C Delete the tail node instead

D Set head to NULL

If the list is empty (head is NULL), there is no node to delete, so the function should simply return.

After deleting the first node, what happens if the list had only one node?

A Head points to the deleted node

B List becomes circular

C Tail pointer changes but head stays the same

D Head becomes NULL

If the list had only one node, deleting it makes the list empty, so head becomes NULL.

Which function is used to free the memory of the deleted node in C?

A clear()

B delete()

C free()

D remove()

In C, free() is used to release the memory allocated to a node.

What is the time complexity of deleting the first node in a doubly linked list?

A O(n)

B O(1)

C O(log n)

D O(n^2)

Deleting the first node is a constant time operation because it involves updating a few pointers only.

Explain step-by-step how to delete the first node from a doubly linked list.

Think about what pointers need to change and how to avoid memory leaks.

Describe what happens to the doubly linked list structure after deleting the first node.

Visualize the list before and after deletion.

Practice

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

easy

A. It remains unchanged

B. It becomes NULL immediately

C. It moves to the second node in the list

D. It points to the last node

Solution

1. Step 1: Understand the head pointer role

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

2. Step 2: Effect of deleting the first node

   When the first node is deleted, the head pointer must move 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:

• Assuming head becomes NULL even if list has more nodes
• Not updating head pointer after deletion
• Pointing head to last node mistakenly

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

easy

A. temp = head; head = head->next; free(temp); head->prev = NULL;

B. free(head); head = head->next; head->prev = NULL;

C. head = head->next; free(head->prev); head->prev = NULL;

D. head->prev = NULL; free(head); head = head->next;

Solution

1. Step 1: Store current head in temp

   We save the current first node in a temporary pointer to free it later.

2. Step 2: Move head to next node and free old head

   Update head to point to the second node, free the old first node, and set new head's prev to NULL.

3. Final Answer:

   temp = head; head = head->next; free(temp); head->prev = NULL; -> Option A

4. Quick Check:

   Proper order: save, move, free, update pointers [OK]

Hint: Save old head before freeing, then update pointers [OK]

Common Mistakes:

• Freeing head before moving pointer
• Not setting new head's prev to NULL
• Accessing freed memory after free

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> NULL, what will be the list after deleting the first node?

medium

A. 20 <-> 30 <-> NULL

B. 10 <-> 30 <-> NULL

C. 30 <-> NULL

D. NULL

Solution

1. Step 1: Identify the first node to delete

   The first node has value 10, which will be removed.

2. Step 2: Update head to second node and adjust pointers

   Head moves to node with value 20, and its prev pointer is set to NULL.

3. Final Answer:

   20 <-> 30 <-> NULL -> Option A

4. Quick Check:

   First node removed, list starts at 20 [OK]

Hint: After deletion, list starts from second node [OK]

Common Mistakes:

• Leaving old head in list
• Not updating prev pointer of new head
• Deleting wrong node

4. What is wrong with this code snippet for deleting the first node of a doubly linked list?

void deleteBegin() {
  if (head == NULL) return;
  free(head);
  head = head->next;
  if (head != NULL) head->prev = NULL;
}

medium

A. It does not free the node

B. It does not check if list is empty

C. It forgets to set head->prev to NULL

D. It frees head before moving pointer, causing invalid access

Solution

1. Step 1: Analyze order of operations

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

2. Step 2: Correct order needed

   We must first save head->next in a temp pointer, move head, then free old node to avoid invalid memory access.

3. Final Answer:

   It frees head before moving pointer, causing invalid access -> Option D

4. Quick Check:

   Free after pointer update to avoid invalid access [OK]

Hint: Always move pointer before freeing old node [OK]

Common Mistakes:

• Freeing node before updating pointers
• Accessing freed memory
• Not handling empty list properly

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> 35 <-> NULL. After deleting the first node twice, what will be the list?

hard

A. 15 <-> 25 <-> 35 <-> NULL

B. 25 <-> 35 <-> NULL

C. 35 <-> NULL

D. NULL

Solution

1. Step 1: Delete first node once

   First deletion removes node with value 5, head moves to 15.

2. Step 2: Delete first node again

   Second deletion removes node with value 15, head moves to 25.

3. Final Answer:

   25 <-> 35 <-> NULL -> Option B

4. 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 correctly after second deletion
• Confusing node values after deletion