Singly-linked list in java - with solved Example
Hi, Welcome to another learning lesson from AlgoMentor in this article we will learn about the linked list in java especially the singly linked list in java. We make the class in java and this particular class is for a singly linked list in java we will create different-2 method in this class we create a function for to insert an element in a singly linked list at the front, insert an element in a singly linked list at the end, insert an element in a singly linked list at the front, and insert an element in a singly linked list after particular element another three functions is dedicated to delete an element in a singly linked list at the front, back, and after a particular position. and the last two functions are for traversing and searching an element in the linked list.
What is a singly linked list?
A singly linked list is the linear data structure which consists in the form of nodes each node has two sections one section hold the data type and another section hold the address of the next node so they all forming a chain one by one.
Why linked list is preferred over an array?
In an array, we need to predefine the size and it is not possible to change array size at runtime to understand this I will give you an example suppose you are writing a software program and first you need to store the data of only 100 people so you make the array of size 100 and later on software became popular and now many users want to connect with you but now you stuck because you declare an array. But if you use a linked list instead you need not worry about it because when a new user applied to use the software then the add method of the linked list automatically creates another node for that particular user and you can grow your user base up to any number.
Another major disadvantage to using an array is if you want to insert an element in the front of the array we need to change the position of every single element of that particular array but in the linked list, you just need to update only three-link and you are good to go. suppose an array of size 10000000000 elements than just to insert a single element at the first position you need to wait for hours. But if you are using a singly linked list then it is work of microsecond (1/1000000 second). so you can now clearly see the difference.
What is the different type of linked list?
There are four different types of linked list
- Singly-linked list.
- Singly circular linked list.
- Doubly linked list.
- Double circular linked list.
What are the topics we covered in this article?
- singly linked list
- singly linked list in java
- singly linked list in java implementation
- singly linked list in java code
- singly linked list in java example
- singly linked list in the java add method
- singly linked list in java traverse
- singly linked list code in java
- singly linked list in java delete method
- create a singly linked list in java
- how to make a singly linked list in java
- application of singly linked list in java
What is five practical use of a singly linked list
- A linked list is used to make a tree data structure which is very fast for the searching compare to any other data structure like a stack, queue, or Array.
- We can create a linked stack and linked queue using a singly linked list.
- Performing arithmetics operation in the long integers.
- Dynamic Memory Allocation to create a free block in the memory and help to memory utilization.
- Next and previous button on any web page uses the concept of a linked list.
Pictorial presentation of the singly linked list.
How to create a singly linked list in java?
public class LinkedList
{
Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
This is how we create a singly link list in java this code is for How to create a singly linked list in java. in this code, we will simply create a class with the name LinkedList. and inside this class, we create a head variable of the Node type. and define Node as a static nested class of the java. in-class Node, we created a constructor and pass the integer to it when an integer is passed it construct a new node and set a value to the data section and sets the value of next pointer to null. so this is how we make a linked list in java up next we discuss all the eight methods of the linked list of add, delete, print, and search.
public static LinkedList insertFirst(LinkedList list,int data)
{
Node new_node = new Node(data);
new_node.next = null;
if(list.head==null)
{
list.head = new_node;
}
else
{
new_node.next = list.head;
list.head = new_node;
}
return list;
}
Here is the code for How to add an element in front of the singly linked list in this above code snippet we first declare a function with name insertFirst which takes two arguments one of type LinkedList (our predefine class) and another of type Integer. and return type of above function is LinkedList. in this function we make a variable of type Node for creating a Node and make the next of new_node is null and then we will check if the head of the linked list is null then we just update head of our linked list and if it not null then first we make next of new_node to the previous list head and next task is to make point old list head to our new_node hence we add another element at the front of the singly linked list.
How to add an element in the back of a singly linked list in java?
public static LinkedList insertLast(LinkedList list,int data)
{
Node new_node = new Node(data);
new_node.next = null;
if(list.head==null)
{
list.head = new_node;
}
else
{
Node last = list.head;
while(last.next!=null)
{
last=last.next;
}
last.next = new_node;
}
return list;
}
This above code is for How to add an element in the back of a singly linked list in java first thing is to create a node by making the object of Node class. then we will check if a list is empty or not if it is empty then we just need to connect the next pointer of the head to our new_node. if it is not empty then first we need to go to the end of the linked list by traversing it and when we reach the end of the linked list then update the last node next pointer and connect to our new_node.
How to add an element in the singly linked list at the particular position in java?
public static LinkedList insertPos(LinkedList list,int data,int pos)
{
Node new_node = new Node(data);
int cou=0;
new_node.next = null;
if(list.head==null)
{
System.out.println("overflow");
}
else
{
Node myPos = list.head;
pos = pos-2;
if(pos==-1)
{
list = insertFirst(list, data);
}
else
{
while(cou!=pos)
{
myPos = myPos.next;
cou++;
}
new_node.next = myPos.next;
myPos.next = new_node;
}
}
return list;
}
This code is a little bit tricky in comparison to the above two we will together understand it. in this code, we need to use a counter in the code we just need to traverse each element one by one till the counter is equal to the given position then it's time to do actual linked list operation first we connect next of our new_node to next of node at that position and then and make next of node at that position to our new_node.
How to delete an element at a first position in a singly linked list in java?
public static LinkedList deleteFirst(LinkedList list)
{
Node curr = list.head,prev = null ;
if(list.head==null)
{
System.out.println("List is already empty");
}
else
{
list.head = curr.next;
}
return list;
}
This particular method of java is for delete the first element in a singly linked list in java in this method first we check if a list is empty or not if a list is empty then we just print that "List is Empty" otherwise we only update head pointer to next element hence we remove the first element from out linked list.
How to delete an element at the last position in a singly linked list?
public static LinkedList deleteLast(LinkedList list)
{
Node curr = list.head,prev = null ;
if(list.head==null)
{
System.out.println("List is already empty");
}
else if(curr.next == null)
{
list = deleteFirst(list);
}
else
{
while(curr.next!=null)
{
prev = curr;
curr = curr.next;
}
prev.next = null;
}
return list;
}
In this scenario, we will check three conditions first condition is if the linked list is empty we just print the message that "List is already Empty" the second case is if the linked list has only one element then we just make head pointer to null hence list became empty. and the third and last case is linked list has more than one element, in that case, we will first traverse to the second last element (logic is described in the code) and than make pointer of second last element to the null and hence we can delete the last element in the linked list.
How to delete an element at a specific position in a singly linked list?
public static LinkedList deletePos(LinkedList list,int pos)
{
Node curr = list.head,prev = null ;
int cou = 0;
pos = pos-1;
if(list.head==null)
{
System.out.println("List is already empty");
}
else if(curr.next == null)
{
list = deleteFirst(list);
}
else
{
while(pos!=cou)
{
prev = curr;
curr = curr.next;
cou++;
}
prev.next = curr.next;
}
return list;
}
The above code illustrates how to delete an element at a specific position in a singly linked list. we will check three conditions first condition is if the linked list is empty we just print the message that "List is already Empty" the second case is if the linked list has only one element then we just make a head pointer to null hence list became empty and in the last case we use a counter to reach the position and when our counter equals to the position then we delete the element by making his previous element linked by his next element and after doing this the particular element is out of the chain of the singly linked list.
How to traverse a singly linked list in java?
public static void traverse(LinkedList list)
{
Node curr = list.head;
if(curr==null)
{
System.out.print("List is empty");
}
while(curr != null)
{
System.out.print(curr.data+" ");
curr = curr.next;
}
System.out.println("");
}
we use while loop to solve the problem of how to traverse a singly linked list inside while loop we put a condition while next pointer of an element did not become null till then print the data of the node and increment the node pointer by one and hence we can traverse the singly linked list in java.
How to search if an element is in the linked list or not?
public static void search(LinkedList list, int num)
{
Node curr = list.head;
boolean check = false;
if(curr==null)
{
System.out.print("List is empty ");
}
while(curr != null)
{
if(curr.data == num)
{
check = true;
}
curr = curr.next;
}
if(check == true)
{
System.out.print("we found it..");
}
else
{
System.out.print("not in the list");
}
System.out.println("");
}
The problem of searching in same as traversing a linked list we just need to use an extra flag an we make initially flag to false and if we find element while traversing we just make flag to true add when flag equal to true you can print a message like "We find it" otherwise "Element is not in linked list".
So finally we covered all the eight methods of the singly linked list hope you like our long article and if you need a whole code of linked list you can download from My Github.
Thanks for reading the article and hope you liked it I request you all to share this article with your friend who wants to learn linked list keep updated with us on social media because many tutorial like this come on the way. Happy learning 😀.
if you want to write a post on our website then please check this article on How to do a guest post.
1 Comments
nice work buddy
ReplyDelete