Linked List Data Structure in Java

Post Views: 50

In this Java tutorial, we are going to discuss the linked list data structure. We will learn the following things in this Java Linked List tutorial:

Advantages of LinkedList in Java
Disadvantages of LinkedList in Java
Implementation of LinkedList in Java
Representation of LinkedList in Java

What is Linked List?

Linked list is a linear data structure in which elements are not stored in contiguous memory locations. Elements in LinkedList are linked to each other using pointers.

A linked list consists of nodes in which each data holds a data field and a pointer to the next node. Starting node of linked list is known as head node.

Representation of a Linked List

Linked list consists of two parts:-

1.) Data field:- stores the data of a node.

2.) Pointer to next node:- Each node holds the address of the next node. Each node in a linked list is connected to next node using pointer.

In Java Linked List is represented as a separate class and node as a separate class

  class Codespeedy

{ 
    node head; 
  
      class node 
    { 
        int value; 
        node next; 
           
     
          Node(int x)
       {
           value = x;
       } 
    } 
}

Advantages of using Linked List

1.) Dynamic Size:- Memory allocation to linked list elements is done dynamically. So, we can add more and more elements in a linked list easily as compared to arrays. There is an upper limit on the number of elements in array as the size of array is fixed.

2.) Ease of Insertion and Deletion:- Insertion and deletion of an element in a linked list is very easy as compared to arrays and can be done in O(1). In array insertion of an element needs room for that element and shifting of elements.

Disadvantages of using Linked List

1.) Extra memory space for pointers:- As each node in a linked list consists of pointers which hold the address of next node, so an extra memory space for a pointer is required with each element of linked list .

2.) Random access not allowed:- Random access of an element in a linked list is not allowed. We have to traverse the linked list from starting to access an element in linked list. While in arrays accessing an element can be done in O(1).

Implementation of LinkedList in Java

import java.util.Scanner;

  public class LinkedList

{ 
  
   static node head;  
  
   static node p;
   
     static class node
  { 
    int value; 
    
      node next; 
  
      node(int x)
    { 
        value = x;
      
           next=null; 
     }  
  } 

    	public void show() 
  
  { 
    node newnode = head; 
     
      while (newnode != null) 
    { 
      System.out.print(newnode.value+" "); 
     
         newnode = newnode.next; 
    } 
  } 
  
    public static void main(String[] args) 
  { 
    
    LinkedList list = new LinkedList(); 
    
    Scanner scan = new Scanner(System.in);

       System.out.println("Enter value for head node :");
          
            int Head = scan.nextInt();
          
    list.head	 = new node(Head);
      
         head.next = null;
      
       node head = p;
       
       char ch='Y';
       
      while (ch!='N')
    {
        System.out.println("Enter value for adding node :");
        
             int add = scan.nextInt();
         
      node addnode = new node(add); 

       list.p.next = addnode;
          
          addnode = p;
         
            addnode.next = null;  
         
         System.out.println("Do you want to continue :-");
            ch=scan.next().charAt(0);   
      }
    
    list.show(); 
  } 
}

In the above code, we are using LinkedList class and node a separate class. We have to define head, p and class node as static so that it can be accessed from main() function. The class node consists of a variable ‘value’ which holds data for each node and reference to the next node . We are assigning the value to each node starting from the head node and connecting the previous node to the current node using reference node p and next of current node making null. In this way, we are creating nodes one by one by asking the user whether he wants to continue.

In the show() function, we are starting from the head node and printing each node one by one till the last node. Criteria for checking to reach the last node is that next of the last node points to null.

Also learn,