Table of Contents
Delete a Node from a Linked List in Java — Step by Step Explanation
Delete a Node from a Linked List in Java — Step by Step Explanation
In this article, we will break the linked list deletion program into multiple small programs so that students can understand the concept slowly and clearly.
The final goal is to learn how to delete a node from a linked list.
Step 1: Understanding the Node Class
A linked list is made up of nodes. Each node contains two parts:
- data — stores the value
- link — stores the reference of the next node
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class TestNode {
public static void main(String[] args) {
Node n = new Node(10);
System.out.println("Data: " + n.data);
System.out.println("Link: " + n.link);
}
}Explanation
Here, one node is created with the value 10. Since it is not connected to any other node, its link is null.
Step 2: Creating a Simple Linked List
A linked list needs a starting point. This starting point is usually called start.
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
LinkedList() {
start = null;
}
boolean isEmpty() {
return start == null;
}
}
class TestList {
public static void main(String[] args) {
LinkedList list = new LinkedList();
if (list.isEmpty()) {
System.out.println("List is empty");
}
}
}Explanation
If start is null, it means the linked list has no node.
Deleting a node from an empty list is called underflow.
Step 3: Inserting Nodes into the Linked List
Before deleting a node, we need some nodes in the list. Here, we insert nodes at the end of the list.
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (start == null) {
start = newNode;
return;
}
Node ptr = start;
while (ptr.link != null) {
ptr = ptr.link;
}
ptr.link = newNode;
}
void display() {
Node ptr = start;
while (ptr != null) {
System.out.print(ptr.data + " -> ");
ptr = ptr.link;
}
System.out.println("NULL");
}
}
class TestInsert {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtEnd(5);
list.insertAtEnd(2);
list.insertAtEnd(7);
list.display();
}
}Output
5 -> 2 -> 7 -> NULLStep 4: Deleting the First Node
If the node to be deleted is the first node, then start should move to the second node.
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (start == null) {
start = newNode;
return;
}
Node ptr = start;
while (ptr.link != null) {
ptr = ptr.link;
}
ptr.link = newNode;
}
boolean deleteFirst(int value) {
if (start == null) {
return false;
}
if (start.data == value) {
start = start.link;
return true;
}
return false;
}
void display() {
Node ptr = start;
while (ptr != null) {
System.out.print(ptr.data + " -> ");
ptr = ptr.link;
}
System.out.println("NULL");
}
}
class TestDeleteFirst {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtEnd(5);
list.insertAtEnd(2);
list.insertAtEnd(7);
list.deleteFirst(5);
list.display();
}
}Output
2 -> 7 -> NULLExplanation
Before deletion:
5 -> 2 -> 7 -> NULL
After deleting 5, start points to the next node.
2 -> 7 -> NULLStep 5: Deleting a Middle Node
To delete a middle node, we need two references:
ptr— points to the current nodesave— points to the previous node
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (start == null) {
start = newNode;
return;
}
Node ptr = start;
while (ptr.link != null) {
ptr = ptr.link;
}
ptr.link = newNode;
}
boolean deleteMiddle(int value) {
if (start == null) {
return false;
}
Node save = start;
Node ptr = start.link;
while (ptr != null) {
if (ptr.data == value) {
save.link = ptr.link;
return true;
}
save = ptr;
ptr = ptr.link;
}
return false;
}
void display() {
Node ptr = start;
while (ptr != null) {
System.out.print(ptr.data + " -> ");
ptr = ptr.link;
}
System.out.println("NULL");
}
}
class TestDeleteMiddle {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtEnd(5);
list.insertAtEnd(2);
list.insertAtEnd(7);
list.insertAtEnd(4);
list.deleteMiddle(7);
list.display();
}
}Output
5 -> 2 -> 4 -> NULLExplanation
Before deletion:
5 -> 2 -> 7 -> 4 -> NULL
To delete 7, the link of node 2 is changed to point to node 4.
5 -> 2 -> 4 -> NULLStep 6: Complete Delete Method
Now we combine both cases:
- Deleting the first node
- Deleting a middle or last node
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
LinkedList() {
start = null;
}
boolean isEmpty() {
return start == null;
}
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (start == null) {
start = newNode;
return;
}
Node ptr = start;
while (ptr.link != null) {
ptr = ptr.link;
}
ptr.link = newNode;
}
boolean delete(int value) {
boolean result = false;
if (start == null) {
return false;
}
if (start.data == value) {
start = start.link;
result = true;
} else {
Node save = start;
Node ptr = start.link;
while (ptr != null) {
if (ptr.data == value) {
save.link = ptr.link;
result = true;
break;
} else {
save = ptr;
ptr = ptr.link;
}
}
}
return result;
}
void display() {
Node ptr = start;
while (ptr != null) {
System.out.print(ptr.data + " -> ");
ptr = ptr.link;
}
System.out.println("NULL");
}
}
class TestDelete {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtEnd(5);
list.insertAtEnd(2);
list.insertAtEnd(7);
list.insertAtEnd(4);
list.insertAtEnd(9);
list.delete(5);
list.display();
}
}Output
2 -> 7 -> 4 -> 9 -> NULLStep 7: Complete Program with User Input
This program creates a linked list with five numbers and then deletes a number entered by the user.
import java.io.*;
class Node {
int data;
Node link;
Node(int d) {
data = d;
link = null;
}
}
class LinkedList {
Node start;
LinkedList() {
start = null;
}
boolean isEmpty() {
return start == null;
}
void insertAtEnd(int value) {
Node newNode = new Node(value);
if (start == null) {
start = newNode;
return;
}
Node ptr = start;
while (ptr.link != null) {
ptr = ptr.link;
}
ptr.link = newNode;
}
boolean delete(int value) {
boolean result = false;
if (start == null) {
return false;
}
if (start.data == value) {
start = start.link;
result = true;
} else {
Node save = start;
Node ptr = start.link;
while (ptr != null) {
if (ptr.data == value) {
save.link = ptr.link;
result = true;
break;
} else {
save = ptr;
ptr = ptr.link;
}
}
}
return result;
}
void display() {
Node ptr = start;
while (ptr != null) {
System.out.print(ptr.data + " -> ");
ptr = ptr.link;
}
System.out.println("NULL");
}
}
class LinkedListTest {
public static void main(String[] args) throws IOException {
int num;
LinkedList list = new LinkedList();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Starting List Test for DELETION");
for (int i = 0; i < 5; i++) {
System.out.print("Enter a number: ");
num = Integer.parseInt(br.readLine());
list.insertAtEnd(num);
}
System.out.print("Enter number to be deleted: ");
num = Integer.parseInt(br.readLine());
boolean result = list.delete(num);
if (result == true) {
System.out.println(num + " deleted successfully.");
} else {
System.out.println("Sorry! No such number found in list.");
}
System.out.println("Now the List is:");
list.display();
System.out.println("List Test Over");
}
}Sample Output
Starting List Test for DELETION
Enter a number: 5
Enter a number: 2
Enter a number: 7
Enter a number: 4
Enter a number: 9
Enter number to be deleted: 5
5 deleted successfully.
Now the List is:
2 -> 7 -> 4 -> 9 -> NULL
List Test OverHow Deletion Works
Suppose the linked list is:
5 -> 2 -> 7 -> 4 -> 9 -> NULL
If we delete 5, the first node is removed and start points to the next node.
2 -> 7 -> 4 -> 9 -> NULL
If we delete 7, the previous node 2 is linked directly with 4.
5 -> 2 -> 4 -> 9 -> NULLImportant Concepts Used
- Node creation
- Linked list traversal
- Checking underflow condition
- Deleting the first node
- Deleting a middle node
- Updating links between nodes
- Using boolean return value
Recommended Teaching Sequence
- Explain the structure of a node
- Explain the role of
start - Insert some nodes into the list
- Display the linked list
- Delete the first node
- Delete a middle node
- Combine all logic into one delete method
- Take input from the user and test the program
Key Learning
Deleting a node from a linked list does not mean physically shifting elements like an array. Instead, we change links between nodes.
If the first node is deleted, start is updated. If a middle or last node is deleted, the previous node is connected to the next node.