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

Related posts:

Injecting Prototype Beans into a Singleton Instance in Spring
Apache Commons Collections OrderedMap
Guide to the Fork/Join Framework in Java
Sắp xếp trong Java 8
JWT – Token-based Authentication trong Jersey 2.x
Java Program to Implement Sieve Of Sundaram
Inject Parameters into JUnit Jupiter Unit Tests
Java Program to Implement Regular Falsi Algorithm
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Using the Not Operator in If Conditions in Java
Java – Convert File to InputStream
Hướng dẫn Java Design Pattern – Flyweight
Rate Limiting in Spring Cloud Netflix Zuul
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Java Program to Implement Affine Cipher
Java Program to Implement Sorted Array
Java Program to Implement the One Time Pad Algorithm
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Java Program to Implement Skew Heap
Spring REST API with Protocol Buffers
A Quick Guide to Using Keycloak with Spring Boot
A Guide to Java HashMap
Properties with Spring and Spring Boot
Java Program to Implement AttributeList API
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Guide to the Java ArrayList
Java Program to Implement Leftist Heap
Java Program to subtract two large numbers using Linked Lists
Java Program to Generate Randomized Sequence of Given Range of Numbers
Java Program to Implement Repeated Squaring Algorithm
Returning Image/Media Data with Spring MVC
A Guide to the ViewResolver in Spring MVC