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.
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:
based on the position at which you are inserting a node, insertion can be of mainly three types which are listed below:
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; } }
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; } }
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.
Based on the position from which you wish to delete a node, deletion can be done in the following ways:
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-- ; }
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 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 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.
/* 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