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:
fig:
Linked List
Types:
- ·      Â
SinglyÂ
Linked List
- ·      Â
Doubly Linked List
- ·      Â
Circular Linked List
- ·      Â
Doubly Circular Linked List
Singly Linked List:
Creation
of Singly Linked List node in java:
Class SLLNode{
         int info;
         SLLNode next;
}
/*
 * 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;
}
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;
}
/*
 * 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.