4. Data Structure Programs – Delete Node From Unsorted LinkedList In Java

Introduction

As a part of the Data structure for Testers series, in this post, we will learn to write a Java program to delete a node from a Linked List.

Prerequisite post

Data Structure For Testers – Implement Linked List In Java

Did you know that I have started a YouTube channel as well and I need your support to make it successful. Please do watch content then comment, like, share, and obviously subscribe.

Logic to delete a node from a Linked List

To delete a node from a LinkedList we need to find it first in the list. As the given Linked List is not sorted we need to traverse the list from head to the tail node. To delete the node in a Linked list we just need to skip the reference as shown below:-

Before deleting a node

After deleting a node with data 2

If I need to delete a node with data as 2 from the list then the just previous node ( i.e. data as 3) of a node to be deleted needs to point to the next node (i.e. data as 10) of the node to be deleted.

Now we need to think of all edge and other scenarios.

Step by step logic

To traverse through a linked list we need to have a reference to the head of the linked list.

// Get a temp pointer to head node to traverse
Node cur = list.headNode;

What if the head node itself is the node to be deleted? We should check it and if it is a match then just make a new head next to the current head.

// Check if head node is node to be deleted
if(cur.data == dataToBeDeleted)
{
	list.headNode = headNode.next;
	return list;
}

If the head node is not the node to be deleted then we need to start traversing the linked list. We need to keep traversing till the end of the list or if we find the node to be deleted. We need to have another node reference to store the previous node as we need to jump/skip the reference as shown in the above pic.

Node prev = null;
while(cur != null && cur.data != dataToBeDeleted)
{
	prev = cur;
	cur = cur.next;
}

Now we can have two scenarios:- a. if the node to be deleted is not found in the linked list – If the node to be deleted is not found in the linked list then the current node will point to null after traversing. In this case, we need not do anything and simply return the existing list.

// If dataToBeDeleted is not found in list
if(cur == null)
     return list;

b. if the node to be deleted is found in the linked list then we just need to shift the next of prev reference to next of current as shown in the above image. Please note here if the node to be deleted is found in the list then reference “cur” will point to the node to be deleted.

// If data is found in the list
prev.next = cur.next;

Are we missing something? Yes! Edge cases. What if the list is empty? We just need to think of edge scenarios and handle the program as it is highly expected in interviews.

Complete Program

Node.java
package DataStructure;

/*
 * A node consists of two components. First one is data another one is a pointer to next node.
 * If a node does not point to any other node, it will be NULL or point to NULL.
 */
public class Node {

	// Data component
	int data; 
	// Pointer component
	Node next; 
	
	// A constructor to create a node
	Node(int d) 
	{ 
		data = d; 
		// Since while creating a node we can not say in advance about next node so pointer will be null
		next = null; 
	}
}
LinkedList.java
package DataStructure;

/*
 * A single linked list consists of zero or more nodes.
 * First node in LinkedList is called Head and last node in a LinkedList
 * is called a tail.
 */
public class LinkedList {

	private Node headNode; // start of list
	private Node tailNode; // end of list

	// To add a new node in LinkedList
	public LinkedList addNode(LinkedList list, int data) {
		// Create a new node with given data
		Node newNode = new Node(data);
		newNode.next = null;

		/*
		 * before adding a new node, check if list is empty. If list is empty, head and
		 * tail will be same.
		 */
		if (list.headNode == null) {
			list.headNode = newNode;
			list.tailNode = newNode;
		}
		// if list is not empty then set next of last node to new node from NULL
		// and new node will have already null from constructor
		else {
			list.tailNode.next = newNode;
			list.tailNode = newNode;
		}

		// Return the list by head
		return list;
	}

	// To print a LinkedList
	public void printList(LinkedList list) {

		// Get the hold of starting node
		Node currNode = list.headNode;
		System.out.print("Nodes in LinkedList are: ");
		// Traverse through the LinkedList till current node becomes null
		while (currNode != null) {
			// Print the data at current node
			System.out.print(currNode.data + " ");
			// Go to next node
			currNode = currNode.next;
		}
		System.out.println();
	}
	
	// To delete a node from list
	public LinkedList deleteNode(LinkedList list, int dataToBeDeleted)
	{
		// If the LinkedList is empty
		if(list.headNode == null)
			return list;
		// Get a temp pointer to head node of list to traverse
		Node cur = list.headNode;
		// Check if head node is node to be deleted
		if(cur.data == dataToBeDeleted)
		{
			list.headNode = headNode.next;
			return list;
		}
		// Another Node reference to pointer to prev node
		Node prev = null;
		/* Need to traverse to list till we reach last of list or
		 we found node to be deleted
		 */
		while(cur != null && cur.data != dataToBeDeleted)
		{
			prev = cur;
			cur = cur.next;
		}
		/* If dataToBeDeleted is not found in list
		 * then cur will point to null after traverse 
		*/
		if(cur == null)
			return list;
		/* If data is found in the list
		 * then to delete the desired node we need to skip reference
		 * of node to be deleted.
		 */
		prev.next = cur.next;
		return list;
	}

}
DeleteNodeFromLinkedList.java
package DataStructure;

public class DeleteNodeFromLinkedList {

	public static void main(String[] args) {
		// Create Linked List
		LinkedList linkedList = new LinkedList();
		linkedList.addNode(linkedList,10);
		linkedList.addNode(linkedList,12);
		linkedList.addNode(linkedList,9);
		linkedList.addNode(linkedList,4);
		linkedList.addNode(linkedList,23);
		// Print linked List
		System.out.println("Before Deleting :");
		linkedList.printList(linkedList);
		// Delete first node from list
		linkedList.deleteNode(linkedList, 10);
		System.out.println("After Deleting first node:");
		linkedList.printList(linkedList);
		linkedList.deleteNode(linkedList, 23);
		System.out.println("After Deleting last node:");
		linkedList.printList(linkedList);
		linkedList.deleteNode(linkedList, 9);
		System.out.println("After Deleting any other node:");
		linkedList.printList(linkedList);
		linkedList.deleteNode(linkedList, 90);
		System.out.println("After Deleting non existing node:");
		linkedList.printList(linkedList);
	}
}
Output
Before Deleting :
Nodes in LinkedList are: 10 12 9 4 23 
After Deleting first node:
Nodes in LinkedList are: 12 9 4 23 
After Deleting last node:
Nodes in LinkedList are: 12 9 4 
After Deleting any other node:
Nodes in LinkedList are: 12 4 
After Deleting non existing node:
Nodes in LinkedList are: 12 4 

You can download/clone the above sample project from here.

You can subscribe to my YouTube channel RetargetCommon to learn from video tutorials.

If you have any doubt, feel free to comment below.
If you like my posts, please like, comment, share and subscribe.
#ThanksForReading
#HappyLearning

Find all Selenium related posts here, all API manual and automation related posts here, and find frequently asked Java Programs here.

Many other topics you can navigate through the menu

Leave a Reply

Your email address will not be published. Required fields are marked *