Java Program to Implement Sorted Singly Linked List

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