LinkedList in Java Explained [Complete Tutorial]

Introduction to LinkedList in Java

In Java, the LinkedList class is a member of Java Collections Framework present in java.util package. This class implements List interface along with other interface like Serializable, Cloneable, Iterable, collection, Deque and Queue. This is basically doubly linked list implementation of List and Deque interfaces. It performs all the operations that can be performed with a doubly-linked list. All the operations that index into the list will either traverse the list from the beginning or the end, whichever is closer to the specified index.

When multiple threads are working on the same list, it has to be synchronized explicitly as this implementation is not synchronized. Moreover, the iterator returned by the class iterator and the listiterator methods are fail fast. So, if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.

 

Constructor of LinkedList Class in Java

There are two ways in which constructors are created for LinkedList in Java.

Empty constructor

When we create an object like as shown below, this empty constructor will be called. Hence, the statement below creates an empty LinkedList.

Example :

LinkedList l = new LinkedList();

 

Parameterized Constructor

When we want to initialize the list with the other collection then we call this parameterized constructor. Hence, the statement below will create a LinkedList already initialized with the elements of collection passed as a parameter.

Example :

LinkedList l = new LinkedList(c);

 

Different Methods of LinkedList Class in Java

The table below lists all the methods of LinkedList in Java.

 

Operations on LinkedList in Java

The basic operations that can be performed using LinkedList in Java are as listed below.

• Insertion Operation
• Deletion Operation
• Update Operation
• Traversal Operation

 

Insertion Operation in LinkedList

An element can be added to an existing LinkedList in six different ways as listed below.

1. Using add(element) method
2. Using add(index, element) method
3. Using addAll(collection) method
4. Using addAll(index, collection) method
5. Using addFirst(element) method
6. using addLast(element) method

Example : In this example, we will see the working of all methods used for inserting an element on an empty list.

// Program to perform Insertion operation on LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating an empty list l1
        LinkedList l1=new LinkedList<>();
        
        // Creating a list l2 with some values
        LinkedList l2=new LinkedList<>(Arrays.asList(30,40,50));
        
        // Adding the elements to list 1
        l1.add(10);
        l1.add(20);
        l1.add(null);
        
        System.out.println("After adding nodes to an empty list. List l1 = "+l1);
        
        // Adding elements at beginning and end of list
        l1.addFirst(5);
        l1.addLast(25);
        
        System.out.println("After adding nodes at first and last. List l1 = "+l1);
        
        // After adding node at index 4
        l1.add(4,15);
        System.out.println("After adding nodes at index 4. List l1 = "+l1);
        
        // appending list 2 to list 1
        l1.addAll(l2);
        System.out.println("After adding values from list l2, List l1 = "+l1);
        
    }
}

Output

After adding nodes to an empty list. List l1 = [10, 20, null]
After adding nodes at first and last. List l1 = [5, 10, 20, null, 25]
After adding nodes at index 4. List l1 = [5, 10, 20, null, 15, 25]
After adding values from list l2, List l1 = [5, 10, 20, null, 15, 25, 30, 40, 50]

 

Deletion Operation in LinkedList

An element can be removed from an existing LinkedList in seven different ways as listed below.

1. Using remove() method
2. Using remove(element) method
3. Using remove(index) method
4. Using removeFirst() method
5. Using removeFirstOccurrence(object) method
6. Using removeLast() method
7. using removeLastOccurrence(object) method

Example : In this example, we will see the working of all methods used to remove an element from the LinkedList.

// Program to remove the elements from a LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
        LinkedList l1=new LinkedList<>(Arrays.asList(5,10,15,20,null,20,30,40,50,10));
        
        // remove using the remove() method
        System.out.println("Element removed is "+l1.remove());
        System.out.println("After removal. List l1 = "+l1);
        
        // Removing the value from index 5
        System.out.println("Removing value from index 5 -"+l1.remove(5));
        System.out.println("After removal. List l1 = "+l1);
        
        // Removing the null value
        System.out.println("Removing by value - "+l1.remove(null));
        System.out.println("After removal. List l1 = "+l1);
        
        // Removing the First and last value
        System.out.println("Removing First value -"+l1.removeFirst());
        System.out.println("Removing Last value -"+l1.removeLast());
        System.out.println("After removal. List l1 = "+l1);
        
        // Removing the First and last value
        System.out.println("Removing First ocuurrence of 20 value "+l1.removeFirstOccurrence(20));
        System.out.println("Removing Last ocuurrence of 30 value "+l1.removeLastOccurrence(30));
        System.out.println("After removal. List l1 = "+l1);
    }
}

Output

Element removed is 5
After removal. List l1 = [10, 15, 20, null, 20, 30, 40, 50, 10]
Removing value from index 5 -30
After removal. List l1 = [10, 15, 20, null, 20, 40, 50, 10]
Removing by value - true
After removal. List l1 = [10, 15, 20, 20, 40, 50, 10]
Removing First value -10
Removing Last value -10
After removal. List l1 = [15, 20, 20, 40, 50]
Removing First ocuurrence of 20 value true
Removing Last ocuurrence of 30 value false
After removal. List l1 = [15, 20, 40, 50]

 

Update operation in a LinkedList

An existing node in the list can be updated with the new value using the set method of LinkedList in Java.

Example : Here, we are updating the value at index 5 in the existing list.

// Program to update the value in LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
        LinkedList l1=new LinkedList<>(Arrays.asList(5,10,15,20,null,20,30,40,50,10));

        System.out.println("Before updation List l1 = "+l1);
        l1.set(5,25);
        System.out.println("After updating value at index 5. List l1 = "+l1);
    }
}

Output

Before updation List l1 = [5, 10, 15, 20, null, 20, 30, 40, 50, 10]
After updating value at index 5. List l1 = [5, 10, 15, 20, null, 25, 30, 40, 50, 10]

 

Traversing a LinkedList

Traversing a list means that we retrieve value from each node in the list in a sequential order. We can perform this operation using the get method of LinkedList in Java.

Example : Here, we are traversing through all the elements of the list in a sequential manner.

// Program to traverse a LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
        LinkedList l1=new LinkedList<>(Arrays.asList(5,10,15,20,30,40,50,10));

        System.out.println("Traversing a list");
        for(int i=0;i<l1.size();i++)
            System.out.println("Value at index "+i+" is "+l1.get(i));
    }
}

Output

Traversing a list
Value at index 0 is 5
Value at index 1 is 10
Value at index 2 is 15
Value at index 3 is 20
Value at index 4 is 30
Value at index 5 is 40
Value at index 6 is 50
Value at index 7 is 10

 

Stack implemented using LinkedList

We can implement stack data structure using the LinkedList class in Java. The basic operations of Stack like Push and Pop can be implemented using the built-in methods of LinkedList class. The code below shows the menu driven program to implement stack using LinkedList in Java.

// Program to implement Stack using LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
        LinkedList l1=new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        int ch;
        do
	    {
	       System.out.println("\nEnter your choice \n1.Push \n2.Pop\n3.Peek");
	       ch=sc.nextInt();
	       switch(ch)
	       {
			case 1:
			// Push value on the Stack
			System.out.println("Enter a data value");
			int val=sc.nextInt();
			l1.push(val);
			break;
			case 2:
			// Pop the value from the Stack
			System.out.println("Popped out value - "+l1.pop());
			break;
			case 3:
			// Peek the value from the Stack
			System.out.println(l1.peek()+" is on the top of the Stack");
			break;
	       }
	}while(ch<4);      
    }
}

Output

Enter your choice 
1.Push 
2.Pop
3.Peek
1
Enter a data value
10
Enter your choice 
1.Push 
2.Pop
3.Peek
1
Enter a data value
20
Enter your choice 
1.Push 
2.Pop
3.Peek
1
Enter a data value
30
Enter your choice 
1.Push 
2.Pop
3.Peek
1
Enter a data value
40
Enter your choice 
1.Push 
2.Pop
3.Peek
2
Popped out value - 40
Enter your choice 
1.Push 
2.Pop
3.Peek
3
30 is on the top of the Stack
Enter your choice 
1.Push 
2.Pop
3.Peek
4

 

Queue implemented using LinkedList

We can implement queue data structure using the LinkedList class in Java. The basic operations of Queue like Enqueue and Dequeue can be implemented using the built-in methods of LinkedList class. The code below shows the menu driven program to implement queue using LinkedList in Java.

// Program to implement Queue using LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
        LinkedList l1=new LinkedList<>();
        Scanner sc = new Scanner(System.in);
        int ch;
        do
	    {
	       System.out.println("\nEnter your choice \n1.Enqueue \n2.Dequeue");
	       ch=sc.nextInt();
	       switch(ch)
	       {
			case 1:
			// Enqueue element on a queue
			System.out.println("Enter a data value");
			int val=sc.nextInt();
			l1.offerLast(val);
			break;
			case 2:
			// Dequeue the element from queue
			System.out.println("Dequeued value - "+l1.pollFirst());
			break;			
	       }
	}while(ch<3);       
    }
}

Output

Enter your choice 
1.Enqueue 
2.Dequeue
1
Enter a data value
10
Enter your choice 
1.Enqueue 
2.Dequeue
1
Enter a data value
20
Enter your choice 
1.Enqueue 
2.Dequeue
1
Enter a data value
30
Enter your choice 
1.Enqueue 
2.Dequeue
2
Dequeued value - 10
Enter your choice 
1.Enqueue 
2.Dequeue
2
Dequeued value - 20
Enter your choice 
1.Enqueue 
2.Dequeue
2
Dequeued value - 30
Enter your choice 
1.Enqueue 
2.Dequeue
2
Dequeued value - null
Enter your choice 
1.Enqueue 
2.Dequeue
4

 

Converting LinkedList to an Array

In many situations, we will need to use the elements of a linked list as an array. The toArray() method of LinkedList allows us to convert the list to an array in proper sequence.

// Program to convert an Array from LinkedList in Java
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        // Creating a list l1 with some values
         LinkedList l1=new LinkedList(Arrays.asList(5,10,15,20,30,40,50,10));
         
         // Declaring an array
         Object[] a=new Object[l1.size()];
         
         // Converting list to an array
         a=l1.toArray();
         
         // Printing an array elements
         for(int i=0;i<a.length;i++)
         {
             System.out.println(a[i]);
         }
    }
}

Output

5
10
15
20
30
40
50
10

 

Summary

The knowledge of LinkedList in Java is very useful while working on real time applications. In many situations, we will need to maintain the ordered collection of elements where we need to make a selection of appropriate methods to perform the operations. In this tutorial, we covered constructors and methods of LinkedList class along with the important operations that can be performed using the built-in methods of LinkedList class with the example. As per the requirement of an application, we can choose an appropriate methods. We learned in detail about this with an example. All in all, this tutorial, covers everything that you need to know in order to have a clear view on LinkedList in Java.

 

References

LinkedList Class