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.

  1. /*
  2.  *  Java Program to Implement Sorted Singly Linked List
  3.  */
  4.  
  5. import java.util.Scanner;
  6.  
  7. /*  Class Node  */
  8. class Node
  9. {
  10.     protected int data;
  11.     protected Node link;
  12.  
  13.     /*  Constructor  */
  14.     public Node()
  15.     {
  16.         link = null;
  17.         data = 0;
  18.     }    
  19.     /*  Constructor  */
  20.     public Node(int d,Node n)
  21.     {
  22.         data = d;
  23.         link = n;
  24.     }    
  25.     /*  Function to set link to next Node  */
  26.     public void setLink(Node n)
  27.     {
  28.         link = n;
  29.     }    
  30.     /*  Function to set data to current Node  */
  31.     public void setData(int d)
  32.     {
  33.         data = d;
  34.     }    
  35.     /*  Function to get link to next node  */
  36.     public Node getLink()
  37.     {
  38.         return link;
  39.     }    
  40.     /*  Function to get data from current Node  */
  41.     public int getData()
  42.     {
  43.         return data;
  44.     }
  45. }
  46. class linkedList
  47. {
  48.     protected Node start;
  49.     public int size;
  50.     public linkedList()
  51.     {
  52.         start=null;
  53.         size = 0;
  54.     }
  55.     /*  Function to check if list is empty  */
  56.     public boolean isEmpty()
  57.     {
  58.         return start == null;
  59.     }
  60.     /*  Function to check size of list  */
  61.     public int getSize()
  62.     {
  63.         return size;
  64.     }    
  65.     /*  Function to insert an element  */
  66.     public void insert(int val)
  67.     {
  68.         Node nptr, ptr, tmp = null;
  69.         nptr = new Node(val, null);
  70.         boolean ins = false;
  71.         if (start == null)
  72.            start = nptr;
  73.         else if (val <= start.getData())
  74.         {
  75.             nptr.setLink(start);
  76.             start = nptr;
  77.         }
  78.         else
  79.         {
  80.             tmp = start;
  81.             ptr = start.getLink();
  82.             while(ptr != null)
  83.             {
  84.                 if (val >= tmp.getData() && val <= ptr.getData())
  85.                 {
  86.                     tmp.setLink(nptr);
  87.                     nptr.setLink(ptr);
  88.                     ins = true;
  89.                     break;
  90.                 }
  91.                 else
  92.                 {
  93.                     tmp = ptr;
  94.                     ptr = ptr.getLink();
  95.                 }
  96.             }
  97.             if (ins == false)
  98.             {
  99.                 tmp.setLink(nptr);
  100.             }
  101.         }
  102.         size++;
  103.     }
  104.     /*  Function to delete an element at position  */
  105.     public void deleteAtPos(int pos)
  106.     {        
  107.         if (pos == 1) 
  108.         {
  109.             start = start.getLink();
  110.             size--; 
  111.             return ;
  112.         }
  113.         if (pos == size) 
  114.         {
  115.             Node ptr = start;
  116.  
  117.             for (int i = 1; i < size - 1; i++)
  118.                 ptr = ptr.getLink();
  119.             ptr.setLink(null);            
  120.             size --;
  121.             return;
  122.         }
  123.         Node ptr = start;
  124.         pos = pos - 1 ;
  125.         for (int i = 1; i < size - 1; i++) 
  126.         {
  127.             if (i == pos) 
  128.             {
  129.                 Node tmp = ptr.getLink();
  130.                 tmp = tmp.getLink();
  131.                 ptr.setLink(tmp);
  132.                 break;
  133.             }
  134.             ptr = ptr.getLink();
  135.         }
  136.         size-- ;
  137.     }    
  138.     /*  Function to display elements  */
  139.     public void display()
  140.     {
  141.         System.out.print("Sorted Singly Linked List = ");
  142.         if (size == 0) 
  143.         {
  144.             System.out.print("empty\n");
  145.             return;
  146.         }
  147.         if (start.getLink() == null) 
  148.         {
  149.             System.out.println(start.getData() );
  150.             return;
  151.         }
  152.         Node ptr = start;
  153.         System.out.print(start.getData()+ "->");
  154.         ptr = start.getLink();
  155.         while (ptr.getLink() != null) {
  156.             System.out.print(ptr.getData()+ "->");
  157.             ptr = ptr.getLink();
  158.         }
  159.         System.out.print(ptr.getData()+ "\n");
  160.     }
  161. }
  162. public class SortedSinglyLinkedList
  163. {
  164.     public static void main(String[] args)
  165.     {             
  166.         Scanner scan = new Scanner(System.in);
  167.         /* Creating object of linkedList */
  168.         linkedList list = new linkedList(); 
  169.         System.out.println("Sorted Singly Linked List Test\n");          
  170.         char ch;
  171.         /*  Perform list operations  */
  172.         do
  173.         {
  174.             System.out.println("\nSorted Singly Linked List Operations\n");
  175.             System.out.println("1. insert");
  176.             System.out.println("2. delete at position");
  177.             System.out.println("3. check empty");
  178.             System.out.println("4. get size");            
  179.             int choice = scan.nextInt();            
  180.             switch (choice)
  181.             {    
  182.             case 1 : 
  183.                 System.out.println("Enter integer element to insert");
  184.                 list.insert( scan.nextInt() );                     
  185.                 break;                          
  186.             case 2 : 
  187.                 System.out.println("Enter position");
  188.                 int p = scan.nextInt() ;
  189.                 if (p < 1 || p > list.getSize() )
  190.                     System.out.println("Invalid position\n");
  191.                 else
  192.                     list.deleteAtPos(p);
  193.                 break;
  194.             case 3 : 
  195.                 System.out.println("Empty status = "+ list.isEmpty()+"\n");
  196.                 break;                   
  197.             case 4 : 
  198.                 System.out.println("Size = "+ list.getSize() +" \n");
  199.                 break;                         
  200.             default : 
  201.                 System.out.println("Wrong Entry \n ");
  202.                 break;   
  203.             }
  204.             /*  Display List  */ 
  205.             list.display();
  206.             System.out.println("\nDo you want to continue (Type y or n) \n");
  207.             ch = scan.next().charAt(0);                
  208.         } while (ch == 'Y'|| ch == 'y');               
  209.     }
  210. }

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.