In this Data structures tutorial we will learn what is generic Single LinkedList in java with example and program. We will learn how to implement your own generic Single LinkedList in java. We will learn how to insert and delete at first of generic Single LinkedList in java.
What is generic Single LinkedList in java?
A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence.
Generic Single LinkedList allows us to store data of single specified type only.
Below we are going to give generic implement LinkedList without taking help of api’s provided by jdk.
What is complexity of insert and delete at first of generic Single LinkedList in java?
Complexity of insertion and deletion at first of generic Single LinkedList is O(1) in java.
Important methods used in below generic Single LinkedList program/example are as follows>
insertFirst(int data)- Inserts New Node at first of Single LinkedList in java
deleteFirst() -Deletes first Node of Single LinkedList in java
displayLinkedList() - displays Single LinkedList in java.
Logic explanation to insert and delete at first of generic Single LinkedList with diagram in java >
Let’s see how we are going to insert node at first in generic Single LinkedList in java :-
Here we see that newNode start pointing to old first and first start pointing to newNode.
Let’s see how we are going delete first node from generic Single LinkedList in java:--
Here we make first point to first.next and there is no live reference to node with data=11(i.e. deleted node), so this node becomes eligible for garbage collection by JVM as well.
Full Program/Example of insert and delete at first of generic Single LinkedList in java >
/**
*Exception to indicate that generic Single 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<T> {
public T data; // data in Node.
public Node<T> next; // points to next Node in list.
/**
* Constructor
*/
public Node(T data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* generic Single LinkedList class (Generic implementation)
*/
class LinkedList<T> {
private Node<T> first; // ref to first link on list
/**
* generic Single LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position of generic Single LinkedList
*/
public void insertFirst(T data) {
Node<T> newNode = new Node<T>(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
/**
* Deletes first Node of generic Single LinkedList
*/
public Node<T> deleteFirst()
{
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
Node<T> tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
first = first.next; // delete first Node (make first point to second node)
return tempNode; // return tempNode (i.e. deleted Node)
}
/**
* Display generic Single LinkedList
*/
public void displayLinkedList() {
System.out.print("Displaying LinkedList [first--->last]: ");
Node<T> 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 */
/**
* Main class - To test generic Single LinkedList .
*/
public class GenericSingleLinkedListInsertDeleteFirstExample {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<Integer>(); // creation of Linked List
linkedList.insertFirst(11);
linkedList.insertFirst(21);
linkedList.insertFirst(59);
linkedList.insertFirst(14);
linkedList.insertFirst(39);
linkedList.displayLinkedList(); // display LinkedList
System.out.print("Deleted Nodes: ");
Node<Integer> deletedNode = linkedList.deleteFirst(); //delete Node
deletedNode.displayNode(); //display deleted Node.
deletedNode = linkedList.deleteFirst(); //delete Node.
deletedNode.displayNode(); //display deleted Node.
System.out.println();// sysout used to format output
linkedList.displayLinkedList(); //Again display LinkedList
}
}
/*OUTPUT
Displaying LinkedList [first--->last]: 39 14 59 21 11
Deleted Nodes: 39 14
Displaying LinkedList [first--->last]: 59 21 11
*/
|
Complexity of insert and delete at first in generic Single LinkedList in java >
Complexity of insertion and deletion at first in generic Single LinkedList is O(1).
As we have to insert at first> best case, average case and worst case are same 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
