Delete Node by Value in DSA Java - Deep Dive

Overview - Delete Node by Value

What is it?

Deleting a node by value means removing the first node in a linked list that contains a specific value. A linked list is a chain of nodes where each node holds data and a link to the next node. When we delete a node by value, we find the node with that value and remove it without breaking the chain. This operation changes the structure by skipping over the removed node.

Why it matters

Without the ability to delete nodes by value, linked lists would grow endlessly or require complex rebuilding to remove unwanted data. This operation allows dynamic updates to data collections, like removing a friend from a contact list or deleting a task from a to-do list. It keeps data structures flexible and efficient in real-world applications.

Where it fits

Before learning this, you should understand what linked lists are and how nodes connect. After mastering deletion by value, you can learn about other linked list operations like insertion at positions, reversing lists, or deleting nodes by position.

Mental Model

Core Idea

Deleting a node by value means finding the node with that value and changing the previous node's link to skip it, effectively removing it from the chain.

Think of it like...

Imagine a paper chain where each paper ring links to the next. To remove a ring with a certain color, you find the ring before it and connect that ring directly to the one after, cutting out the unwanted ring without breaking the chain.

Head -> [Node1|Next] -> [Node2|Next] -> [Node3|Next] -> null

If Node2 has the value to delete:
Change Node1's Next to point to Node3, skipping Node2.

Result:
Head -> [Node1|Next] -> [Node3|Next] -> null

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect through links.

A linked list is a sequence of nodes. Each node has two parts: data (the value it holds) and a reference (link) to the next node. The list starts at a special node called the head. The last node points to null, meaning the end of the list.

Result

You can visualize a linked list as a chain of connected boxes, each holding a value and a pointer to the next box.

Understanding the basic structure of linked lists is essential because deletion changes how these links connect.

2

Foundation

Traversing a Linked List

Concept: Learn how to move through a linked list node by node.

To find a node, start at the head and follow each node's link to the next until you find the target value or reach the end (null). This process is called traversal.

Result

You can visit every node in order, checking each node's value.

Traversal is the foundation for deletion because you must find the node to remove.

3

Intermediate

Deleting the Head Node by Value

🤔Before reading on: If the head node has the value to delete, do you think you need to change the head pointer or just skip the node?

Concept: Deleting the first node requires updating the head pointer to the next node.

If the head node contains the value to delete, you remove it by making the head point to the second node. This effectively removes the first node from the list.

Result

The list starts from the second node, and the original head is no longer linked.

Knowing that the head pointer must be updated prevents losing access to the list after deletion.

4

Intermediate

Deleting a Middle or Last Node by Value

🤔Before reading on: When deleting a node in the middle, do you think you remove the node itself or just change the previous node's link?

Concept: To delete a node in the middle or end, change the previous node's link to skip the target node.

While traversing, keep track of the previous node. When you find the node with the target value, set previous node's next to current node's next. This skips the current node, removing it from the chain.

Result

The node with the target value is removed, and the list remains connected.

Understanding that you only change links, not the nodes themselves, keeps the list intact.

5

Intermediate

Handling Value Not Found Cases

🤔Before reading on: If the value is not in the list, do you think the list changes or stays the same?

Concept: If the value is not found, the list remains unchanged.

Traverse the list fully. If no node matches the value, do nothing. The list stays as it was.

Result

No deletion occurs, and the list is unchanged.

Recognizing this prevents accidental changes or errors when the value is missing.

6

Advanced

Implementing Delete Node by Value in Java

🤔Before reading on: Do you think the deletion method should return a boolean, the new head, or nothing? Commit to your answer.

Concept: Implement deletion by value in Java, handling all cases and returning the updated head.

public class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } public class LinkedList { Node head; public Node deleteByValue(int value) { if (head == null) return head; if (head.data == value) { return head.next; // delete head } Node current = head; while (current.next != null && current.next.data != value) { current = current.next; } if (current.next != null) { current.next = current.next.next; // skip node } return head; } }

Result

The method removes the first node with the given value and returns the possibly new head.

Knowing to return the head allows handling deletion of the first node cleanly.

7

Expert

Edge Cases and Performance Considerations

🤔Before reading on: Do you think deleting by value in a singly linked list is always fast? Commit to yes or no.

Concept: Explore edge cases like empty lists, multiple nodes with the same value, and performance limits.

Deleting by value requires traversal, which takes time proportional to list length (O(n)). If multiple nodes have the value, only the first is deleted. Deleting in an empty list does nothing. For large lists, consider data structures with faster deletion like doubly linked lists or hash maps.

Result

You understand when deletion is efficient and when it might slow down.

Knowing these limits helps choose the right data structure for your needs.

Under the Hood

Internally, each node stores a reference to the next node. Deletion by value works by changing the 'next' reference of the previous node to point to the node after the one being deleted. This removes the target node from the chain, allowing it to be garbage collected if no other references exist.

Why designed this way?

Singly linked lists use simple references to save memory and allow easy insertion and deletion. Changing links instead of copying data keeps operations efficient. Alternatives like arrays require shifting elements, which is slower.

Head -> [Node1|Next] -> [Node2|Next] -> [Node3|Next] -> null

To delete Node2:

Head -> [Node1|Next] ---------> [Node3|Next] -> null
                  (skip Node2)

Myth Busters - 4 Common Misconceptions

Quick: Does deleting a node by value remove all nodes with that value or just the first? Commit to your answer.

Common Belief: Deleting by value removes all nodes with that value.

Reality: Only the first node with the matching value is deleted in a standard implementation.

Why it matters: Expecting all nodes to be deleted can cause bugs where unwanted duplicates remain.

Quick: If the node to delete is the head, do you think you can just set head.next to null? Commit to yes or no.

Common Belief: You can delete the head by setting head.next to null.

Reality: You must update the head pointer itself to head.next; setting head.next to null only disconnects the rest of the list.

Why it matters: Incorrect deletion of head breaks the list and loses access to remaining nodes.

Quick: Does deleting a node by value require shifting all nodes after it? Commit to yes or no.

Common Belief: Deleting a node requires shifting all subsequent nodes to fill the gap.

Reality: No shifting is needed; only the previous node's link changes to skip the deleted node.

Why it matters: Misunderstanding this leads to inefficient code and confusion about linked list operations.

Quick: Can you delete a node by value without knowing the previous node? Commit to yes or no.

Common Belief: You can delete a node by value without tracking the previous node.

Reality: In singly linked lists, you must track the previous node to change its link; otherwise, you cannot remove the target node.

Why it matters: Not tracking the previous node causes inability to remove nodes properly.

Expert Zone

1

Deleting the head node requires special handling because it changes the entry point to the list.

2

In singly linked lists, you cannot delete a node if you only have a reference to that node; you need the previous node to update links.

3

Repeated values require careful design if you want to delete all occurrences, which is not handled by a simple delete-by-value method.

When NOT to use

Deleting by value in singly linked lists is inefficient for large lists or frequent deletions. Alternatives include doubly linked lists for easier backward traversal or balanced trees and hash tables for faster search and deletion.

Production Patterns

In real systems, delete-by-value is often combined with search optimizations or replaced by data structures with direct access. For example, in caches or databases, keys are used for quick deletion rather than scanning linked lists.

Connections

Hash Tables

Builds-on

Understanding linked list deletion helps grasp how hash tables handle collisions using chaining, where linked lists store multiple values per bucket.

Garbage Collection

Supports

Deleting nodes by changing links allows unreferenced nodes to be cleaned up automatically by garbage collection, preventing memory leaks.

Supply Chain Management

Analogous process

Removing a node by value is like removing a supplier from a supply chain by redirecting orders to the next supplier, ensuring the chain continues smoothly.

Common Pitfalls

#1 Not updating the head pointer when deleting the first node.

Wrong approach:

if (head.data == value) {
head.next = head.next.next; // wrong: head pointer unchanged
}

Correct approach:

if (head.data == value) {
head = head.next; // correct: head pointer updated
}

Root cause:

Confusing the head node's link with the head pointer itself.

#2 Trying to delete a node without tracking the previous node.

Wrong approach:

Node current = head;
while (current != null) {
if (current.data == value) {
current = current.next; // wrong: does not remove node from list
break;
}
current = current.next;
}

Correct approach:

Node current = head;
Node prev = null;
while (current != null) {
if (current.data == value) {
if (prev != null) {
prev.next = current.next;
} else {
head = current.next;
}
break;
}
prev = current;
current = current.next;
}

Root cause:

Not realizing that changing the current pointer alone does not remove the node from the linked list.

#3 Assuming all nodes with the value are deleted by one call.

Wrong approach:

public void deleteByValue(int value) {
Node current = head;
Node prev = null;
while (current != null) {
if (current.data == value) {
if (prev != null) prev.next = current.next;
else head = current.next;
break; // stops after first deletion
}
prev = current;
current = current.next;
}
}

Correct approach:

public void deleteAllByValue(int value) {
while (head != null && head.data == value) {
head = head.next;
}
Node current = head;
while (current != null && current.next != null) {
if (current.next.data == value) {
current.next = current.next.next;
} else {
current = current.next;
}
}
}

Root cause:

Not handling multiple occurrences requires looping through the entire list.

Key Takeaways

Deleting a node by value in a linked list means changing the previous node's link to skip the target node, effectively removing it.

Special care is needed when deleting the head node because it changes the starting point of the list.

Only the first node with the matching value is deleted unless explicitly coded to remove all occurrences.

Tracking the previous node during traversal is essential to update links correctly.

Understanding deletion by value helps in grasping more complex data structures and real-world applications where dynamic data removal is needed.

Practice

1. What is the main purpose of the Delete Node by Value operation in a linked list?

easy

A. Reverse the linked list

B. Add a new node with the given value to the end of the list

C. Find the position of the node with the given value

D. Remove the first node that contains the given value from the list

Solution

1. Step 1: Understand the operation goal

   The operation aims to remove a node that matches a specific value from the linked list.

2. Step 2: Identify the correct description

   Removing the first node with the given value matches Remove the first node that contains the given value from the list, while other options describe different operations.

3. Final Answer:

   Remove the first node that contains the given value from the list -> Option D

4. Quick Check:

   Delete Node by Value = Remove matching node [OK]

Hint: Deleting by value means removing matching node, not adding [OK]

Common Mistakes:

• Confusing delete with add operation
• Thinking it finds position instead of deleting
• Assuming it reverses the list

2. Which of the following is the correct Java syntax to start deleting a node by value from a singly linked list named head with value val?

easy

A. Node current = head; while(current != null && current.value != val) { current = current.next; }

B. Node current = head; while(current.value != val) { current = current.next; }

C. Node current = head; while(current.next != null && current.next.value != val) { current = current.next; }

D. Node current = head; if(current.value == val) { head = head.next; }

Solution

1. Step 1: Understand traversal to find node before target

   To delete a node by value, we need to find the node before the target node to change its next pointer.

2. Step 2: Check which loop finds the previous node

   Node current = head; while(current.next != null && current.next.value != val) { current = current.next; } correctly loops while current.next is not null and its value is not the target, so current stops at the node before the target.

3. Final Answer:

   Node current = head; while(current.next != null && current.next.value != val) { current = current.next; } -> Option C

4. Quick Check:

   Find previous node with current.next check = Node current = head; while(current.next != null && current.next.value != val) { current = current.next; } [OK]

Hint: Loop to node before target uses current.next, not current [OK]

Common Mistakes:

• Checking current.value instead of current.next.value
• Not handling head node deletion separately
• Using while loop without null check causing errors

3. What will be the output linked list after deleting the node with value 3 from the list: 1 -> 2 -> 3 -> 4 -> null?

medium

A. 1 -> 2 -> 4 -> null

B. 1 -> 3 -> 4 -> null

C. 2 -> 3 -> 4 -> null

D. 1 -> 2 -> 3 -> 4 -> null

Solution

1. Step 1: Locate node with value 3

   The node with value 3 is the third node in the list: 1 -> 2 -> 3 -> 4 -> null.

2. Step 2: Remove node with value 3 by linking previous to next

   We link node with value 2 directly to node with value 4, skipping the node with value 3.

3. Final Answer:

   1 -> 2 -> 4 -> null -> Option A

4. Quick Check:

   Deleted node 3, list skips it = 1 -> 2 -> 4 -> null [OK]

Hint: Skip node with value by linking previous to next [OK]

Common Mistakes:

• Not updating links, leaving deleted node in list
• Deleting wrong node by value
• Confusing node values and positions

4. Consider this Java code snippet to delete a node by value from a singly linked list:

Node current = head;
while(current.next != null && current.next.value != val) {
    current = current.next;
}
if(current.next.value == val) {
    current.next = current.next.next;
}

What error can occur when deleting the node if the value val is not present in the list?

medium

A. NullPointerException at current.next.value

B. IndexOutOfBoundsException at current.next.next

C. Compilation error due to missing semicolon

D. No error, deletion works fine

Solution

1. Step 1: Analyze loop exit condition

   The loop stops when current.next == null or current.next.value == val. If val is not found, current.next becomes null.

2. Step 2: Check the if condition usage

   The code checks current.next.value == val without verifying if current.next is null, causing NullPointerException if val is missing.

3. Final Answer:

   NullPointerException at current.next.value -> Option A

4. Quick Check:

   Accessing value of null next node causes NullPointerException [OK]

Hint: Always check for null before accessing next.value [OK]

Common Mistakes:

• Assuming node always found, skipping null check
• Confusing runtime exceptions with compile errors
• Ignoring loop exit conditions

5. Given a singly linked list head with nodes 10 -> 20 -> 30 -> 40 -> 50 -> null, what will be the list after deleting the node with value 10 (the head node)?

hard

A. null

B. 20 -> 30 -> 40 -> 50 -> null

C. 30 -> 40 -> 50 -> null

D. 10 -> 20 -> 30 -> 40 -> 50 -> null

Solution

1. Step 1: Identify head node deletion case

   The node to delete is the head node with value 10, so we must update head to point to the next node.

2. Step 2: Update head pointer to next node

   Set head = head.next, which points to node with value 20, effectively removing the original head.

3. Final Answer:

   20 -> 30 -> 40 -> 50 -> null -> Option B

4. Quick Check:

   Deleting head means head moves to next node [OK]

Hint: Deleting head means move head pointer to next node [OK]

Common Mistakes:

• Not updating head pointer when deleting first node
• Removing wrong node by mistake
• Assuming list becomes empty after head deletion