Delete Node at Beginning in DSA Java - Time & Space Complexity

Time Complexity: Delete Node at Beginning

O(1)

Understanding Time Complexity

We want to know how long it takes to remove the first item from a list.

How does the time needed change when the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node {
  int data;
  Node next;
}

Node deleteAtBeginning(Node head) {
  if (head == null) return null;
  return head.next;
}
    

This code removes the first node from a linked list and returns the new head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the first node and changing the head pointer.
• How many times: This happens only once, no loops or repeated steps.

How Execution Grows With Input

Removing the first node takes the same amount of time no matter how big the list is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays the same even if the list grows larger.

Final Time Complexity

Time Complexity: O(1)

This means deleting the first node takes a fixed amount of time regardless of list size.

Common Mistake

[X] Wrong: "Deleting the first node takes longer if the list is bigger because we have to check all nodes."

[OK] Correct: We only change the head pointer; no need to look at other nodes.

Interview Connect

Knowing this helps you explain how simple operations on linked lists work fast, a key skill in many coding tasks.

Self-Check

"What if we had to delete the last node instead? How would the time complexity change?"

Practice

1. What happens to the head pointer when you delete a node at the beginning of a singly linked list?

easy

A. It moves to the next node in the list

B. It becomes null immediately

C. It points to the last node

D. It remains unchanged

Solution

1. Step 1: Understand the head pointer role

   The head pointer always points to the first node in the list.

2. Step 2: Effect of deleting the first node

   Deleting the first node means the head must point to the second node, which becomes the new first node.

3. Final Answer:

   It moves to the next node in the list -> Option A

4. Quick Check:

   Head points to next node after deletion [OK]

Hint: Head always points to first node; update it to next after deletion [OK]

Common Mistakes:

• Forgetting to update head pointer
• Setting head to null without checking list
• Pointing head to last node incorrectly

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

easy

A. head = head.next;

B. head.next = head;

C. head = null.next;

D. head.next = null;

Solution

1. Step 1: Understand the head pointer update

   To delete the first node, head must point to the second node, which is head.next.

2. Step 2: Check each option

   head = head.next; correctly assigns head to head.next. Others either cause errors or wrong assignments.

3. Final Answer:

   head = head.next; -> Option A

4. Quick Check:

   Assign head to next node to delete first [OK]

Hint: Assign head to head.next to delete first node [OK]

Common Mistakes:

• Using head.next = head which reverses links
• Trying to access null.next causing error
• Setting head.next to null which breaks list

3. Given the linked list: 10 -> 20 -> 30 -> null, what will be the list after deleting the node at the beginning using head = head.next;?

medium

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

B. 20 -> 30 -> null

C. 30 -> null

D. null

Solution

1. Step 1: Identify the initial list

   The list starts as 10 -> 20 -> 30 -> null, with head pointing to 10.

2. Step 2: Apply deletion by moving head

   Setting head = head.next moves head to 20, so the list becomes 20 -> 30 -> null.

3. Final Answer:

   20 -> 30 -> null -> Option B

4. Quick Check:

   Head moves from 10 to 20 after deletion [OK]

Hint: After deletion, head points to second node, list starts there [OK]

Common Mistakes:

• Not updating head pointer
• Assuming first node remains
• Confusing node values after deletion

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

if (head == null) {
    System.out.println("List is empty");
} else {
    head.next = head;
}

medium

A. It correctly deletes the first node

B. It throws a NullPointerException

C. It sets head to null, losing the list

D. It causes the head to point to itself, creating a cycle

Solution

1. Step 1: Analyze the assignment head.next = head

   This sets the next pointer of the first node to point back to itself, creating a cycle.

2. Step 2: Understand the impact on deletion

   The head pointer is not updated, so the first node is not removed and the list structure is broken.

3. Final Answer:

   It causes the head to point to itself, creating a cycle -> Option D

4. Quick Check:

   Incorrect pointer assignment creates cycle [OK]

Hint: Assign head = head.next to delete; avoid head.next = head [OK]

Common Mistakes:

• Confusing head.next = head with head = head.next
• Not checking for empty list before deletion
• Ignoring pointer updates causing cycles

5. You have a singly linked list with nodes: 5 -> 15 -> 25 -> 35 -> null. After deleting the first node twice using head = head.next;, what will be the final list?

hard

A. 35 -> null

B. 15 -> 25 -> 35 -> null

C. 25 -> 35 -> null

D. null

Solution

1. Step 1: Initial list and first deletion

   Start: 5 -> 15 -> 25 -> 35 -> null. After first deletion, head moves to 15, list is 15 -> 25 -> 35 -> null.

2. Step 2: Second deletion

   After second deletion, head moves to 25, list is 25 -> 35 -> null.

3. Final Answer:

   25 -> 35 -> null -> Option C

4. Quick Check:

   Two deletions remove first two nodes [OK]

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

Common Mistakes:

• Deleting only once instead of twice
• Confusing node values after multiple deletions
• Not updating head pointer correctly each time