This is a Java Program to implement a Sorted Singly Linked List. 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. This structure allows for efficient insertion or removal of elements from any position in the sequence. In a sorted singly linked list each node has only one link pointing to the next node and insertion of an element into the list is done in a sorted fashion.
Here is the source code of the Java program to implement Sorted Singly Linked List. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/*
* Java Program to Implement Sorted Singly Linked List
*/
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
class linkedList
{
protected Node start;
public int size;
public linkedList()
{
start=null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to check size of list */
public int getSize()
{
return size;
}
/* Function to insert an element */
public void insert(int val)
{
Node nptr, ptr, tmp = null;
nptr = new Node(val, null);
boolean ins = false;
if (start == null)
start = nptr;
else if (val <= start.getData())
{
nptr.setLink(start);
start = nptr;
}
else
{
tmp = start;
ptr = start.getLink();
while(ptr != null)
{
if (val >= tmp.getData() && val <= ptr.getData())
{
tmp.setLink(nptr);
nptr.setLink(ptr);
ins = true;
break;
}
else
{
tmp = ptr;
ptr = ptr.getLink();
}
}
if (ins == false)
{
tmp.setLink(nptr);
}
}
size++;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node ptr = start;
for (int i = 1; i < size - 1; i++)
ptr = ptr.getLink();
ptr.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print("Sorted Singly Linked List = ");
if (size == 0)
{
System.out.print("empty\n");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null) {
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ "\n");
}
}
public class SortedSinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.println("Sorted Singly Linked List Test\n");
char ch;
/* Perform list operations */
do
{
System.out.println("\nSorted Singly Linked List Operations\n");
System.out.println("1. insert");
System.out.println("2. delete at position");
System.out.println("3. check empty");
System.out.println("4. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 3 :
System.out.println("Empty status = "+ list.isEmpty()+"\n");
break;
case 4 :
System.out.println("Size = "+ list.getSize() +" \n");
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display List */
list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Sorted Singly Linked List Test Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 3 Empty status = true Sorted Singly Linked List = empty Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 24 Sorted Singly Linked List = 24 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 6 Sorted Singly Linked List = 6->24 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 19 Sorted Singly Linked List = 6->19->24 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 94 Sorted Singly Linked List = 6->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 1 Sorted Singly Linked List = 1->6->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 7 Sorted Singly Linked List = 1->6->7->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 1 Enter integer element to insert 12 Sorted Singly Linked List = 1->6->7->12->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 4 Size = 7 Sorted Singly Linked List = 1->6->7->12->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 3 Sorted Singly Linked List = 1->6->12->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Sorted Singly Linked List = 6->12->19->24->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 4 Sorted Singly Linked List = 6->12->19->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 3 Sorted Singly Linked List = 6->12->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Sorted Singly Linked List = 12->94 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 2 Sorted Singly Linked List = 12 Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 2 Enter position 1 Sorted Singly Linked List = empty Do you want to continue (Type y or n) y Sorted Singly Linked List Operations 1. insert 2. delete at position 3. check empty 4. get size 3 Empty status = true Sorted Singly Linked List = empty Do you want to continue (Type y or n) n
Sanfoundry Global Education & Learning Series – 1000 Java Programs.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Related Posts:
- Apply for Computer Science Internship
- Practice Programming MCQs
- Check Programming Books
- Practice Computer Science MCQs
- Practice Design & Analysis of Algorithms MCQ