LinkedList in Java

LinkedList in Java is a linear data structure that is present in the java.util package. It is similar to ArrayList in Java and we can perform operations like adding an element, removing an element, etc. In this tutorial, we will understand about Java LinkedList.

Java LinkedList

Java LinkedList is a doubly-linked list that can store any type of data. It extends the AbstractList class and implements the List and Deque interfaces. It is called a doubly linked list since it contains a link to the previous node as well as the next successive node. LinkedList contains a collection of nodes and implements a linear data structure. We call each element in the list as a node. We name the first element in the list as head and the last element as a tail.

Features of LinkedList in Java

• It can contain any type of elements
• It allows storing duplicate values.
• Maintains insertion order.
• It is faster than arrays since there is no shifting of elements during insertion.

Working of a LinkedList in Java

As we discussed, LinkedList uses a double LinkedList. This means each node contains 3 parts: the first part has a reference to the previous node, the second part contains the value of the element and the third part contains the reference to the next node. You can understand this clearly from the pictorial representation.

The first element in the LinkedList will have null in the previous node reference and the last element in the LinkedList will have null in the next node reference.

Java LinkedList Hierarchy

Constructors in LinkedList

Below are the 2 constructors which we can use in Java LinkedList:

Java LinkedList Methods

Below is the list of commonly used methods for a Java LinkedList.

Create a new LinkedList in Java

We can create a new LinkedList in Java as below:

LinkedList<Type> list_variable = new LinkedList<Type>();

Type – specifies the type of data that you want to store in the list. Eg: String, Integer, etc

list_variable – the variable name of the linked list

Now, let us see different examples of how to use the Java LinkedList methods that we discussed above.

Example: Create and Add elements to the list

Below is an example to create a new LinkedList called names and add elements to the list. We can add an element at a specified index using the add method and passing the index value, add an element at beginning of the list using the addFirst method, and add an element at the end of the list using the addLast method. We can also add a collection of elements to the LinkedList using the addAll method.

import java.util.LinkedList;

public class AddListElements {

  public static void main(String[] args) {
    
    //Create a linked list
    LinkedList<String> names = new LinkedList<String>();
    LinkedList<String> newnames = new LinkedList<String>();
    
    //Add elements to the list
    names.add("Ramesh");
    names.add("Suresh");
    names.add("Ganesh");
    
    System.out.println("List elements: " + names);
    
    //Add element to the specified index
    names.add(1, "Jayesh");
    
    System.out.println("List elements after add at specified index: " + names);
    
    //Add element at the beginning of the list
    names.addFirst("Rupesh");
    
    //Add element at the end of the list
    names.addLast("Mahesh");
    
    System.out.println("List elements after addFirst and addLast: " + names);
    
    //Create a new collection list
    newnames.add("Divya");
    newnames.add("Ramya");
    
    //Add collection to the existing linked list
    names.addAll(newnames);
    
    System.out.println("List elements after adding collection of elements: " + names);
  }

}

List elements: [Ramesh, Suresh, Ganesh]
List elements after add at specified index: [Ramesh, Jayesh, Suresh, Ganesh]
List elements after addFirst and addLast: [Rupesh, Ramesh, Jayesh, Suresh, Ganesh, Mahesh]
List elements after adding collection of elements: [Rupesh, Ramesh, Jayesh, Suresh, Ganesh, Mahesh, Divya, Ramya]

Example: Remove elements from the list

Below is an example to remove elements from the LinkedList. We can remove an element at the specified index, a first element, last element, and collection of elements from the list.

import java.util.LinkedList;

public class RemoveListElements {

  public static void main(String[] args) {
    LinkedList<Integer> numbers = new LinkedList<Integer>();
    LinkedList<Integer> num = new LinkedList<Integer>();
    numbers.add(54);
    numbers.add(64);
    numbers.add(24);
    numbers.add(14);
    numbers.add(84);
    numbers.add(94);
    numbers.add(44);
    
    System.out.println("List elements: " + numbers);
    
    //Removes the head element
    numbers.remove();
    
    System.out.println("List elements after remove: " + numbers);
    
    //Removes the element at the specified index
    numbers.remove(2);
    
    System.out.println("List elements after removing element at specified index: " + numbers);
    
    //Removes the specified element
    numbers.removeFirst();	
    System.out.println("List elements after removing the first element: " + numbers);
    
    //Removes the last element
    numbers.removeLast();
    System.out.println("List elements after removing the last element: " + numbers);
    
    //Create a collection list
    num.add(12);
    num.add(22);
    
    numbers.addAll(num);
    System.out.println("List elements after adding collection: " + numbers);
    
    //Remove a collection from list
    numbers.removeAll(num);
    System.out.println("List elements after removeAll: " + numbers);

  }

}

List elements: [54, 64, 24, 14, 84, 94, 44]
List elements after remove: [64, 24, 14, 84, 94, 44]
List elements after removing element at specified index: [64, 24, 84, 94, 44]
List elements after removing the first element: [24, 84, 94, 44]
List elements after removing the last element: [24, 84, 94]
List elements after adding collection: [24, 84, 94, 12, 22]
List elements after removeAll: [24, 84, 94]

Example: Other methods of the LinkedList

Below is an example of other useful methods in the Java LinkedList. We can insert an element at the beginning of the list using the push method and retrieve the first element using the element method. We can get the element based on a specified index using the get method. To remove and retrieve the first element, we use the pop method. We can replace a specific value based on the index using the set method and get the size of the list using the size method. We can check if a list is empty or not using the isEmpty method.

import java.util.Deque;
import java.util.LinkedList;
public class LinkedListDemo {

  public static void main(String[] args) {
    LinkedList<String> cities = new LinkedList<String>();
    
    cities.add("Chennai");
    cities.add("Bangalore");
    
    //Inserts element at the beginning
    cities.push("Kolkata");
    
    System.out.println(cities);
    
    //Retrieves first element
    System.out.println("Output of element() method: " + cities.element());
    
    System.out.println("Out of get method at specified index 2: " + cities.get(2));
    
    //Retrieves and removes the first element
    System.out.println("Output of pop() method: " + cities.pop());
    System.out.println(cities);
    
    //Check if list is empty
    System.out.println("Is LinkedList empty: " + cities.isEmpty());
    
    //Replaces the element at index 1 with new value
    cities.set(1, "Goa");
    System.out.println("List elements after using set() method: " + cities);
    
    //List size
    System.out.println("Size of the LinkedList: " + cities.size());
  }

}

[Kolkata, Chennai, Bangalore]
Output of element() method: Kolkata
Out of get method at specified index 2: Bangalore
Output of pop() method: Kolkata
[Chennai, Bangalore]
Is LinkedList empty: false
List elements after using set() method: [Chennai, Goa]
Size of the LinkedList: 2

Example: Empty or clear the LinkedList in Java

Below is an example of clearing or emptying LinkedList using the clear() method. We can check if the list is empty using the isEmpty() method. If it returns true, it means the list is empty.

import java.util.LinkedList;

public class ClearLinkedList {

  public static void main(String[] args) {
    LinkedList<String> l = new LinkedList<String>();
    l.add("Java");
    l.add("C");
    l.add("C++");
    
    System.out.println("Contents in the List: " +l);
    
    //Clear the list
    l.clear();
    System.out.println("Is List empty: " + l.isEmpty());
    System.out.println("Contents in the List: " + l);
    
  }

}

Contents in the List: [Java, C, C++]
Is List empty: true
Contents in the List: []

Different ways to iterate through a LinkedList in Java

There are different ways to iterate through elements in a LinkedList. We can use for loop, for each loop, while loop or Iterator to traverse through elements in the list.

Using for loop

In the below example, we can iterate through every element in the list using the for loop. We can retrieve the value using the get method.

import java.util.LinkedList;

public class LinkedListForLoop {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    //Using for loop
    System.out.println("Iterate using for loop:");
    for(int i=0;i<list.size();i++)
      System.out.println(list.get(i));

    
  }

}

Iterate using for loop:
Apple
Banana
Grapes
Pear
Papaya

Using a for-each loop

Below is an example of iterating through LinkedList using for-each loop.

import java.util.LinkedList;

public class LinkedListForEach {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    //Using for each loop
    System.out.println("Iterate using for each loop:");
    for(String fruits : list)
      System.out.println(fruits);

  }

}

Iterate using for each loop:
Apple
Banana
Grapes
Pear
Papaya

Using while loop

We can also use a while loop to traverse through elements in the LinkedList as in the below example. Using the size method, we get the list size, and using the get method, we can retrieve individual elements.

import java.util.LinkedList;

public class LinkedListWhileLoop {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    System.out.println("Iterate using while loop:");
    
    int i=0;
    while(i<list.size())
    {
      System.out.println(list.get(i));
      i++;
    }

  }

}

Iterate using while loop:
Apple
Banana
Grapes
Pear
Papaya

Using iterator and listiterator

In the below example, we use iterator and ListIterator to navigate through individual elements in the list. Using the next method of the iterator, we can get the elements one by one until it reaches the end of the list. We use the hasNext method to check if there is the next element in the list.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListIterator {

  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.add("Apple");
    list.add("Banana");
    list.add("Grapes");
    list.add("Pear");
    list.add("Papaya");
    
    System.out.println("Iterate using iterator:");
    //Using iterator
    Iterator<String> i = list.iterator();
    while(i.hasNext())
      System.out.println(i.next());

    System.out.println("Iterate using listiterator:");
    ListIterator<String> li = list.listIterator();
    while(li.hasNext())
      System.out.println(li.next());
  }

}

Iterate using iterator:
Apple
Banana
Grapes
Pear
Papaya
Iterate using listiterator:
Apple
Banana
Grapes
Pear
Papaya

LinkedList as Deque and Queue

We can use the methods of the Deque and Queue interface since the LinkedList class implements both interfaces. To add elements to the beginning and end of the list, we use addFirst and addLast methods. We use getFirst and getLast methods to retrieve the first and last elements. To remove the first and last element, we use removeFirst and removeLast methods. We use the poll method to retrieve and remove the first element from the list.

import java.util.Deque;
import java.util.LinkedList;

public class DequeLinkedList {

  public static void main(String[] args) {
    Deque<String> lang = new LinkedList<>();
    lang.add("Python");
    lang.add("C");
    lang.add("HTML");
    lang.add("Ruby");
    lang.addFirst("Java");
    lang.addLast("C++");
    
    System.out.println("Elements in the list: " + lang);
    
    System.out.println("First element: " + lang.getFirst());
    System.out.println("Last element: " + lang.getLast());
    
    System.out.println("Remove first element: " + lang.removeFirst());
    System.out.println("Remove last element: " + lang.removeLast());
    
    System.out.println("List elements after removing first and last elements: " + lang);
  
    System.out.println("Head element: " + lang.peek());
    System.out.println("Retrieves the first element: " + lang.peekFirst());
    System.out.println("Retrieves the last element: " + lang.peekLast());
    System.out.println( "Remove and returns the first element: " + lang.poll());
    System.out.println("Remove and returns the first element: " + lang.pollFirst());
    System.out.println("Remove and returns the last element: " + lang.pollLast());
    
    System.out.println("List elements after poll method: " + lang);
    
    lang.offer("C#");
    lang.offerFirst("Java");
    lang.offerLast("C++");
    System.out.println("List elements: " + lang);
    
    
  }

}

Elements in the list: [Java, Python, C, HTML, Ruby, C++]
First element: Java
Last element: C++
Remove first element: Java
Remove last element: C++
List elements after removing first and last elements: [Python, C, HTML, Ruby]
Head element: Python
Retrieves the first element: Python
Retrieves the last element: Ruby
Remove and returns the first element: Python
Remove and returns the first element: C
Remove and returns the last element: Ruby
List elements after poll method: [HTML]
List elements: [Java, HTML, C#, C++]

Reference