Implementation of Singly linked list in Java
In this guide, you will learn how to implement a Singly linked list in Java. You will also learn about the operations that we can possibly perform with the Singly linked list.
Implementation of Singly linked list in java
Before we start with the implementation, let's understand what a singly linked list is. A singly linked list is a data structure that can be traversed in only one direction. and the direction moves from the head to the tail (last node). Simply put, it is unidirectional. In a linked list, each element is known as a node. each node contains data and a pointer. The pointer can be used to refer to the next node and helps in sustaining the structure of the list. The linked list has a head and a tail node too. Head, also known as the first node, points to the first node of the list. Tail, also known as the last node, points to null which tells us when the list ends.
Since we know briefly what a singly linked list is, Let's look at the operations in a singly linked list. There are various operations that can be performed on a singly linked list, some are as follows:
Insertion in a singly linked list
based on the position at which you are inserting a node, insertion can be of mainly three types which are listed below:
1. Insertion at the beginning:
In insertion at beginning of the singly linked list, Element is inserted at the front of the list. Here, we have created a function to insert an element at the beginning in Java.
public void insrtatstart(int val)
{
linkedlist nptr= new linkedlist(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setlk(start);
start = nptr;
}
}
2. Insertion at the end:
In this type of insertion, the element is inserted as the last one or as the only node in the list. In the code given below, we have created a function to insert an element at the end of the singly linked list, using Java code.
public void insrtatend(int val)
{
linkedlist nptr = new linkedlist(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setlk(nptr);
end = nptr;
}
}
3. Insertion after a given node:
In this case, you are required to skip a number of nodes to reach the node. In the code given below, we have created a function to insert at a particular position which inserts a new node after the given previous node.
public void insrtatposn(int val , int pos)
{
linkedlist nptr = new linkedlist(val, null);
linkedlist ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
linkedlist tmp = ptr.getln() ;
ptr.setlk(nptr);
nptr.setlk(tmp);
break;
}
ptr = ptr.getln();
}
size++ ;
}
after insertion, the next major operation is deletion and traversal.
Deletion and traversal in the Singly linked list
Based on the position from which you wish to delete a node, deletion can be done in the following ways:
- Deletion at the beginning - deletes a node at the top or first of the list.
- Deletion at the end of the list - deletes the last node of the list. Note that the list can be empty too. Each case has a different logic.
- Deletion after a given node: if you are required to delete after a particular node, we need to skip some nodes to reach the node we need to delete. Traversal can be used to achieve this.
public void delatposn(int pos)
{
if (pos == 1)
{
start = start.getln();
size--;
return ;
}
if (pos == size)
{
linkedlist s = start;
linkedlist t = start;
while (s != end)
{
t = s;
s = s.getln();
}
end = t;
end.setlk(null);
size --;
return;
}
linkedlist ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
linkedlist tmp = ptr.getln();
tmp = tmp.getln();
ptr.setlk(tmp);
break;
}
ptr = ptr.getln();
}
size-- ;
}
Display elements in a Singly linked list
As the name suggests, display() will show the nodes in the list. The process begins by defining a node current which initially points to the head of the list. then, it traverses through the list until the null value is reached in the list. Finally, each node is displayed by making current to point to the node next to it in each cycle/iteration.
In the java code given below, we have defined a function display() to show the elements present in the singly linked list.
public void display()
{
System.out.print("\nSingly Linked List: ");
if (size == 0)
{
System.out.print("List is currently empty\n");
return;
}
if (start.getln() == null)
{
System.out.println(start.getdt() );
return;
}
linkedlist ptr = start;
System.out.print(start.getdt()+ ">");
ptr = start.getln();
while (ptr.getln() != null)
{
System.out.print(ptr.getdt()+ ">");
ptr = ptr.getln();
}
System.out.print(ptr.getdt()+ "\n");
}
To get the size of the Singly linked list
To check the size of the linked list, you can use the size method. You can get the size of the linked list and compare it with zero to know the size of the linked list. Here, we have taken a function getsz() and we return the size of the linked list.
public int getsz()
{
return size;
}
To check if the list is empty
To check whether the linked list is empty, you can use the isEmpty method. If the linked list object is empty, the isEmpty method returns True. One thing to note is that isEmpty method returns only a Boolean value implying if the linked list is empty or not. In the code snippet given below, we have taken a function isEmpty() which tells us if the list is empty with True or False.
public boolean isEmpty()
{
return start == null;
}
Now that we have learned about the operations possible in the singly linked list, let’s implement singly linked list and these operations and design a menu-driven code in Java.
FULL code:
/* Java Program to Implement Singly Linked List in Java */
import java.util.Scanner ;
class linkedlist
{
protected int data;
protected linkedlist link;
/* Constructor */
public linkedlist()
{
link = null;
data = 0;
}
public linkedlist(int d, linkedlist n)
{
data = d;
link = n;
}
public void setlk(linkedlist n)
{
link = n;
}
public void setData(int d)
{
data = d;
}
public linkedlist getln()
{
return link;
}
public int getdt()
{
return data;
}
}
class llist
{
protected linkedlist start;
protected linkedlist end ;
public int size ;
public llist()
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty()
{
return start == null;
}
public int getsz()
{
return size;
}
public void insrtatstart(int val)
{
linkedlist nptr= new linkedlist(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setlk(start);
start = nptr;
}
}
public void insrtatend(int val)
{
linkedlist nptr = new linkedlist(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setlk(nptr);
end = nptr;
}
}
public void insrtatposn(int val , int pos)
{
linkedlist nptr = new linkedlist(val, null);
linkedlist ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
linkedlist tmp = ptr.getln() ;
ptr.setlk(nptr);
nptr.setlk(tmp);
break;
}
ptr = ptr.getln();
}
size++ ;
}
public void delatposn(int pos)
{
if (pos == 1)
{
start = start.getln();
size--;
return ;
}
if (pos == size)
{
linkedlist s = start;
linkedlist t = start;
while (s != end)
{
t = s;
s = s.getln();
}
end = t;
end.setlk(null);
size --;
return;
}
linkedlist ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
linkedlist tmp = ptr.getln();
tmp = tmp.getln();
ptr.setlk(tmp);
break;
}
ptr = ptr.getln();
}
size-- ;
}
public void display()
{
System.out.print("\nSingly Linked List: ");
if (size == 0)
{
System.out.print("List is currently empty\n");
return;
}
if (start.getln() == null)
{
System.out.println(start.getdt() );
return;
}
linkedlist ptr = start;
System.out.print(start.getdt()+ ">");
ptr = start.getln();
while (ptr.getln() != null)
{
System.out.print(ptr.getdt()+ ">");
ptr = ptr.getln();
}
System.out.print(ptr.getdt()+ "\n");
}
}
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
llist list = new llist();
System.out.println("Test Singly Linked List\n");
char c;
/* Perform list operations */
do
{
System.out.println("\n ----- || Singly Linked List Operations || -----\n");
System.out.println("1. insert at beginning");
System.out.println("2. insert at end");
System.out.println("3. insert at a specific position");
System.out.println("4. delete at specific position");
System.out.println("5. check if the list is empty");
System.out.println("6. get size of the list");
int ch = scan.nextInt();
switch (ch)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insrtatstart(scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insrtatend(scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter the position where you want to insert element: ");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getsz() )
System.out.println("Invalid position\n");
else
list.insrtatposn(num, pos);
break;
case 4 :
System.out.println("Enter position of the element you want to delete");
int p = scan.nextInt() ;
if (p < 1 || p > list.getsz() )
System.out.println("Error\n");
else
list.delatposn(p);
break;
case 5 :
System.out.println("Is the list empty? (True or False) "+ list.isEmpty());
break;
case 6 :
System.out.println("The size of the list is: "+ list.getsz() +" \n");
break;
default :
System.out.println("Sorry! Please enter a valid input.\n ");
break;
}
/* Display List */
list.display();
System.out.println("\n Press 'y' to continue or press 'n' to skip\n");
c = scan.next().charAt(0);
} while ( c == 'Y'|| c == 'y');
}
}
And voila! You have designed and implemented singly-linked lists using Java!
Submitted by KHYATI MADDALI (khyatimaddali)
Download packets of source code on Coders Packet
Comments