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.
|
1 2 |
// 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.
|
1 2 3 4 5 6 |
// 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.
|
1 2 3 4 5 6 |
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.
|
1 2 3 |
// 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.
|
1 2 |
// 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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
|
1 2 3 4 5 6 7 8 9 10 |
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
