# 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:

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

we can access elements by index:

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

It is also possible to remove elements by index:

```java
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:

```java
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.

```java
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:

```java
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.

```mermaid
graph LR
    subgraph MyLinkedList [Linked List]
        A[10] --> B[20]
        B --> C[30]
    end
```

After removing 20:

```mermaid
graph LR
    subgraph MyLinkedList [Linked List after removing Node B]
        A[10] --> C[30]
        B[20]  
    end
```

## 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:

```java
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.**

```java
    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.