Dev.to

What's in a List

NOTE: Originally published on my blog ----> What's in a List Introduction List is an interface in Java Collections that represents an ordered sequence of elements. Features of a List: Access elements by position (index). Store duplicate elements, because a Set does not store duplicates. Insert or remove elements at any position. This is the canonical definition of a List in Java. The most common implementation List being an interface, the most used implementation is the java.util.ArrayList class: List list = new ArrayList(); list.add("This"); list.add("is"); list.add("a"); list.add("list"); we can access elements by index: String element = list.get(1); System.out.println(element); // prints "is" It is also possible to remove elements by index: list.remove(2); for (String element : list) { System.out.println(element); // prints "This", "is", "list" } It is quite simple. It is like an array, but we do not have to worry about resizing it. The ArrayList class takes care of that. The notation is also different. We use get() instead of [] to access elements by index. List Methods Most of the methods are self-explanatory. The main ones are: add(): adds an element to the end of the list. remove(): removes an element from the list. get(): returns the element at the specified index. size(): returns the number of elements in the list. isEmpty(): returns true if the list is empty, false otherwise. contains(): returns true if the list contains the specified element, false otherwise. indexOf(): returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found. lastIndexOf(): returns the index of the last occurrence of the specified element in the list, or -1 if the element is not found. Two methods are going to be explained, because they are a bit confusing. add() add() is an overloaded method. It has two versions: list.add(element); list.add(index, element); The first version adds the element to the end of the list, while the second version adds the element at the specified index. The second one would have rather been called insertAt(). set() set(int index, E element) replaces the element at the specified index with the given element. It return the element that was previously at the specified position. The list must have an element at the specified index, otherwise it throws an exception. It changes the element in place, so it does not change the size of the list. The LinkedList class Why not use the ArrayList implementation always? The ArrayList class is a good choice for most cases, in fact most of the programmers have only used that class when creating a List. But there is one thing that the ArrayList class does not do very well: inserting and removing elements in random list positions. Why? Because every time an element is inserted or removed, the remaining elements starting from the modified position have to be shifted, since all the array elements must be stored in contiguous memory. As a consequence, an LinkedList should be faster than an ArrayList for adding or removing elements in the middle of the list. Unless you have to use a cache memory, in which case you will prefer a list whose elements are contiguous in memory. List list = new LinkedList(); list.add("This"); list.add("is"); list.add("a"); list.add("list"); Since both classes implement the List interface, we can use them interchangeably. Let's see how a simplified LinkedList looks like: class LinkedList { private Node head = null; // Start of the list private int size = 0; // Number of nodes private int index = 0; } class Node { private String data; // Element stored in this node private Node next = null; // Link to the next node private Node previous = null; // Link to the previous node } As we can see, it is a doubly linked list. A node has three attributes: the data itself, and references to the next and previous nodes. These nodes are not contiguous in memory. Therefore, when an element is inserted or removed, the remaining elements do not have to be shifted. A node has to modify only its two references, resulting in much faster operations. +-------+ +-------+ +-------+ | 10 |-->--| 20 |-->--| 30 | +-------+ +-------+ +-------+ Node A Node B Node C After removing 20: +-------+ +-------+ | 10 |-->--| 30 | +-------+ +-------+ Node A Node C ArrayList vs LinkedList The ArrayList class is faster for adding and removing elements in the middle of the list, while the LinkedList class is faster for adding and removing elements at the beginning or end of the list. Let's see an example for measuring the time it takes to add and remove elements in the middle of the list: import java.util.List; import java.util.ArrayList; import java

Apr 17, 2025 - 16:07

NOTE: Originally published on my blog ----> What's in a List

Introduction

List is an interface in Java Collections that represents an ordered sequence of elements.

Features of a List:

Access elements by position (index).
Store duplicate elements, because a Set does not store duplicates.
Insert or remove elements at any position.

This is the canonical definition of a List in Java.

The most common implementation

List being an interface, the most used implementation is the java.util.ArrayList class:

List<String> list = new ArrayList<>();
list.add("This");
list.add("is");
list.add("a");
list.add("list");

we can access elements by index:

String element = list.get(1);
System.out.println(element); // prints "is"

It is also possible to remove elements by index:

list.remove(2);
for (String element : list) {
    System.out.println(element);  // prints "This", "is", "list"
}

It is quite simple. It is like an array, but we do not have to worry about resizing it. The ArrayList class takes care of that.
The notation is also different. We use get() instead of [] to access elements by index.

List Methods

Most of the methods are self-explanatory. The main ones are:

add(): adds an element to the end of the list.
remove(): removes an element from the list.
get(): returns the element at the specified index.
size(): returns the number of elements in the list.
isEmpty(): returns true if the list is empty, false otherwise.
contains(): returns true if the list contains the specified element, false otherwise.
indexOf(): returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found.
lastIndexOf(): returns the index of the last occurrence of the specified element in the list, or -1 if the element is not found.

Two methods are going to be explained, because they are a bit confusing.

add()

add() is an overloaded method. It has two versions:

list.add(element);
list.add(index, element);

The first version adds the element to the end of the list, while the second version adds the element at the specified index. The second one would have rather been called insertAt().

set()

set(int index, E element) replaces the element at the specified index with the given element. It return the element that was previously at the specified position.

The list must have an element at the specified index, otherwise it throws an exception.
It changes the element in place, so it does not change the size of the list.

The LinkedList class

Why not use the ArrayList implementation always?

The ArrayList class is a good choice for most cases, in fact most of the programmers have only used that class when creating a List.

But there is one thing that the ArrayList class does not do very well: inserting and removing elements in random list positions. Why? Because every time an element is inserted or removed, the remaining elements starting from the modified position have to be shifted, since all the array elements must be stored in contiguous memory.

As a consequence, an LinkedList should be faster than an ArrayList for adding or removing elements in the middle of the list.
Unless you have to use a cache memory, in which case you will prefer a list whose elements are contiguous in memory.

List<String> list = new LinkedList<>();
list.add("This");
list.add("is");
list.add("a");
list.add("list");

Since both classes implement the List interface, we can use them interchangeably.

Let's see how a simplified LinkedList looks like:

class LinkedList {
    private Node head = null;  // Start of the list
    private int size = 0;      // Number of nodes
    private int index = 0;
}

class Node {
    private String data;        // Element stored in this node
    private Node next = null;     // Link to the next node
    private Node previous = null; // Link to the previous node
}

As we can see, it is a doubly linked list. A node has three attributes: the data itself, and references to the next and previous nodes.

These nodes are not contiguous in memory. Therefore, when an element is inserted or removed, the remaining elements do not have to be shifted. A node has to modify only its two references, resulting in much faster operations.

+-------+ +-------+ +-------+
| 10 |-->--| 20 |-->--| 30 |
+-------+ +-------+ +-------+
Node A Node B Node C

After removing 20:

+-------+ +-------+
| 10 |-->--| 30 |
+-------+ +-------+
Node A Node C

ArrayList vs LinkedList

The ArrayList class is faster for adding and removing elements in the middle of the list, while the LinkedList class is faster for adding and removing elements at the beginning or end of the list.

Let's see an example for measuring the time it takes to add and remove elements in the middle of the list:

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class ListInsertionBenchmark {
    public static void main(String[] args) {
        final int ELEMENT_COUNT = 10_000; // Number of insertions to test

        // Test ArrayList
        List<Integer> arrayList = new ArrayList<>();
        long arrayListTime = timeInsertInMiddle(arrayList, ELEMENT_COUNT);

        // Test LinkedList
        List<Integer> linkedList = new LinkedList<>();
        long linkedListTime = timeInsertInMiddle(linkedList, ELEMENT_COUNT);

        System.out.println("\nResults:");
        System.out.printf("ArrayList insertion time: %d ms\n", arrayListTime);
        System.out.printf("LinkedList insertion time: %d ms\n", linkedListTime);
    }

    private static long timeInsertInMiddle(List<Integer> list, int insertions) {
        // Pre-fill the list to avoid starting empty
        for (int i = 0; i < 1_000_000; i++) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < insertions; i++) {
            int middleIndex = list.size() / 2;
            list.add(middleIndex, i); // Insert at middle
        }
        long endTime = System.currentTimeMillis();

        return endTime - startTime;
    }
}

If we run this program, it turns out that the LinkedList insertion time is much greater than the ArrayList one, although all the insertions are done in the middle of the list.

It seems that the time it takes to traverse the list from head/tail to reach a middle index is higher for the LinkedList.
This happens because the ArrayList data structure is optimized for shifting contiguous elements by using System.arraycopy(); whereas traversing all the nodes is slow because nodes are scattered in memory. Each pointer access can result in a memory cache miss, which makes the process even slower.
In other words, insertion in a LinkedList without an iterator is a O(n) operation.

System.arraycopy() copies memory blocks from one part of an array to another. It's a native method, that is, its core logic is implemented in a lower-level language like C (or C++) for performance reasons.
If a traditional loop were used to copy every single list element, the traversing time would be much higher.

ArrayList is faster due to contiguous memory and optimized block copying, not because it's a faster algorithm in terms of complexity.

The benchmark highlights that algorithmic complexity alone does not determine real-world performance. ArrayList’s optimized memory operations make it a strong contender even for middle insertions.
We should profile our specific use case to make the most informed decision.

The missing piece: ListIterator

We said

The LinkedList class is faster for adding and removing elements at the middle of the list.

but the results obtained in the benchmark did not match that statement.

We can use a ListIterator and move it to a position once and then do many insertions/removals at that spot. In this way, we don't need to traverse the list each time.

    public static void main(String[] args) {
        final int ELEMENT_COUNT_WITH_ITERATOR = 3000;

        long arrayListIteratorTime = timeInsertUsingAnIterator(arrayList, ELEMENT_COUNT_WITH_ITERATOR);

        long linkedListIteratorTime = timeInsertUsingAnIterator(linkedList, ELEMENT_COUNT_WITH_ITERATOR);
        // ArrayList vs LinkedList
        System.out.println("\nResults:");
        System.out.printf("ArrayList insertion time: %d ms\n", arrayListTime);
        System.out.printf("LinkedList insertion time: %d ms\n", linkedListTime);

        System.out.printf("ArrayList iterator insertion time: %d ms\n", arrayListIteratorTime);
        System.out.printf("LinkedList iterator insertion time: %d ms\n", linkedListIteratorTime);
    }

    private static long timeInsertUsingAnIterator(List<Integer> list, int insertions) {
        // Pre-fill the list to avoid starting empty
        for (int i = 0; i < 10_000; i++) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        ListIterator<Integer> iterator = list.listIterator(5000);
        for (int i = 0; i < insertions; i++) {
            iterator.add(i);
        }
        long endTime = System.currentTimeMillis();

        return endTime - startTime;
    }
}

The insertions time for the LinkedList is very close to zero, and it's much faster than the ones for the ArrayList.

Multiple insertion and removals are faster when using a LinkedList, provided an iterator at the correct position is used.
In these cases, insertion in a LinkedList is a O(1) operation.

A LinkedList is suitable for use cases where we need to add and remove elements at a known same position and we don't need to access elements by index often. Examples are undo/redo stacks and managing history.

LinkedList implements both the Queue and Deque interfaces, which means that it is a good choice for use cases where we need to add and remove elements from both ends of the list.

Conclusion

The Java List is an interface with methods for adding, removing, and accessing elements. It has two different implementations: ArrayList and LinkedList.

ArrayList offers excellent general-purpose performance, especially for random access and adding/removing at the end.
LinkedList provides faster insertion and deletion if an iterator at the correct position is used.
As always, the optimal choice depends on your application's specific needs and access patterns.