In this Data structures tutorial we will learn what is Singly LinkedList in java with example and program. We will learn how to implement your own Singly LinkedList in java. We will learn how to delete specific nodes from Singly LinkedList in java. We will also learn complexity of deleting specific nodes from Singly LinkedList in java.
Below implementation of Singly LinkedList helps us in deleting specific node from Singly LinkedList in java.
What is complexity of deleting specific nodes from Singly LinkedList in java?
Complexity of deleting specific nodes from Singly LinkedList is O(n).
Important methods used in below Singly LinkedList program/example are as follows>
deleteSpecificNode(int data)- Method deletes specified Node from Singly LinkedList in java.
Logic explanation of deleting specific nodes from Singly LinkedList in java with diagram >
Let’s see how we are going delete specific node from Singly LinkedList in java:-
Here as soon as we detect that current is the node to be deleted we make
>previous node’s next point to current’s next, doing so makes node pointed by current eligible for garbage collection.
Full Program/Example of deleting specific nodes from Singly LinkedList in java>
/**
*Exception to indicate that Singly LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException{
public LinkedListEmptyException(){
super();
}
public LinkedListEmptyException(String message){
super(message);
}
}
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* Singly LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on list
/**
* LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position
*/
public void insertFirst(int data) {
Node newNode = new Node(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
/**
* Method deletes specific Node from Singly LinkedList in java.
*/
public Node deleteSpecificNode(int deleteKey){
//Case1: when there is no element in LinkedList
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
//Case2: when there is only one element in LinkedList- check whether we have to delete that Node or not.
if(first.data==deleteKey){ //means LinkedList consists of only one element, delete that.
Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
first=first.next;
System.out.println("Node with data="+tempNode.data+" was found on first and has been deleted.");
return tempNode; //return deleted Node.
}
//Case3: when there are atLeast two elements in LinkedList
Node previous=null;
Node current=first;
while(current!=null){
if(current.data==deleteKey){
System.out.println("Node with data="+current.data+" has been deleted.");
previous.next=current.next; //make previous node's next point to current node's next.
return current; //return deleted Node.
}
else{
if(current.next==null){ //Means Node wasn't found.
System.out.println("Node with data="+deleteKey+" wasn't found for deletion.");
return null;
}
previous=current;
current=current.next; //move to next node.
}
}
return null;
}
/**
* Display Singly LinkedList
*/
public void displayLinkedList() {
System.out.print("Displaying LinkedList [first--->last]: ");
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don't find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();
}
}
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
/**
* SinglyLinkedListDeleteNodeExample - Main class - To test LinkedList.
*/
public class SinglyLinkedListDeleteNodeExample {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList(); // creation of Linked List
linkedList.insertFirst(92);
linkedList.insertFirst(20);
linkedList.insertFirst(19);
linkedList.insertFirst(29);
linkedList.displayLinkedList(); // display LinkedList
linkedList.deleteSpecificNode(29);
linkedList.deleteSpecificNode(11);
linkedList.displayLinkedList(); //Again display LinkedList
}
}
/*OUTPUT
Displaying LinkedList [first--->last]: 29 19 20 92
Node with data=92 has been deleted.
Node with data=11 wasn't found for deletion.
Displaying LinkedList [first--->last]: 29 19 20
*/
|
Complexity of deleting specific nodes from Singly LinkedList in java -
Best Case : O(1), when node to be deleted is at first of Singly LinkedList in java.
Average Case : O(n)
Worst Case : O(n)
In this Data structures tutorial we learned what is Singly LinkedList in java with example and program. We learned how to implement your own Singly LinkedList in java. We learned how to delete specific nodes from Singly LinkedList in java. We also learned complexity of deleting specific nodes from Singly LinkedList in java.
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>
1) Stacks, Queues in Data Structures in java
2) Single LinkedList implementations in Data Structures in java:-
>
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList
5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java
6) Binary tree tutorial in java >