# 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
```

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)
{
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;
}
}
```
```package DataStructure;

/*
* A single linked list consists of zero or more nodes.
* is called a tail.
*/

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

// 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.
*/
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;
}

// Get the hold of starting node
// 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
{
// If the LinkedList is empty
return list;
// Get a temp pointer to head node of list to traverse
// Check if head node is node to be deleted
if(cur.data == dataToBeDeleted)
{
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;
}
* 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;
}

}
```
```package DataStructure;

public static void main(String[] args) {
System.out.println("Before Deleting :");
// Delete first node from list
System.out.println("After Deleting first node:");
System.out.println("After Deleting last node:");
System.out.println("After Deleting any other node:");
System.out.println("After Deleting non existing node:");
}
}
```
###### 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
```