Java LinkedList (Linked List)

In this tutorial, we will learn about the LinkedList class in detail through many examples.

The LinkedList class in the Java collection framework provides the functionality of the linked list data structure.

interfaces implemented by LinkedList

• Java List Interface

• Java Queue interface

• Java Deque Interface

LinkedList implementation in Java

The Java LinkedList class provides an implementation of a doubly linked list.

Each element in the linked list is callednodes. It contains3fields:

• Prev - stores the address of the previous element in the list. The first element is null.

• Next - stores the address of the next element in the list. The last element is null.

• Data - stores actual data.

The elements in the linked list are not stored in order. Instead, they are scattered and connected by links (Prev and Next).

Here, the linked list contains3element.

• Dog - The first element will use null as the previous address and the address of Cat as the next address

• Cat - The second element will use the address of Dog as the previous address and the address of Cow as the next address

• Cow - The last element will use the address of Cat as the previous address and null as the next element

Create a LinkedList

This is how we create a LinkedList in Java:

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

Here, Type represents the type of the linked list. For example,

//Create a linked list of integer type
LinkedList<Integer> linkedList = new LinkedList<>();
//Create a linked list of string type
LinkedList<String> linkedList = new LinkedList<>();

Creating LinkedList using interfaces

Let's take an example.

List<String> animals1　= new LinkedList<>();

Here, we declare a linked list animals using the List interface1, the linked list can only access methods of the List interface.

Let's take another example.

Queue<String> animals2　= new LinkedList<>();
Deque<String> animals3　= new LinkedList<>();

Here, animal2can access methods of the Queue interface.

However, animal3can only access methods of the Deque and Queue interfaces. This is because Deque is a subinterface of Queue.

Methods of LinkedList

LinkedList provides various methods that allow us to perform different operations on the linked list.

To add an element (node) to the end of the linked list, we use the add() method. For example,

1.Add elements:.Add elements:

using add() method

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args){
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//To add an element (node) to the end of the linked list, we use the add() method. For example,
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Horse");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Cat, Horse]

2.Add elements: using index number

We can also use an index to add elements to the linked list. For example,

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args){
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//.Add elements: using index number
　　　　　　　　Add elements using index
　　　　　　　　animals.add(1animals.add(0,"Dog");
　　　　　　　　animals.add(2,"Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Cat, Horse]

3,"Horse");

.Add elements: adding one linked list to another

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args){
　　　　　　　　To add all elements of a linked list to another linked list, we use the addAll() method. For example,
　　　　　　　　LinkedList<String> mammals = new LinkedList<>();
　　　　　　　　mammals.add("Dog");
　　　　　　　　mammals.add("Cat");
　　　　　　　　mammals.add("Horse");　+　System.out.println("Mammals: ")
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　mammals);
　　　　　　　　//animals.add("Crocodile");
　　　　　　　　Add all elements of mammals to animals
　　　　　　　　animals.addAll(mammals);　+　animals);
　　　　}
}

Output Result

System.out.println("Animals: ")
Mammals: [Dog, Cat, Horse]

4Animals: [Crocodile, Dog, Cat, Horse]

.Add elements: using the listIterator() method

import java.util.ArrayList;
import java.util.ListIterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　ArrayList<String> animals = new ArrayList<>();
　　　　　　　　//Create a ListIterator object
　　　　　　　　ListIterator<String> listIterate = animals.listIterator();
　　　　　　　　We can also use the listsIterator() method to add elements to the linked list. To use it, we must import the java.util.ListIterator package. For example,
　　　　　　　　listIterate.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　}
}

Output Result

listIterate.add("Cat");

LinkedList: [Dog, Cat]

1Access LinkedList elements

.Access elements: using the get() method

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//To retrieve elements from the linked list, we can use the get() method. For example,
　　　　　　　　String str = animals.get(1);
　　　　　　　　System.out.print("index1element: "　+　str);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
index1element: Horse

2.Access elements: using the iterator() method

To traverse the elements of a linked list, we can use the iterator() method. We must import the java.util.Iterator package to use this method. For example,

import java.util.LinkedList;
import java.util.Iterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　//Create an Iterator object
　　　　　　　　Iterator<String> iterate = animals.iterator();
　　　　　　　　System.out.print("LinkedList: ");
　　　　　　　　while(iterate.hasNext()) {
　　　　　　　　　　　　System.out.print(iterate.next());
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: Dog, Cat, Horse,

Here,

• hasNext() - Returns true if there is a next element

• next() - Returns the next element

3. Access element: using listIterator() method

We can also use the listIterator() method to iterate over the elements of the linked list. To use this method, we must import the java.util.ListIterator package.

The listsIterator() method is more suitable for use with lists. This is because the listIterator() object can also iterate backward. For example

import java.util.LinkedList;
import java.util.ListIterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　//Create a ListIterator object
　　　　　　　　ListIterator<String> listIterate = animals.listIterator();
　　　　　　　　System.out.print("LinkedList: ");
　　　　　　　　while(listIterate.hasNext()) {
　　　　　　　　　　　　System.out.print(listIterate.next());
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　　　　　//　Traverse backward
　　　　　　　　System.out.print("\nReverse LinkedList: ");
　　　　　　　　while(listIterate.hasPrevious()) {
　　　　　　　　　　　　System.out.print(listIterate.previous());
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: Dog, Horse, Cat,
Reverse LinkedList: Cat, Horse, Dog,

Here,

• hasNext() - Returns true if there is a next element

• next() - Returns the next element

• hasPrevious() - Returns true if there is a previous element

• previous() - Returns the previous element

Find LinkedList element

1. Find element: using contains() method

To check if a list contains a specific element, we use the contains() method. For example,

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Check if Dog is in the list
　　　　　　　　if(animals.contains("Dog")) {
　　　　　　　　　　　　System.out.println("Dog is in the LinkedList.");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
Dog is in the LinkedList.

2. Search for element: using indexOf() method

• indexOf() - Returns the index of the first occurrence of the element

• lastIndexOf() - Returns the index of the last occurrence of the element

For example,

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//　Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//The first occurrence of Dog
　　　　　　　　int index1　= animals.indexOf("Dog");
　　　　　　　　System.out.println("The first occurrence index value of Dog: "}　+　index1);
　　　　　　　　//The last occurrence of Dog
　　　　　　　　int index2　= animals.lastIndexOf("Dog");
　　　　　　　　System.out.println("The last index value of Dog: ",　+　index2);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat, Dog]
The first index value of Dog: 0
The last index value of Dog:　3

Note:If the specified element is not found, indexOf() and lastIndexOf() both return-1.

Change LinkedList elements

1Change elements: using the set() method

To change elements in a linked list, we can use the set() method. For example,

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Change index value3of the elements
　　　　　　　　animals.set(3, "Zebra");
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat, Dog]
New LinkedList: [Dog, Horse, Cat, Zebra]

2Change elements: using the listIterator() method

We can also use the listIterator() method to change elements in a linked list. For example,

import java.util.ArrayList;
import java.util.ListIterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　ArrayList<String> animals = new ArrayList<>();
　　　　　　　　//　Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Horse");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Create a ListIterator object
　　　　　　　　ListIterator<String> listIterate = animals.listIterator();
　　　　　　　　listIterate.next();
　　　　　　　　//Change the element returned by next()
　　　　　　　　listIterate.set("Cow");
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Cat, Horse]
New LinkedList: [Cow, Cat, Horse]

Remove LinkedList elements

1Remove elements: using the remove() method

To remove elements from a linked list, we can use the remove() method. For example,

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Zebra");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Remove index value1of the elements
　　　　　　　　String str = animals.remove(1);
　　　　　　　　System.out.println("Remove element: ",　+　str);
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat, Zebra]
Remove element: Horse
New LinkedList: [Dog, Cat, Zebra]

2Remove elements: using the listIterator() method

We can also use the listsIterator() method to remove elements from a linked list. For example,

import java.util.ArrayList;
import java.util.ListIterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　ArrayList<String> animals = new ArrayList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Horse");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Create a ListIterator object
　　　　　　　　ListIterator<String> listIterate = animals.listIterator();
　　　　　　　　listIterate.next();
　　　　　　　　//Delete the element returned by next()
　　　　　　　　listIterate.remove();
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Cat, Horse]
New LinkedList: [Cat, Horse]

3. Delete element: using clear() method

To delete all elements from the linked list, we use the clear() method. For example:

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Horse");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Delete all elements
　　　　　　　　animals.clear();
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Cat, Horse]
New LinkedList: []

Note:We can also use the removeAll() method to delete all elements. However, the clear() method is more efficient than the removeAll() method.

4. Delete element: using removeIf() method

If an element meets a specific condition, we can also delete it from the linked list. To do this, we use the removeIf() method. For example:

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　LinkedList<Integer> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add(2);
　　　　　　　　animals.add(3);
　　　　　　　　animals.add(4);
　　　　　　　　animals.add(5);
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//　Delete all elements less than4of the elements
　　　　　　　　animals.removeIf((Integer i)->i <　4);
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　　　　/**　Here we use lambda expressions
　　　　　　　*　　Now please remember
　　　　　　　*　　The parameter in removeIf() is a condition
　　　　　　　*/
　　　　}
}

Output Result

LinkedList: [2,　3,　4,　5]
New LinkedList: [4,　5]

Note: (Integer i)->i<4 It is a lambda expression. To learn about lambda expressions, please visitJava Lambda Expression

LinkedList as Deque and Queue

Since the LinkedList class also implements the Queue and Deque interfaces, it can also implement the methods of these interfaces. Here are some commonly used methods:

addFirst() and addLast() methods

• addFirst() - Add the specified element to the beginning of the linked list

• addLast() - Add the specified element to the end of the linked list

For example,

import java.util.LinkedList;
import java.util.Deque;
class Main {
　　　　public static void main(String[] args){
　　　　　　　　Deque<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the beginning of LinkedList
　　　　　　　　animals.addFirst("Cow");
　　　　　　　　animals.addFirst("Dog");
　　　　　　　　animals.addFirst("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Add elements to the end of LinkedList
　　　　　　　　animals.addLast("Zebra");
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Cat, Dog, Cow]
New LinkedList: [Cat, Dog, Cow, Zebra]

getFirst() and getLast() methods

• getFirst() - Return the first element

• getLast() - Return the last element

For example,

import java.util.LinkedList;
import java.util.Deque;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　Deque<String> animals = new LinkedList<>();
　　　　　　　　//　Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Get the first element from the linked list
　　　　　　　　String str1　= animals.getFirst();
　　　　　　　　System.out.println("First element: ")　+　str1);
　　　　　　　　//Get the last element from the linked list
　　　　　　　　String str2　= animals.getLast();
　　　　　　　　System.out.println("Last element: ")　+　str2);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
First element: Dog
Last element: Cat

removeFirst() and removeLast() methods

• removeFirst() - Delete the first element

• removeLast() - Delete the last element

For example,

import java.util.LinkedList;
import java.util.Deque;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　Deque<String> animals = new LinkedList<>();
　　　　　　　　//　Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Delete the first element from LinkedList
　　　　　　　　String str1　= animals.removeFirst();
　　　　　　　　System.out.println("Deleted element: ")　+　str1);
　　　　　　　　//Delete the last element from LinkedList
　　　　　　　　String str2　= animals.removeLast();
　　　　　　　　System.out.println("Deleted element: ")　+　str2);
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
Deleted element: Dog
Deleted element: Cat
New LinkedList: [Horse]

peek() method

The peek() method returns the first element (head) of the linked list. For example,

import java.util.LinkedList;
import java.util.Queue;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　Queue<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Access the first element of LinkedList
　　　　　　　　String str = animals.peek();
　　　　　　　　System.out.println("Element access: ")　+　str);
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
Element access: Dog
New LinkedList: [Dog, Horse, Cat]

poll() method

The poll() method returns and deletes the first element from the linked list. For example,

import java.util.LinkedList;
import java.util.Queue;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　Queue<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　animals.add("Cat");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Return and delete the first element
　　　　　　　　String str = animals.poll();
　　　　　　　　System.out.println("Deleted element: ")　+　str);
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse, Cat]
Deleted element: Dog
New LinkedList: [Horse, Cat]

offer() method

The offer() method adds the specified element to the end of the linked list. For example,

import java.util.LinkedList;
import java.util.Queue;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　Queue<String> animals = new LinkedList<>();
　　　　　　　　//Add elements to the linked list
　　　　　　　　animals.add("Dog");
　　　　　　　　animals.add("Horse");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Add elements to the end of LinkedList
　　　　　　　　animals.offer("Cat");
　　　　　　　　System.out.println("New LinkedList: ");　+　animals);
　　　　}
}

Output Result

LinkedList: [Dog, Horse]
New LinkedList: [Dog, Horse, Cat]

Traverse LinkedList iterator

1.Use forEach loop to traverse

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　//Create a linked list
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　animals.add("Cow");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Use forEach loop
　　　　　　　　System.out.println("Access linked list elements:");
　　　　　　　　for(String animal: animals) {
　　　　　　　　　　　　System.out.print(animal);
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: [Cow, Cat, Dog]
Access linked list elements:
Cow, Cat, Dog,

2.Use for loop

import java.util.LinkedList;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　//Create a linked list
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　animals.add("Cow");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Use for loop
　　　　　　　　System.out.println("Access linked list elements:");
　　　　　　　　for(int i = 0; i < animals.size(); i++) {
　　　　　　　　　　　　System.out.print(animals.get(i));
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: [Cow, Cat, Dog]
Access linked list elements:
Cow, Cat, Dog,

In both examples, we use loops to access each element of the linked list.

3.Use iterator() method

We can use the iterator() method to access the elements of the linked list. To use this method, we must import the java.util.Iterator package.

import java.util.LinkedList;
import java.util.Iterator;
class Main {
　　　　public static void main(String[] args) {
　　　　　　　　//Create a linked list
　　　　　　　　LinkedList<String> animals = new LinkedList<>();
　　　　　　　　animals.add("Cow");
　　　　　　　　animals.add("Cat");
　　　　　　　　animals.add("Dog");
　　　　　　　　System.out.println("LinkedList: ");　+　animals);
　　　　　　　　//Use iterator() method
　　　　　　　　System.out.println("LinkedList uses iterator() method:");
　　　　　　　　Iterator<String> iterate = animals.iterator();
　　　　　　　　while(iterate.hasNext()) {
　　　　　　　　　　　　System.out.print(iterate.next());
　　　　　　　　　　　　System.out.print(", ");
　　　　　　　　}
　　　　}
}

Output Result

LinkedList: [Cow, Cat, Dog]
LinkedList uses the iterator() method:
Cow, Cat, Dog,

LinkedList vs ArrayList

LinkedList and ArrayList both implement the List interface of the Collections framework. However, there are some differences between them.