bim 4th semester

Linked List and Types in Java

Ankeet Chamlagain
by Ankeet Chamlagain February 02, 2022

Linked List in Java

A linked list is a linear data structure. Linked List is collection of nodes; nodes are containers having at least two parts: one for storing data and another for storing address of another node. Linked List is very flexible kind of data structure; insertion and deletion of any node from any position is possible, but random access of the nodes is not possible in the linked list.

The elements in a linked list are linked using pointers as shown in the below image:

linked list

fig: Linked List

Types:

  • ·        Singly  Linked List
  • ·        Doubly Linked List
  • ·        Circular Linked List
  • ·        Doubly Circular Linked List

Singly Linked List:

It is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single linked list allows traversal of data only in one way.

Creation of Singly Linked List node in java:

Class SLLNode{

          int info;

          SLLNode next;

}

singly linked list


Source Code:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package LinkedList;
import java.util.*;
/**
 *
 * @author AnkeetPC
 */
// inserting and deleting first and last node of SLL
class SLLNode{
    int info; //data holder
    SLLNode next; // address holder
}
class SLL{
    SLLNode first,last;
    
    public void insertAtFirst(int data){
        SLLNode newnode = new SLLNode();
        newnode.info = data;
        
        if(first == null){
            newnode.next = null;
            first = newnode;
            last = newnode;
        }else{
            newnode.next = first;
            first = newnode;
        }   
    }
    
    
   public void insertAtEnd(int data){
       SLLNode newnode = new SLLNode();
       newnode.info = data;
       
       if(first == null){
           newnode.next = null;
           first = newnode;
           last = newnode;
       }else{
           last.next = newnode;
           last = newnode;
       }
       
   }
   
   public void deleteAtFirst(){
       SLLNode temp = first;
       
       if(first == null){
           System.out.println("Empty List");
       }else{
           first = first.next;
           temp.next = null;
       }
   }
    
   public void deleteAtLast(){
       SLLNode temp = first;
       
       if(first == null){
           System.out.println("EmptyList");
       }else if(first == last){
           first = null;
           last = null;
       }else{
           while(temp.next!=last){
               temp = temp.next;
           }
           temp.next= null;
           last = temp;
           
       }
       
   }
   
   public void insertAtSpecifiedPos(int data){
       int position;
       SLLNode newnode = new SLLNode();
       SLLNode temp = new SLLNode();
       newnode.info = data;
       
       System.out.println("Enter the position: ");
       Scanner input = new Scanner(System.in);
       
       position = input.nextInt();
       
       if(first == null){
           newnode.next = null;
           first = newnode;
           last = newnode;
       }else{
           temp = first;
           for(int i=0;i<position-1;i++){
               temp =temp.next;
           }
           newnode.next = temp.next;
           temp.next = newnode;
       }
       
   }
   
  public void search(int data){
      SLLNode temp = first;
      int flag = 0;
      
      while(temp!=null){
          if(temp.info==data){
              flag =1;
              System.out.println("Data found: "+temp.info);
              
          }
          temp = temp.next;
      }
      if(flag ==0){
          System.out.println("Not found");
      }
  }
   
    public void display(){
        SLLNode temp = first;
        
        if(first == null){
            System.out.println("Empty list");
        }else{
            while(temp.next!=null){
                System.out.println(temp.info+"");
                temp = temp.next;
            }
            System.out.println(temp.info+"");
        }
        
    }
    
}
public class SLLDemo {
    public static void main(String[] args) {
        SLL ob = new SLL();
        ob.insertAtFirst(15);
        ob.insertAtFirst(20);
        ob.insertAtFirst(25);
        ob.insertAtEnd(55);
        ob.insertAtEnd(35);
       ob.insertAtEnd(88);
         ob.deleteAtFirst();
         ob.deleteAtLast();
       // ob.insertAtSpecifiedPos(45);
        ob.search(55);
        ob.display();
    }
}

Doubly Linked List:

A doubly linked list or a two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in sequence, Therefore, it contains three parts are data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well.

Creation of Doubly Linked List node in java:

Class DLLNode{

          int info;

          DLLNode next,prev;

}

 

doubly linked list



Source Code:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package LinkedList;

/**
 *
 * @author AnkeetPC
 */
// inserting and deleting first and last node of DLL
class DLLNode{
    int info; // data holder
    DLLNode next,prev; //address holder
    
}
class DLL{
    DLLNode first, last;
    
    public void insertAtFirst(int data){
        DLLNode newnode = new DLLNode();
        newnode.info = data;
        if(first == null && last == null){
            first = newnode;
            last = newnode;
        }else{
            newnode.next = first;
            first.prev = newnode;
            first = newnode;
            
        } 
    }
    
    public void insertAtLasr(int data){
        DLLNode newnode = new DLLNode();
        newnode.info = data;
         
        if(first == null && last == null){
            first = newnode;
            last =  newnode;
        }else{
            last.next = newnode;
            newnode.prev = last;
            last = newnode;
        }
    }
    
    public void deleteFirst(){
        
        if(first == null && last == null){
            System.out.println("Empty List");
        }else if(first == last){
            first = null;
            last = null;
        }else{
            DLLNode temp = first;
            first = first.next;
            temp.next = null;
            first.prev = null;
        }
    }
    
    public void deleteLast(){
        if(first==null && last == null){
            System.out.println("Empty List");
        }else if(first == last){
            first = null;
            last = null;
        }else{
            DLLNode temp=first;
            while(temp.next!=last){
                temp = temp.next;
            }
            temp.next = null;
            last = temp;
        }
    }
    
    public void display(){
        DLLNode temp = first;
        if(temp == null){
            System.out.println("Empty List");
        }else{
            while(temp!=last.next){
                System.out.println(temp.info+"");
                temp = temp.next;
            }
        }
    }
    
}
public class DLLDemo {
    public static void main(String[] args) {
        DLL ob = new DLL();
        ob.insertAtFirst(15);
        ob.insertAtFirst(25);
         ob.insertAtFirst(45);
         ob.insertAtLasr(55);
         ob.deleteFirst();
         ob.deleteLast();
        ob.display();
    }
}

Circular Linked List:

A circular linked list is that in which the last node contains the pointer to the first node of the list. While traversing a circular liked list, we can begin at any node and traverse the list in any direction forward and backward until we reach the same node we started. Thus, a circular linked list has no beginning and no end.


Creation of Circular Linked List node in java:

Class CLLNode{

          int info;

          CLLNode next;

} 




Source Code:
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package LinkedList;

/**
 *
 * @author AnkeetPC
 */
// inserting and deleting first and last node from CLL

class CLLNode{
    int info; // data holder
    CLLNode next; // address holder
}

class CLL{
    CLLNode first,last;
    
    public void insertFirst(int data){
        CLLNode newnode = new CLLNode(); // node creation
        newnode.info = data;
        
        if(first == null){
            newnode.next = null;
            first = newnode;
            last = newnode;
        }else{
            newnode.next = first;
            first = newnode;
            last.next = newnode;
        }
        
        
    }
    
    public void insertLast(int data){
        CLLNode newnode = new CLLNode(); // node creation
        newnode.info = data;
        
        if(first == null){
            newnode.next = null;
            first = newnode;
            last =  newnode;
        }else{
            newnode.next = last.next;
            last.next = newnode;
            last = newnode;
        }
        
        
    }
    
    public void deleteFirst(){
        if(first == null && last == null){
            System.out.println("Empty List");
        }else if(last == last.next){
            last.next= null;
            last = null;
        }else{
            CLLNode temp = first;
            first = first.next;
            last.next = first;
            temp = null;
        }
    }
    
    public void deleteLast(){
        if(first == null && last ==null){
            System.out.println("Empty List");
        }else if(last == last.next){
            last.next = null;
            last = null;
        }else{
            CLLNode temp = first;
            
            while(temp.next!= last){
                temp = temp.next;
            }
            temp.next = first;
            last = temp;
        }
    }
    
    public void display(){
        CLLNode temp = first;
        
        if(first == null){
            System.out.println("Empty List");
        }else{
        while(temp.next!=first){
            System.out.println(temp.info+"");
            temp = temp.next;
        }
            System.out.println(temp.info+"");
    }
    }
    
}

public class CLLDemo {
    public static void main(String[] args) {
        CLL ob = new CLL();
        ob.insertFirst(25);
        ob.insertFirst(77);
        ob.insertLast(88);
        ob.insertLast(89);
        ob.deleteFirst();
        ob.deleteLast();
        ob.display();
    }
}

Doubly Circular Linked List:

A Doubly Circular linked list or a circular two-way linked list is a more complex type of linked-list that contains a pointer to the next as well as the previous node in the sequence. The difference between the doubly linked and circular doubly list is the same as that between a singly linked list and a circular linked list. The circular doubly linked list does not contain null in the previous field of the first node. 


Creation of Doubly Circular Linked List node in java:

Class DCLLNode{

          int info;

          DCLLNode next,prev;

}




Source Code:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package LinkedList;

/**
 *
 * @author AnkeetPC
 */

// inserting and deleting first and last node from DCLL
class DCLLNode{
    int info; // data holder
    DCLLNode prev,next; // adress holder
}

class DCLL{
    DCLLNode first,last;
    
    public void insertFirst(int data){
        DCLLNode newnode = new DCLLNode(); // node creation
        newnode.info = data;
        
        if(first == null  && last == null){
            newnode.next =newnode;
            newnode.prev = newnode;
            first = newnode;
            last = newnode;
        }else{
            newnode.next = first;
            first.prev =newnode;
            first = newnode;
            newnode.prev= last;
            first.prev = last;
        }
        
    }
    
    public void insertLast(int data){
        DCLLNode newnode = new DCLLNode(); // node creation
        newnode.info = data;
        
        if(first == null && last== null){
            newnode.next = newnode;
            newnode.prev = newnode;
            first = newnode;
            last = newnode;
        }else{
            last.next = newnode;
            newnode.next = first;
            newnode.prev = last;
            first.prev = newnode;
            last = newnode;
        }
    }
    
    public void deleteFirst(){
        if(first == null && last == null){
            System.out.println("Empty List");
        }else if(first == last){
            first = null;
            last = null;
        }else{
            DCLLNode temp = first;
            first = first.next;
            temp.next = null;
            first.prev = last;
            last.next= first;
        }
    }
    
    public void deleteLast(){
        if(first== null && last == null){
            System.out.println("EMpty list");
        }else if(first == last){
            first = null;
            last = null;
        }else{
            DCLLNode temp =first;
            last = last.prev;
            temp.prev = null;
            first.prev= last;
            last.next = first;
        }
    }
    
    public void display(){
        DCLLNode temp = first;
        if(first == null){
            System.out.println("Empty List");
        }else{
            do{
                System.out.println(temp.info+"");
                temp = temp.next;
            }while(temp!=last);
            System.out.println(temp.info+"");
        }
    }
}

public class DCLLDemo {
    public static void main(String[] args) {
        DCLL ob = new DCLL();
        ob.insertFirst(88);
        ob.insertFirst(101);
        ob.insertLast(99);
        ob.deleteFirst();
        ob.deleteLast();
        ob.display();
    }
}

Video is available on YouTube . Don't Forget to check out the video.

Ankeet Chamlagain

Posted by Ankeet Chamlagain

Post a Comment

0 Comments