Java LinkedList

The List interface

A list is an ordered collection of elements: each element has a position in the list specified by an integer index just like in regular arrays. However, unlike the size of arrays, the size of lists can be changed dynamically. Moreover, lists provide more advanced behavior than arrays. In this topic, you will deepen your knowledge of lists and their relationship with the Collections Framework.

You cannot create an instance of the List interface, but you can create an instance of one of its implementations: ArrayList or LinkedList or an immutable list, and then use it through the common List interface. You will have access to all methods declared in both the List<E> and Collection<E> interfaces.

Immutable lists

The simplest way to create a list is to invoke the of method of the List interface.

List<String> emptyList = List.of(); // 0 elements
List<String> names = List.of("Larry", "Kenny", "Sabrina"); // 3 elements
List<Integer> numbers = List.of(0, 1, 1, 2, 3, 5, 8, 13);  // 8 elements

It returns an immutable list containing either all the passed elements or an empty list. Using this method is convenient when creating a list of constants or testing some code.

Let's perform some operations:

List<String> daysOfWeek = List.of(
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday",
        "Sunday"
);

System.out.println(daysOfWeek.size()); // 7
System.out.println(daysOfWeek.get(1)); // Tuesday
System.out.println(daysOfWeek.indexOf("Sunday")); // 6

List<String> weekDays = daysOfWeek.subList(0, 5);
System.out.println(weekDays); // [Monday, Tuesday, Wednesday, Thursday, Friday]

Since it is immutable, only methods that do not change the elements in the list will work and others will throw an exception.

daysOfWeek.set(0, "Funday"); // throws UnsupportedOperationException
daysOfWeek.add("Holiday");   // throws UnsupportedOperationException

This situation demonstrates when immutable lists are needed. It's hard to imagine that someone renames a day or adds another one!

Be careful when working with immutable lists: sometimes even experienced developers get an UnsupportedOperationException.

Another way to create unmodifiable lists was introduced before Java 9 and is the following:

List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5); // fixed-size list
numbers = Collections.unmodifiableList(numbers); // unmodifiable list

To use it, the classes java.util.Arrays and java.util.Collections must be imported.

Mutable lists

When you need to use a mutable list, you can take one of two commonly used mutable implementations of the List interface.

One of them is familiar to you: the ArrayList<E> class. It represents a resizable array. In addition to implementing the List interface, it provides methods to manipulate the size of the array that is used internally. These methods are not needed in programs often, so it is better to use an object of this class through the List interface.

List<Integer> numbers = new ArrayList<>();

numbers.add(15);
numbers.add(10);
numbers.add(20);

System.out.println(numbers); // [15, 10, 20]

numbers.set(0, 30); // no exceptions here

System.out.println(numbers); // [30, 10, 20]

If you have an immutable list, you can take the mutable version from it using the following code:

List<String> immutableList = List.of("one", "two", "three");
List<String> mutableList = new ArrayList<>(immutableList); 

Another mutable implementation of the List interface is the LinkedList class. It represents a doubly-linked list based on connected nodes. All operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

List<Integer> numbers = new LinkedList<>();
        
numbers.add(10);
numbers.add(20);
numbers.add(30);

System.out.println(numbers); // [10, 20, 30]

Access to the first and the last element of the list is always carried out in constant time O(1) because links to the first and the last element are stored. So, adding an item to the end of the list does not mean that you have to iterate the whole list searching for the last element. However, accessing/setting an element by its index takes O(n) time for a linked list.

In the general case, LinkedList loses to ArrayList in memory consumption and speed of operations. Still, you can choose either depending on the problem you are trying to solve.

Iterating over a list

You can use the for loop and the for-each loop to iterate over a list.

List<String> names = List.of("Larry", "Kenny", "Sabrina");

1) Using the for-each loop:

// print every name
for (String name : names) {
    System.out.println(name);
}

2) Using indexes and the size() method:

// print every second name
for (int i = 0; i < names.size(); i += 2) {
    System.out.println(names.get(i));
}

When you need to go through all elements of a list, we recommend choosing the first way to iterate. The second way is good when you need to skip some elements based on their positions in the list.

List equality

The final question is how lists are compared. Two lists are equal when they contain the same elements in the same order. The equality does not depend on the types of the lists themselves (ArrayList, LinkedList or something else).

Objects.equals(List.of(1, 2, 3), List.of(1, 2, 3));    // true
Objects.equals(List.of(1, 2, 3), List.of(1, 3, 2));    // false
Objects.equals(List.of(1, 2, 3), List.of(1, 2, 3, 1)); // false

List<Integer> numbers = new ArrayList<>();
        
numbers.add(1);
numbers.add(2);
numbers.add(3);

Objects.equals(numbers, List.of(1, 2, 3)); // true

Working with lists through the List interface is considered good practice in programming since your code will not depend on the internal mechanisms of a specific implementation.

But the list class ArrayList is quite similar to LinkedList. They both implement the List interface and provide useful features for storing and accessing elements. So which one should you use? Sadly, there is no definite answer as different problems require different approaches. To make the right choice you need to understand who is the winner in which situation. So let's compare ArrayList and LinkedList in detail.

What is inside?

Let's start with a quick and illustrative overview of how our lists look inside.
On the inside, an ArrayList is a resizable array of objects, where every element has an index.

A LinkedList is a doubly-linked list based on connected nodes. LinkedList stores its head and tail.

A node is a class that has three fields: the element itself, the previous, and the next node.

Now, with these pictures in mind, it's time to think how fast standard operations will work for both of them and why.

First round: ArrayList

The logic of an ArrayList is simple. Because internally it's an array, the operations get(int index) and set(int index, E element) will be fast. In other words, the time complexity for access by an index is O(1).

If you use the add(E e) operation, a new element will be added to the end of ArrayList. This would also be fast and take constant time to make, so the complexity would be the same: O(1).

But if you would like to insert an element into the ArrayList by using the add(int index, E element) operation the situation will be different. To put the new element into a specific index the ArrayList needs to move all subsequent elements.

In our example, after the insertion, an element Array will have an index of 4 and an element List! will have an index of 5. If there are a lot of subsequent elements this operation will be quite long with the time complexity O(n).

Let's take a look at what is really happening inside of Java.

When you want to add a new element to the full ArrayList, a new array with a bigger size will be created first. Then all existing elements will be copied to that new array. And only then your new element will be added. So, the worst time complexity would be O(n).

An ArrayList is a resizable array, so when you fill up its initial size, it becomes bigger and that will happen again and again.

The last operation is remove(int index). When you would like to remove an element all subsequent elements will have to be moved.

Because of moving all subsequent elements, this operation won't be very efficient for a long list, with the time complexity O(n).

Now you know what is happening inside an ArrayList and it's time to pay some attention to its rival LinkedList.

Final round: LinkedList

A LinkedList is not an array, so it doesn't support fast access by index. But it can reach any element by its index. In order to do this LinkedList decides what will be closer to that index: head or tail. And then going from either head or tail, the LinkedList traverses all the elements before it reaches the required one.

firstElement.next.next.next.next.next.next...

Let's start with get(int index) and set(int index, E element) operations.

To get the element am with index 1, LinkedList will start from the head. In our example, LinkedList will need to go only through one link: between element I and element am. But if you have a long LinkedList and the required index is in the middle, these operations get(int index) and set(int index, E element) will take a lot of time. So, in a bad situation, the time complexity would be O(n).

Adding an element to the end of the LinkedList is a fast operation. LinkedList will connect the new element Hello! with the last element List! and will make Hello! the new tail.

So it always takes constant time and the complexity of add(E e) is O(1).

Besides the method add(E e) there are two other methods: addFirst(E e) and addLast(E e). As you can understand from their names, they add the element in the head and in the tail of the LinkedList respectively. Their internal mechanism is absolutely the same as with the method add(E e). And their complexity is also O(1). The method addLast(E e) is the equivalent to the method add(E e). The difference is that the method add(E e) returns boolean and the method addLast(E e) returns void.

And what about inserting an element at a specific index with the operation add(int index, E element)?

To add an element LinkedList needs to reach the required position and then only change the connecting links of the new element neighbors.

And that's it: connect the new element with the previous and the next element, and the insertion is done. No need to move elements as in the ArrayList.

If you add new elements near the head or tail the time complexity of it would be O(1). In most situations, it's a fast operation. But if your list is a very long one, then reaching the element in the middle wouldn't be so fast. So, in a bad situation, the time complexity would be O(n).

The last one is remove(int index) operation. The mechanism is the same as LinkedList needs to reach the element and change the links.

By changing the neighbors' links the unwanted element would be deleted. And again, for most situations, it's a fast operation. But for removing the element from the middle of a very long LinkedList the time complexity would be O(n).

LinkedList has two other useful methods: removeFirst() and removeLast(). For them, LinkedList doesn't need to traverse the elements. It just removes the first or last element and changes the head or tail respectively. The time complexity for both operations is O(1).

And the winner is...

Let's illustrate the main points with a table:

As a LinkedList implements both List and Queue interfaces, sometimes it isn't fully obvious what to choose  between ArrayList and LinkedList or LinkedList and ArrayDeque. In modern versions of Java, the array-based collections are stated to be more performant and should be used in most standard cases. LinkedList can be chosen when you have a colossal number of elements and requires a lot of addition/deletion operations, especially to the beginning and the end of the list. However, there is still no guarantee that a LinkedList will perform better than the others.

So, there is no absolute winner in our competition. Yes, ArrayList is more popular, but in fact, everything depends on the task you are working on. For all operations, it's impossible to say in advance whether they are fast or take a long time. It depends on what is the size of your list and which part of the list you are working on. The most important thing for you to understand is how these operations work. Sometimes it may be difficult to make the right choice, but with this understanding, you will definitely avoid silly mistakes.