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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Implement Sorted Circularly Singly Linked List

» Next - Java Program to Implement Circular Doubly Linked List

Related Posts:

Recommended Articles: