Linked List in Java

A linear data structure used to store the elements in contiguous locations is called a Linked List in Java. It has addresses and pointers that are used to link the elements, and each element in the linked list consists of two parts, namely the data part and the address part. The data part is the value of the element, and the address part consists of the pointers and addresses that are used to link the elements. Each element in the list is called a node.

The syntax to define a Linked list in Java is as follows:

LinkedList <data_type> linkedlistname = new LinkedList<data_type>();

where data_type is the data type of the elements to be stored in the linked list,

linkedlistname is the name of the .linked list.

The usage of a linked list allows dynamic insertion and deletion of elements into the linked list. Because of this feature, linked lists are preferred over arrays.

Working Of Linked List in Java Is As Follows:

  • A linked list in Java is a dynamic data structure whose size increases as you add the elements and decreases as you remove the elements from the list.
  •  The elements in the linked list are stored in containers.
  • The list holds the link to the first container.
  • All the containers have a link to the next container in the list.
  •  Whenever you add an element to the list using add() operation, a new container is created, and this container is linked to the other containers in the list.

The Hierarchy of Linked Lists Is Explained as Follows:

The linked list extends to the Abstract Sequential List, which in turn implements a list that extends the collection interface, which further extends the Iterable interface. The Linked list implements the deque interface which extends the Queue interface, which then extends the collection interface, which further extends the Iterable interface.

FREE Java Certification Training

Learn A-Z of Java like never beforeEnroll Now
FREE Java Certification Training

There Are Various Types of Linked List. They Are:

  • Singular Linked List
  • Doubly Linked List
  • Circular Linked List

Singular Linked List

LinkedListInJava_1

  • The type of linked list consisting of a sequence of nodes where each node consists of data and a link to the next node, that can be traversed from the first node of the list (also called as head) to the last node of the list (also called as Tail)  and is unidirectional is called Singly Linked list. 
  • The above figure demonstrates a singly linked list.
  • Each element in the list is called a node.
  • A node is made of two parts, namely data and pointer.
  • Data is the data stored in the   and the pointer is the next node in the list.
  • The first node in the list is referred to as the head of the list.
  • The last node in the list is the tail, and it points to NULL.

The syntax to define a node in a singular linked list is as follows:

public class SinglyLinkedList 

{    

       class Node

{    

               int data;    

               Node next;                

               public Node(int data) 

{    

                           this.data = data;    

                           this.next = null;    

               }    

       }    

}

Example 1:

Java program to demonstrate the creation of a singly Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:

public class SinglyLinkedList 

{    

    //defining a node in singly linked list  

    class Node

    {    

        int data;    

        Node next;                

        public Node(int data) 

        {    

            this.data = data;    

            this.next = null;    

        }    

    }         

    //defining the head and tail of a singly linked list   

    public Node head = null;    

    public Node tail = null;          

    //defining insert() function to add a node to the list   

    public void insert(int data) 

    {    

        //Creating a new node   

        Node newNode = new Node(data);               

        //checking of the list is empty   

        if(head == null) 

        {    

//if the given list is empty, making the two nodes head and tail to point to the newly created node newNode    

            head = newNode;    

            tail = newNode;    

        }    

        else 

        {    

//otherwise the newNode will be added after tail so that the next pointer of tail points to    the newNode   

            tail.next = newNode;    

            tail = newNode;    

        }    

    }          

    //defining displaylist() function to display the data in the list  

    public void displaylist() 

    {    

        //Pointing the head to the node called current    

        Node current = head;               

        if(head == null)

        {    

            System.out.println("The given list is empty");    

            return;    

        }    

        System.out.println("The data in the given list are: ");    

        while(current != null) 

        {    

            //printing each data in the list and next pointer pointing to the next node   

            System.out.print(current.data + " ");    

            current = current.next;    

        }    

        System.out.println();    

    }            

    public static void main(String[] args)

    {    

        //creating a new list    

        SinglyLinkedList newList = new SinglyLinkedList();                

        //Adding data to the list by calling the insert function  

        newList.insert(10);    

        newList.insert(30);   

        newList.insert(50); 

        newList.insert(70); 

        newList.insert(100);             

        //Displaying the data in the list by calling displaylist() function    

        newList.displaylist();    

    }    

}    

The output of the above program is shown in the snapshot below:

LinkedListInJava_2.

Doubly Linked List

LinkedListInJava_3.

  • This type of a linked list consists of a sequence of nodes where each node consists of data and two pointers, namely the previous pointer pointing to the previous node and the subsequent pointer that points to the next node that is part of the list. This can be traversed from the first node of the list to the last node of the list and vice versa, and this is called Doubly Linked list.
  • The above figure demonstrates a doubly linked list.
  • Data is the data stored in the node and each node consists of two pointers namely the previous pointer and the next pointer.
  • The previous pointer points, as the name suggests to the previous node that is part of the list.
  • The pointer after the current one, points to the next node on the list.

The syntax to define a node in a doubly linked list is as follows:

public class DoublyLinkedList

{  

    class Node

    {  

        int data;  

        Node previous;  

        Node next;    

        public Node(int data)

        {  

            this.data = data;  

        }  

    }

}  

Example 2:

Java program to demonstrate the creation of a doubly Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:

public class DoublyLinkedList 

{    

    //defining a node in a doubly linked list 

    class Node

    {  

        int data;  

        Node previous;  

        Node next;   

        public Node(int data)

        {  

            this.data = data;  

        }  

    }   

    //defining the head and tail of the doubly linked list and assigning it to Null

    Node head, tail = null;   

    //defining insert() function to insert the data into the list  

    public void insert(int data)

    {  

        //creating a new node called newNode  

        Node newNode = new Node(data);   

        //checking if the given list is empty 

        if(head == null) 

        {  

            //if the lists empty, making both head and tail of the list to point to the newNode  

            head = tail = newNode;  

            //the previous pointer of head will point to null  

            head.previous = null;  

            //the next pointer of tail will point to the null 

            tail.next = null;  

        }  

        else 

        {  

            //otherwise the next pointer of tail will point to the newNode  

            tail.next = newNode;  

            //the previous pointer of the newNode will point to the tail  

            newNode.previous = tail;  

            //and the newNode is made the tail of the list  

            tail = newNode;  

//and the next pointer of tail is made to point to null indicating it is the last node of the list  

            tail.next = null;  

        }  

    }  

  

    //defining displaylist() function to display the data in the list  

    public void displaylist() 

    {  

        //defining a node called current and assigning the head of the list to it 

        Node current = head; 

        //checking if the head/list is empty

        if(head == null) 

        {  

            System.out.println("The given list is empty");  

            return;  

        }  

        //otherwise printing each element in the list

        System.out.println("The data in the doubly linked list are: ");  

        while(current != null) 

        {  

            //printing each data in the list and next pointer pointing to the next node 

            System.out.print(current.data + " ");  

            current = current.next;  

        }  

    } 

    public static void main(String[] args)

    {  

        //defining a new doubly linked list

        DoublyLinkedList newList = new DoublyLinkedList();  

        //inserting data into the list by calling insert() function

        newList.insert(10);  

        newList.insert(30);  

        newList.insert(50);  

        newList.insert(70);  

        newList.insert(100);   

        //displaying the data in the list by calling displaylist() function

        newList.displaylist();  

    }  

}  

The output of the above program is shown in the snapshot below:

LinkedListInJava_4

Circular Linked List

LinkedListInJava_5.

It is the type of linked list consisting of a sequence of nodes where each node consists of data and a link to the next node and the last node in the list (also called as tail) that points to the first node in the list (also called as head) is called as Circular Linked List.

The figure above demonstrates a Circular linked list.

The syntax to define a node in a circular linked list is as follows:

public class CircularLinkedList 

{  

    public class Node

    {  

        int data;  

        Node next;  

        public Node(int data)

        {  

            this.data = data;  

        }  

    } 

Example 3:

Java program to demonstrate the creation of a circular Linked list in Java and insertion of elements into the list and then display the elements of the list as the output on the screen:

public class CircularLinkedList

{  

    //defining a node in circular linked list  

    public class Node

    {  

        int data;  

        Node next;  

        public Node(int data) 

        {  

            this.data = data;  

        }  

    }   

    //defining the head and tail of the circular linked list and assigning it to Null

    public Node head = null;  

    public Node tail = null;  

    //defining insert() function to insert the data into the list  

    public void insert(int data)

    {  

        //creating a new node called newNode 

        Node newNode = new Node(data);  

        //checking if the given list is empty   

        if(head == null) 

        {  

//If list is empty, making both the head and tail point to the newNode and the next pointer of newNode to head  

            head = newNode;  

            tail = newNode;  

            newNode.next = head;  

        }  

        else 

        {  

            //otherwise the next pointer of the tail is made the newNode

            tail.next = newNode;  

            //and the newNode is made the tail of the list  

            tail = newNode;  

//and the next pointer of the tail is made to point to the head of the list as it is a circular linked list

            tail.next = head;  

        }  

    }   

    //defining displaylist() function to display the data in the list  

    public void displaylist() 

    {  

        //defining a node called current and assigning the head of the list to it 

        Node current = head; 

        //checking if the head/list is empty

        if(head == null)

        {  

            System.out.println("The given list is empty");  

        }  

        else 

        {  

            //otherwise printing each element in the list

            System.out.println("The data in the circular linked list are: ");  

             do{  

                 //printing each data in the list and next pointer pointing to the next node   

                System.out.print(" "+ current.data);  

                current = current.next;  

            }

            while(current != head);  

            System.out.println();  

        }  

    }   

    public static void main(String[] args) 

    {  

         //defining a new circular linked list

        CircularLinkedList newList = new CircularLinkedList();  

        //inserting data into the list by calling insert() function

        newList.insert(10);  

        newList.insert(30);  

        newList.insert(50);  

        newList.insert(70);

        newList.insert(100);

        //displaying the data in the list by calling displaylist() function

        newList.displaylist();  

    }  

}  

The output of the above program is shown in the snapshot below:

LinkedListInJava_6

Full Stack Java Developer Course

The Gateway to Master Web DevelopmentExplore Course
Full Stack Java Developer Course

Various operations can be performed on the elements in a Linked list in Java. Those operations are:

1. Insert Elements to the List

The elements can be inserted into a given list at the beginning of the list, at the end of the list, or at a specified position of the list.

Insertion at the Beginning of the List

  • A new node to store the data is created 
  • The next pointer of the new node is made to point to the head of the list 
  • The new node is then made the head of the list

Insertion at the End of the List

  • A new node to store the data is created 
  • The entire list is traversed to reach the last node of the list
  • The next pointer of the last node is made to point to the new node of the list making the new node the last node of the list

Insertion at the Specified Position of the List

  • A new node to store the data is created
  • The list is traversed to reach the node which is just before the node at the specified position of the list
  • The next pointers are made to point to the new node of the list making the new node one of the nodes in the list 

2. Delete Elements From the List

The elements can be deleted from a given list from the beginning of the list, from the end of the list, or from a specified position of the list.

Deletion From the Beginning of the List

  • The head of the list is made to point to the second node of the list

Deletion From the End of the List

  • The entire list is traversed to reach the second last node of the list
  • The next pointer of the second last node is made to point to null

Deletion From a Specified Position of the List

  • The list is traversed to reach the node which is just before the node to be deleted at the specified position of the list
  • The next pointers are changed to remove the node at the specified position of the list 

Example 4:

Java program to demonstrate the insertion of an element at the beginning of the list, insertion at the end of the list, insertion at a specified position of the list, deletion from the beginning of the list, deletion from the end of the list and deletion from the specified position of the list and then display the elements of the list as the output on the screen:

public class LinkedList

{

//defining a node in singly linked list

class Node 

{

private int data;

private Node next;

public Node(int data) 

{

this.data = data;

this.next = null;

}

}

    public Node head = null;  

    //defining a method to insert an element at the beginning of the list

   public void insertionatthebeginning(int data)

   {

        System.out.println("Adding a node at the beginning of the list with data " + data + "\n");

//creating a new node called newNode 

Node newNode = new Node(data);

//checking if the given list is empty 

if (this.head == null)

{

//if the list is empty, making the newNode as the head of the list

this.head = newNode;

else 

{

//otherwise the next pointer of the newNode is made the head

newNode.next = this.head;

//and then making the newNode as the head of the list

this.head = newNode;

}

 //defining a method to insert an element at the end of the list

public void insertionattheend(int data) 

{

        System.out.println("Adding a node at the end of the list with data " + data + "\n");

//creating a new node called newNode 

Node newNode = new Node(data);

//checking if the given list is empty 

if (this.head == null) 

{

//if the list is empty, making the newNode as the head of the list

this.head = newNode;

else 

{

//otherwise create a new node called current and assign head of the list to the current node

Node current = this.head;

//and traverse till the end of the list

while (current.next != null)

{

//and assign each node to the current node till the last node is reached

current = current.next;

}

//assigning the next pointer of the last node to the newNode

current.next = newNode;

}

//defining a method to insert an element at the specified position of the list

public void insertionatpos(int position, int data) 

{

System.out.println("Adding a node at the specified position " + position + " of the list with data " + data + "\n");

//creating a new node called newNode

Node newNode = new Node(data);

//creating two new nodes called current and previous and then assigning head of the list to these two nodes

Node current = this.head;

Node previous = this.head;       

         //checking if the element to be inserted at position 1

if (position == 1) 

{

//then the next pointer of the new node is made to point to the head

newNode.next = head;

//and the new node is made the head of the list

this.head = newNode;

return;

}

//otherwise the entire list is traversed until the specified position is found by assigning current to previous and next pointer of current to current

while (current.next != null && position > 0) 

{

previous = current;

current = current.next;

}

//then the new node is inserted at the next pointer of previous node

previous.next = newNode;

// and the next pointer of new node is made the current node

newNode.next = current;

}

    //defining a method to delete an element from the beginning of the list

    public void deletionfromthebeginning()

   {

         System.out.println("deleting a node from the beginning of the list: \n");

//checking if the given list is empty

if (this.head == null)

{

System.out.println("The given list is empty.\n");

else 

{

//otherwise removing head and making the first node as the head of the list

head = head.next;

}

}

//defining a method to delete an element from the end of the list

public void deletionfromtheend()

{

         System.out.println("Deleting a node from the end of the list: \n");

//checking if the given list is empty

if (this.head == null)

{

System.out.println("The given list is empty.\n");

else 

{

//otherwise creating a new node called current and assigning head to it to traverse through the list to reach the second last element of the list and then making its next pointer to point to null

Node current = this.head;

while (current.next.next != null)

{

current = current.next;

    }

    current.next = null;

    }

}

//defining a method to delete an element from the specified position of the list

public void deletionfrompos(int position) 

{

System.out.println("Deleting a node from the specified position " + position +  "\n");

         //checking if the given list is empty

    if (this.head == null)

{

System.out.println("The given list is empty.\n");

//checking if the given position is 0 

else if(position == 0)

{

//removing the head of the list and making the first node of the list as the head of the list

head = head.next;

    }

    else

    {

//otherwise creating a new node called current and making it head of the list

      Node current = head;

        //then traversing through the list

        for(int i =0; current!=null && i < position -1; i++)

        {

          current = current.next;

          //checking if the element is not present at all in the list

          if(current == null || current.next == null)

            {

                System.out.println("The element is not present at the specified position.\n");

          }

//removing the node at the specified position of the list and assigning the next pointer of the current node to point to the next to next node

          Node temp = current.next.next;

            current.next = temp;

        }

  }

}

//defining displaylist() function to display the data in the list  

   public void displaylist() 

   {

       //checking if the head/list is empty

if (this.head == null)

{

System.out.println("The given list is empty.\n");

else 

{

    //otherwise printing each element in the list

System.out.println("The elements of the Singly Linked List are : \n");

Node current = this.head;

while (current != null)

{

//printing each data in the list and next pointer pointing to the next node  

System.out.print(current.data + " -> ");

current = current.next;

}

System.out.println("NULL\n");

}

}  

   public static void main(String[] args)

   {

       //defining a new linked list

           LinkedList newlist = new LinkedList();

           //displaying the elements of the list before performing any operation on the list

System.out.println("The elements of the singly linked list before insertion operation     are: \n");

    newlist.displaylist();

//performing various operations on the list and then displaying the elements of the list

newlist.insertionatthebeginning(1);

    newlist.displaylist();

    System.out.println("\n");

newlist.insertionatthebeginning(2);

newlist.displaylist();

System.out.println("\n");

       newlist.insertionattheend(8);

    newlist.displaylist();

    System.out.println("\n");

newlist.insertionattheend(9);

newlist.displaylist();

System.out.println("\n");

         newlist.insertionatpos(2,3);

         newlist.displaylist();

         System.out.println("\n");

         newlist.insertionatpos(3,4);

         newlist.displaylist();

         System.out.println("\n");

         newlist.insertionatpos(4,5);

         newlist.displaylist();

         System.out.println("\n");

         newlist.deletionfromthebeginning();

         newlist.displaylist();

         System.out.println("\n");

         newlist.deletionfromtheend();

         newlist.displaylist();

         System.out.println("\n");

         newlist.deletionfrompos(3);

        newlist.displaylist();

         System.out.println("\n");

    }

}

The output of the above program is shown in the snapshot below:

/LinkedListInJava_7.

LinkedListInJava_8

LinkedListInJava_9

Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE CoursesEnroll Now
Stand Out From Your Peers this Appraisal Season

There are two constructors associated with the Linked List in Java. They are:

  • LinkedList()

An empty linked list can be created using the constructor LinkedList().

The syntax to create an empty linked list using LinkedList() constructor is as follows:

                   LinkedList listname = new LinkedList();

Example 5:

Java program to demonstrate the creation of an empty linked list using LinkedList() constructor:

  public class LinkedList 

  {    

     //defining a node in a linked list  

     class Node

     {    

         int data;    

         Node next;                

         public Node(int data) 

         {    

             this.data = data;    

             this.next = null;    

         }    

     }         

     //defining the head and tail of a linked list   

     public Node head = null;    

    public Node tail = null;        

    //defining insert() function to add a node to the list   

     public void insert(int data) 

     {    

         //Creating a new node   

         Node newNode = new Node(data);               

         //checking of the list is empty   

         if(head == null) 

        {    

//if the given list is empty, making the two nodes head and tail to point to the newly created node newNode    

             head = newNode;    

             tail = newNode;    

         }    

         else 

        {    

//otherwise the newNode will be added after tail so that the next pointer of tail points to the newNode   

             tail.next = newNode;    

             tail = newNode;    

         }    

     }            

     //defining displaylist() function to display the data in the list  

     public void displaylist() 

     {    

         //Pointing the head to the node called current    

         Node current = head;               

        if(head == null)

         {    

             System.out.println("The given list is empty");    

             return;    

         }    

         System.out.println("The data in the given list are: ");    

         while(current != null) 

         {    

             //printing each data in the list and next pointer pointing to the next node   

             System.out.print(current.data + " ");    

             current = current.next;    

         }    

        System.out.println();    

    }          

    public static void main(String[] args)

     {    

        //creating a new list    

         LinkedList newList = new LinkedList();              

         //Adding data to the list by calling the insert function  

         newList.insert(10);    

         newList.insert(30);   

         newList.insert(50); 

                 //Displaying the data in the list by calling displaylist() function    

         newList.displaylist();    

    }    

}    

The output of the above program is shown in the snapshot below:

LinkedListInJava_10

  • LinkedList(Collection C)

To create a list made of all the elements from a specific collection C, you need to make use of the constructor LinkedList(Collection C).

The syntax to create the linked list formed by the elements of a specific collection using LinkedList(Collection C) constructor is as follows:

                   LinkedList listname = new LinkedList(c);

Example 6:

Java program to demonstrate the creation of an empty linked list using LinkedList(Collection C) constructor:

 import java.util.*;  

 import java.util.ArrayList;

 import java.util.LinkedList;

 //defining a class called demo

 public class demo

 {    

     //main method is called    

    public static void main(String[] args)

     {         

         defining a string arraylist collection

         ArrayList<String> collect = new ArrayList<String>();

         collect.add("Simplilearn");

         collect.add("is");

         collect.add("Awesome");      

//passing the collection as a parameter to the LinkedList constructor

         LinkedList List2 = new LinkedList(collect);

         //displaying the elements of the list

         System.out.println("The new linked list is: " + List2);

    }    

}    

The output of the above program is shown in the snapshot below:

LinkedListInJava_11

There are several methods associated with a Linked List in Java. Some of them are:

  • add()

The add() method is used to insert elements into the list.

  • addFirst()

The addFirst() method is used to insert elements to the beginning of the list.

  •  addLast()

The addLast() method is used to insert elements at the end of the list.

  • remove()

The remove() method is used to remove the elements from the list. 

  • removeFirst()

The removeFirst() method is used to remove the elements from the beginning of the list.

  •  removeLast()

The removeFirst() method is used to remove the elements from the end of the list.

  •  getFirst()

The getFirst() method is used to get the elements from the beginning of the list.

  •  getLast()

The getLast() method is used to get the elements from the end of the list.

  • clear()

The clear() method is used to remove all the elements from the list.

  • clone()

A shallow copy of the linked list is returned using clone() method.

  • peek()

The head of the list is retrieved using peek() method.

  • peekFirst()

The first element of the list is retrieved using peekFirst() method.

  • peekLast()

The last element of the list is retrieved using peekLast() method.

  • poll()

The head of the list is retrieved and removed using poll() method.

  • pollFirst()

The first element of the list is retrieved and removed using pollFirst() method.

  • pollLast()

The last element of the list is retrieved and removed using pollLast() method.

  • size()

The number of elements present in the list is returned using size() method.

  • get(int index)

The element present at the position specified by the index is returned using get(int index) method.

  • element()

The head of the list is retrieved but not removed using element() method.

Get a firm foundation in Java, the most commonly used programming language in software development with the Java Certification Training Course.

Conclusion

In this article, you looked into the concept of Linked List in Java, types of linked lists through programming examples to demonstrate them and their outputs, constructors, and methods associated with linked lists. Simplilearn offers Online Java Certification Course designed to help you learn everything in Java to kick start your career in Java and this is a very flexible way to acquire skills in Java.

Do you have questions for us? Please leave them in the comments section, and our experts will get back to you on the same, at the earliest. Happy learning!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.