The List type is probably one of the most widely used structures in the Java programming language. Simply put, data structures implementing this interface store a vector of values that we can query and iterate over as required.

Two important implementations which on the surface have differences which are difficult to decipher are the ArrayList and LinkedList found in the ​java.util` package. Understanding the differences between the two is important for designing and writing more efficient code.

Several years ago I worked on a project where a senior developer inadvertently used a LinkedList over an ArrayList for a vector of data that was being accessed by index. Let’s take a look and see why this was a problem.

The basics of the ArrayList

The underlying structure of an ArrayList is an array. When you create a new ArrayList it creates and new array with ten elements.

    // creates a new ArrayList with an underlying 
    // array containing 10 cells
    
    List users = new ArrayList();

As you start adding new users into the ArrayList the underlying array populates. However what happens when the ArrayList reaches 10 records? The ArrayList recognises this and copies the values into a new array that is as large as the old capacity x 1.5. This is the formula:

    (oldCapacity * 3)/2 + 1

In the case of the initial 10 cells it will grow to 16 cells. This keeps happening as new values are added into the list. This is incredibly efficient and fast.

The basics of the LinkedList

The underlying structure of a LinkedList is a vector of nodes each of which links to the next - like a chain where each link hooks to the next/previous. When you create a new LinkedList it simply creates a container to place each value into. As a new value is added into the list, a new node object is created which is referenced bt the previous object.

    // creates a new LinkedList ready for new objects to be added
    
    List users = new LinkedList();

Internally, each value is stored as a private static Entry object. (Note: Static inner classes prevent the enclosing class from accessing the internals of the static class.). Notice that there is a property for the next and previous Entry objects? This is how our list of objects links together. Remember, think of a chain of double ended hooks. The element property holds the value of the Entry.

    private static class Entry {
        E element;
        Entry next;
        Entry previous;
    
        Entry(E element, Entry next, Entry previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
    }

The structure of the LinkedList can be visualised once we see this inner Entry class and the following diagram.

Image: Wikipedia

Memory Footprint

ArrayList

To store its values an ArrayList uses an array as the underlying data structure. Contiguous in form, this is incredible fast and efficient for access by index and for appending at the end of the list. In terms of memory, each reference contains between 4-6 bytes per reference. In terms of the JDK, this is probably as good as it gets. Moreover, it is better not to allocate a large ArrayList in advance if you do not know what its size will be in advance.

Linked List

A LinkedList on the other hand consists of multiple objects linked together in a chain. Each new value requires the creation of a new Entry object where each Entry has three references at 4 bytes each (previous, next, element) plus 12 more bytes for the header for a total of 24 bytes per Entry. Around 4 x more than the ArrayList. In contrast to the ArrayList, the underlying Entry objects of the structure are not contiguous (i.e. low spacial-locality) this leading

What should I use?

Given that LinkedList also implements Deque, it would be useful for iteration operations on queue/dequeue/stack structures. Moreover, if you need to insert or delete at the middle of your list then use a LinkedList however even then the ArrayList is efficient as the underlying operation is a native function. Otherwise always use an ArrayList.

One last thing, keep in mind, that the list interface only accepts objects. If your values are primitives then you will either need to roll your own or use a library such as Trove. The Trove library provides high speed regular and primitive collections for Java. F.A.S.T. ! ! !

…and finally…

…from the author of the original LinkedList Java implementation:

> > [@jerrykuch](https://twitter.com/jerrykuch?ref_src=twsrc%5Etfw) [@shipilev](https://twitter.com/shipilev?ref_src=twsrc%5Etfw) [@AmbientLion](https://twitter.com/AmbientLion?ref_src=twsrc%5Etfw) Does anyone actually use LinkedList? I wrote it, and I never use it. > > — Joshua Bloch (@joshbloch) [April 3, 2015](https://twitter.com/joshbloch/status/583813919019573248?ref_src=twsrc%5Etfw)

hmmm…..