Single Linked List

Single Linked List

package list;
import java.util.Scanner;
class Node
{
  int info;
  Node next;
}
 // Node Has two Parts 
  //  1. information
  //  2.  pointer value

public class LinkedList
{
 
    static void create(Node start)
    {
    Scanner sc= new Scanner(System.in);
    int option;
    Node p;
    System.out.println("Enter the node info\n");
    start.info=sc.nextInt();
    start.next=null;
    p=start;
    System.out.println("Do u want to add new node Yes-1/No-0 \n");
    option=sc.nextInt();

    //To Add the Node Information And Node Swapping 
 
    while(option!=0)
    {
    p.next=new Node();
    p=p.next;
    System.out.println("Enter the node info\n");
    p.info=sc.nextInt();;
    p.next=null;
    System.out.println("Do u want to add new node Yes-1/No-0\n");
    option=sc.nextInt();
    }
    }

    

    
   //To display the Linked List 

    static void display(Node start)
    {
    Node p;
    p=start;
    while(p!=null)
    {
      System.out.println(p.info);
           p=p.next;
    }
    }



   // Node Insert at The Beginging 

    static Node InsBeg(Node start)
    {
     Scanner sc= new Scanner(System.in);
    Node curr;
    curr=new Node();
    if(curr==null)
    {
      System.out.println("Out of memory space\n");
      System.exit(0);
    }
    System.out.println("Enter the node info\n");
     curr.info=sc.nextInt();
    curr.next=start;
    start=curr;
    return start;
    }



   // Insert Node At the End of the Linked List
    static Node InsEnd(Node start)
    {
            Scanner sc= new Scanner(System.in);
    Node p,curr;
    p=start;
    while(p.next!=null)
    {
      p=p.next;
    }
    curr=new Node();
    System.out.println("Enter the node info\n");
     curr.info=sc.nextInt();;
    p.next=curr;
    curr.next=null;
    return start;
    }



    static node InsEnd ( Node Start )
    {
     Scanner sc = new Scanner(System.in);
     Node curr = new  Node();
     System.out.println(“ Enter the node Info “);
     curr.info = sc.nextInt();
     curr.next = null;
     Node p;
     p = start;
     while( p.next != null ) 
    {
     p = p.next;
    }
    return start;
   } 
 
    
  
   // Insert Node at any position after the location
   // User will enter the node after which you will insert a new node


    static Node InsAft(Node start)
    {
Scanner sc=new Scanner(System.in);
           Node curr;
           int x;
           Node p;
      p=start;
     System.out.println("Enter the node value after which the new node to be inserted\n");
           x=sc.nextInt();
      while(p!=null)
      {
              if(x==p.info)
               break;
              p=p.next;
           }
     curr=new Node();
    System.out.println("Enter the node info\n");
 curr.info=sc.nextInt();
     curr.next=p.next;
     p.next=curr;
     return start;
     }


   // Insert at Any Location Where User Wants 
   
    static Node InsAny(Node start)
    {
            Scanner sc= new Scanner(System.in);
           Node curr;
           int i,loc;
           Node prev = null;
           Node p;
           p=start;
      System.out.println("Enter the location you want to insert\n");
         loc=sc.nextInt();
           i=1;
           while(i<loc)
           {
               prev =p;
              p=p.next;
               i++;
           }
      curr=new Node();
     System.out.println("Enter the node info\n");
     curr.info=sc.nextInt();
      curr.next=prev.next;
      prev.next=curr;
      return start;
     }




    // delete node at the begining
    
    static Node DelBeg(Node start)
    {
    Node temp;
    if(start==null)
    {
     System.out.println("Memory underflow\n");
     System.exit(0);
    }
    temp=start;
    start=start.next;
    temp.next=null;
   
    return start;
    }



    // Delete Node At the End
    
    static Node  DelEnd(Node start)
    {
    Node temp;
    Node p;
    p=start;
    temp=null;
    while(p.next!=null)
    {
           temp=p;
           p=p.next;
    }
    temp.next=null;
   
    return start;
    }


 
   //  Delete A Given Node 

    static Node Del(Node start)
    {
     Scanner sc= new Scanner(System.in);
    Node p;
    Node temp;
    int x;int flag=0;
    p=start;
    temp=null;
    System.out.println("Enter the node value you want to  delete\n");
     x=sc.nextInt();
    while(p!=null)
    {
           
           if(x==p.info)
           { flag=1;
            break;}
            temp=p;
            p=p.next;
    }
    temp.next=p.next;
     if(flag==1)
            {
              System.out.println("Item deleted \n");
            }
            else
            {
             System.out.println("Item to be deleted  is not found\n");
            }
    return start;
    }



   // Delete Any Specific node the Node Information has to be inserted by the user

    static Node DelAny(Node start)
    {
    Scanner sc=new Scanner(System.in);
    Node p;
    Node prev;
    int loc;
    int i=1;
    p=start;
    prev=null;
    System.out.println("Enter the location number where the node to be deleted\n");
    loc=sc.nextInt();
    while(i<loc)
    {
      prev=p;
      p=p.next;
      i++;
    }
    prev.next=p.next;
 
    return start;
    }







//   Search a node ( user will enter the node to be searched )


static void search(Node start)
    {
            Scanner sc= new Scanner(System.in);
            int item;
            int flag=0;
            Node p;
            p=start;
           System.out.println("Enter the node value you want to search\n");
      item=sc.nextInt();
            while(p!=null)
            {
               if(p.info==item)
                {
                 flag=1;
                 break;
                 }
                else
                {
                 p=p.next;
                }
             }
            if(flag==1)
            {
              System.out.println("Item is found\n");
            }
            else
            {
             System.out.println("Item is not found\n");
            }
    }

    // Sort the Given Node In Ascending Order
    
    static void sortA(Node start)
    {
      Node p1;
      Node p2;
      int temp;                        //temporary variable
      for(p1=start;p1!=null;p1=p1.next)
      {
       for(p2=start;p2!=null;p2=p2.next)
       {
         if( p1.next > p2.next )
          {
            temp = p1.info;
            p1.info = p2.info;
            p2.info = temp;
          }
          
       }
       
      } 
       
    }
    
    // Count the number of nodes present in the linked list
    static int count(Node start)
    {
            Node p;
            p=start;
            int c=0;
            while(p!=null)
            {
              c++;
              p=p.next;
            }
           return c;
    }


   // Reversing The Linked List 
   
    static Node reverse(Node start)
    {
      Node p1,p2,p3;
      p1 = null;
      p2 = start;
      p3 = p2.next();
      p2.next = null;
      
      while(p3!=null)
      {
        p1 = p2 ; 
        p2 =  p3;
        p3 = p3.next;
        p2.next = p1;
      }
      start = p2 ;
      return start;
      
    }


public static void main(String[] arg)
{
    Scanner sc= new Scanner(System.in);
  Node start;
   start=new Node() ;
         int choice;
         int res;
        while(true)
 {
   System.out.println("\n 0:Exit");
   System.out.println("\n 1:Creation");
   System.out.println("\n 2:Display");
   System.out.println("\n 3:Insert at the beginnning");
   System.out.println("\n 4:Insert at the end");
   System.out.println("\n 5: Insert after a given node");
   System.out.println("\n 6: Insert at any location");
   System.out.println("\n 7: Delete from the beginning");
   System.out.println("\n 8: Delete from the end");
   System.out.println("\n 9: Delete a given node");
   System.out.println("\n 10: Delete from any location");
   System.out.println("\n 11:Search a node");
   System.out.println("\n 12: sort the linked list");
   System.out.println("\n 13:Count the no of nodes in the linked list");
   System.out.println("\n 14:Reverse the linked list\n");
   System.out.println("\nEnter the choice\n");
 choice=sc.nextInt();
        switch(choice)
        {
            case 0:
                    System.out.println("Exit! Thank you !!");
                    System.exit(0);
            case 1:
             create(start);
             break;
            case 2:
             display(start);
             break;
            case 3:
             start=InsBeg(start);
             break;
            case 4:
             start=InsEnd(start);
             break;
            case 5:
             start=InsAft(start);
             break;
            case 6:
             start=InsAny(start);
             break;
            case 7:
             start=DelBeg(start);
             break;
            case 8:
              start=DelEnd(start);
              break;
            case 9:
              start=Del(start);
              break;
             case 10:
              start=DelAny(start);
              break;
             case 11:
           
              search(start);
           
              break;
             case 12:
              sort(start);
              break;
             case 13:
              res=count(start);
             System.out.println("Total no of nodes= "+res);
              break;
             case 14:
               start=reverse(start);
               break;  
             default:
             System.out.println("Wrong choice\n");
               
         }
}
}

if you have to write only the methods then dont use static Node function name(Node start) else type out ststic void function name (Node start)

The Concept Of Link List
Link list used for the dynamic memory allocation.
Array and link list both are the linear data structure.
When we want to represent several lists by using arrays of varying size, either we have to represent.
each list using a separate array of maximum size or we have to represent each of the lists using one single array.
The first one will lead to wastage of storage, and the second will involve a lot of data movement.
A linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element.

Representation of link list
Link list consists a series of structure. Each structure consists of a data field and address field. Data field consists data part and the address field contains the address of the successors.

Advantage of Link list
Link list is an example of dynamic data structure. They can grow and shrink during the execution of program.
Efficient memory utilization. Memory is not pre allocated like static data structure. The allocation of memory depends upon the user ,i.e no need to pre-allocate memory
Insertion and deletion easily performed.
Linear Data Structures such as Stack,Queue can be easily implemeted using Linked list
Faster Access time,can be expanded in constant time without memory overhead

Points to Remember
Linked lists are used when the quantity of data is not known prior to execution.
In linked lists, data is stored in the form of nodes and at runtime, memory is allocated for creating nodes.
Due to overhead in memory allocation and deallocation, the speed of the program is lower.
The data is accessed using the starting pointer of the list.