Implementing Sinlge Linked List in Java

Linked List :

Linked list is a dynamic data structure whose length can be increased or decreased at run time.
How Linked lists are different from arrays? Consider the following points :

• An array is a static data structure. This means the length of array cannot be altered at run time. While, a linked list is a dynamic data structure.
• In an array, all the elements are kept at consecutive memory locations while in a linked list the elements (or nodes) may be kept at any location but still connected to each other. 

The figure below shows representation of Single Linked List

When to prefer linked lists over arrays?

Linked lists are preferred mostly when you don’t know the volume of data to be stored. For example, In an employee management system, one cannot use arrays as they are of fixed length while any number of new employees can join. In scenarios like these, linked lists (or other dynamic data structures) are used as their capacity can be increased (or decreased) at run time (as an when required).

How linked lists are arranged in memory?

Linked list basically consists of memory blocks that are located at random memory locations. 

A node class in Java can be created as :

class Node
{
    int data;
    Node link;
}  

Operations on Single Linked List :

• Insert : Add/Insert node into the list.
• Delete : Delete a node/element from the list
• Search : Search for an element in the list
• Display : Display the list
• Sort : Sort the list.
• Length : Finding the length of the list i.e., number of elements in the list.

import java.util.Scanner;
interface SllAdt{
    public void insert();
    public void delete();
    public void display();
    public int len();
    public void search();
    public void sort();
}
class SNode{
    int data;
    SNode link;
}
public class SLL extends SNode implements SllAdt {    
    SNode first;
    Scanner s=new Scanner(System.in);
    public SLL(){
        first=null;
    }
public void insert(){
        System.out.println("Enter the position to insert a node: ");
        int pos=s.nextInt();
        System.out.println("Enter the data into a node");
        int ele=s.nextInt();
        
        SNode p=new SNode();
        p.data=ele;
        p.link=null;
        
        if(pos<&eq;1||pos>len()+1)
            System.out.println("Invalid position and insertion is not possible");
        else if(pos==1){
            p.link=first;
            System.out.println("found at position 1 and p.link is :"+p.link+" and first is :"+first);
            first=p;
            System.out.println("now first is :"+first);
            System.out.println("Entered position is(1st):"+pos);
        }
        else{
            SNode temp;
            temp=first;
            for(int i=1;i<pos-1;i++)
                temp=temp.link;
            p.link=temp.link;
            temp.link=p;
            System.out.println("ENtered position is:"+pos);
            
        }
    }
    
    public void delete(){
        System.out.println("Enter the positon to delete a node:");
        int pos=s.nextInt();
        SNode p,temp;
        if(pos<1||pos>len()+1)
            System.out.println("Invalid position and deletion is not possible");
        else if(pos==1){
            temp=first;
            first=first.link;
            System.out.println("Deleted element is :"+temp.data);
        }
        else{
            temp=first;
            for(int i=1;i < pos-1;i++)
                temp=temp.link;
            p=temp.link;
            temp.link=p.link;
            System.out.println("Deleted element is :"+p.data);
        }
    }
    public void display(){
        SNode temp;
        if(first==null)
            System.out.println("Linked list is empty:");
        else{
            System.out.println("List of elements:");
            System.out.print("First->");
            for(temp=first;temp!=null;temp=temp.link)
                System.out.print(temp.data+"-->");
            System.out.print("End");
        }
    }
    public int len(){
        int count=0;
        SNode temp;
        for(temp=first;temp!=null;temp=temp.link)
            count++;
        return count;
    }
    public void search(){
        System.out.println("Enter the element to search :");
        int ele=s.nextInt();
        int pos=1;
        SNode temp;
        for(temp=first;temp!=null;temp=temp.link){
            if(temp.data==ele)
                System.out.println("Element "+ele+" is found at position: "+pos);
            else
                System.out.println("Element "+ele+" is not found");
            pos++;
        }
    }
    public void sort(){
        SNode temp1,temp2;
        for(temp1=first;temp1!=null;temp1=temp1.link)
            for(temp2=temp1.link;temp2!=null;temp2=temp2.link)
            {
                if(temp1.data>temp2.data)
                {
                    int t=temp1.data;
                    temp1.data=temp2.data;
                    temp2.data=t;
                }
            }
    }
    
    public static void main(String[] args){
        System.out.println("Single Linked List ADT");
        Scanner s=new Scanner(System.in);
        SLL s1=new SLL();
        String ch="y";
        while(ch.equalsIgnoreCase("y")){
            System.out.println("\nStack Operations:\n1. Insert 2. Delete 3. Display 4. Length 5. Search 6. Sort 7. Exit :");
            System.out.println("Enter the option :");
            int opt=s.nextInt();
            switch(opt){
                case 1:s1.insert();break;
                case 2:s1.delete();break;
                case 3:s1.display();break;
                case 4: System.out.println("Length of SLL is :"+s1.len());break;
                case 5:s1.search();break;
                case 6:s1.sort();break;
                case 7:System.exit(0);
                default:System.out.println("Invalid option");
            }
        }
    }
}