Core Java

Java ArrayList vs LinkedList Example

1. Introduction

One of the most commonly used data structures in programming is the Array. Java comes with two implementations of the Array data structure, the ArrayList and LinkedList classes. In a nutshell, the ArrayList is a resizable-array implementation, whereas the LinkedList is a doubly-linked list implementation. In this post, we will cover the differences between the methods and time complexity of those data structures, provide custom implementations and measure their performance.

The technologies that we will use in the code examples of this post are:

  • Java 8
  • Eclipse 4.10.0

2. Class Hierarchy

The ArrayList and LinkedList classes are part of the Java Collection Framework and reside in the java.util package. The diagram below shows the hierarchy in the Collection framework:

Java ArrayList vs LinkedList - Class Hierarchy
Java ArrayList & LinkedList Class Hierarchy

The Collection interface is the root interface from which the List and Queue interfaces are extended. The ArrayList and LinkedList both implement the List interface and the LinkedList also implements the Queue interface.

3. ArrayList

The ArrayList class is an auto-resizable array implementation of the List interface which accepts duplicate and null values. It uses a fixed-size array buffer under the hood to store the elements. By default when a new ArrayList object is created the size of the array buffer is 10. The array buffer is resized when it hits its capacity while adding new elements.

Java ArrayList vs LinkedList - Java ArrayList
Java ArrayList

The ArrayList provided by Java has several methods but we will focus on the most common used ones which are:

  • Add element
  • Remove element
  • Get element by index
  • Contains element

Custom Implementation

Below we create our own custom implementation of the ArrayList that stores a list of integers and implements the methods we discussed above.

MyArrayList

public class MyArrayList {

    // initial size of array buffer
    private static final int INITIAL_SIZE = 10;

    // the array buffer
    private Integer[] array;
    
    // actual size of array buffer
    private int actualSize = 0;

    public MyArrayList() {
        array = new Integer[INITIAL_SIZE];
    }

    // Add element
    public void add(int element) {
        // resize array
        if (actualSize == array.length - 1) {
            Integer[] newArray = new Integer[array.length * 2];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            array = newArray;
        }
        array[actualSize++] = element;
    }

    // Remove element
    public boolean remove(int element) {
        // reorder array
        for (int i = 0; i < actualSize; i++) {
            if (array[i] == element) {
                for (int j = i; j < actualSize; j++) {
                    array[j] = array[j + 1];
                }
                actualSize--;
                return true;
            }
        }
        return false;
    }

    // Get by index
    public int get(int index) {
        if (index > 0 && index < actualSize) {
            return array[index];
        }
        throw new ArrayIndexOutOfBoundsException();
    }

    // Contains element
    public boolean contains(int element) {
        for (int i = 0; i < actualSize; i++) {
            if (array[i] == element) {
                return true;
            }
        }
        return false;
    }
    
    public int size() {
        return actualSize;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < actualSize; i++) {
            builder.append(array[i]);
            builder.append(" ");
        }
        return builder.toString();
    }

    // Example
    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);

        System.out.println("Initial ArrayList: " + list + "| size: " + list.size());
        System.out.println("Get index 2: " + list.get(2));
        System.out.println("Contains element 3: " + list.contains(2));
        System.out.println("-------------");
        System.out.println("Removing element 2: " + list.remove(2));
        System.out.println("ArrayList after removal: " + list + "| size: " + list.size());
        System.out.println("Get index 2: " + list.get(2));
        System.out.println("Contains element 3: " + list.contains(2));
    }
}

In the class above, we create the MyArrayList class which has implementation for the methods add(int element), remove(int element), get(int index) and contains(int element). All those methods use the array to add, remove or get the elements. Let's run the main method which invokes all those methods and see the output.

Output

Initial ArrayList: 1 2 3 4 5 6 | size: 6
Get index 2: 3
Contains element 3: true
-------------
Removing element 2: true
ArrayList after removal: 1 3 4 5 6 | size: 5
Get index 2: 4
Contains element 3: false

In the above output, we initially print the ArrayList and its size, then we call the get(int index) method which returns an element and finally the contains(int element) method. Then we remove one element from the list and call the same methods again which result in different output.

4. LinkedList

The LinkedList class is a doubly-linked list implementation of the List and Queue interfaces. A linked list is a linear data structure, in which each element (also called node) has a reference to the next element. A double-linked list, on the other hand, has also a reference to the previous element. The LinkedList has a reference to the head and tail nodes.

Java ArrayList vs LinkedList - Java LinkedList
Java LinkedList

Custom Implementation

Below we create our own custom implementation of a singly linked list that stores a sequence of integers and implements the same methods we did for the ArrayList.

MyLinkedList

public class MyLinkedList {

    // Node with data and reference to the next node
    class Node {

        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    // head Node
    private Node head;
    
    // size of LinkedList
    private int size;

    // Add new element
    public void add(int element) {
        Node newNode = new Node(element);

        if (head == null) {
            head = newNode;
        } else {
            // traverse list to find last node
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // Remove element
    public boolean remove(int element) {
        if (head == null) {
            return false;
        }
        Node current = head;

        if (current == null) {
            return false;
        }

        // found in head
        if (current.data == element) {
            head = current.next;
            size--;
            return true;
        }

        // traverse list to find element
        while (current != null) {
            if (current.next != null && current.next.data == element) {
                size--;
                current.next = current.next.next;
                return true;
            }
        }
        return false;
    }

    // Get element by idex
    public int get(int index) {
        if (head == null) {
            throw new ArrayIndexOutOfBoundsException();
        }
        if (index > 0 && index  ");
            current = current.next;
        }
        return builder.toString();
    }

    // Example
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);

        System.out.println("Initial LinkedList: " + list + "| size: " + list.size());
        System.out.println("Get index 2: " + list.get(2));
        System.out.println("Contains element 3: " + list.contains(2));
        System.out.println("-------------");
        System.out.println("Removing element 2: " + list.remove(2));
        System.out.println("LinkedList after removal: " + list + "| size: " + list.size());
        System.out.println("Get index 2: " + list.get(2));
        System.out.println("Contains element 3: " + list.contains(2));
    }
}

In the class above, we create the MyLinkedList class which has the exact same methods with the ArrayList but with different implementation. Note that for each method the head is used to either add, remove or start traversing the linked list. Let's run the main method which prints similar output with the ArrayList.

Output

Initial LinkedList: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> | size: 6
Get index 2: 3
Contains element 3: true
-------------
Removing element 2: true
LinkedList after removal: 1 -> 3 -> 4 -> 5 -> 6 -> | size: 5
Get index 2: 4
Contains element 3: false

Above, we print the exact same output we did for the ArrayList. In the following section we will compare the methods of the two data structures and their complexities.

5. Methods Comparison

Let's take a closer look at the equivalent methods of the ArrayList and LinkedList provided by Java, that we implemented in the previous examples, and check out their worst case time complexity.

5.1 Add Element

ArrayList

The add(element) method appends an element to the end of the ArrayList. If the size of the array hits its maximum capacity, then the ArrayList will create a new array with more capacity and copy all the elements over to the new array. Most of the times the time complexity of the add operation is O(1), but if the array has to grow it requires O(n) time. That is what we call the amortized constant time.

LinkedList

The add(element) method appends the specified element to the end of the LinkedList by adding the next node to the tail node (in the previous example we used the head node). The LinkedList class also has the addLast(element) and offerLast(element) methods which do the exact same operation. There is also the addFirst(element) and offerFirst(element) methods which insert the specified element at the beginning of the list using the head node. All those operations run in O(1), as they make use of the head and tail node references and do not require iterating over the list.

5.2 Remove Element

ArrayList

The remove(element) method removes the first occurrence of the specified element from the ArrayList, only if it is present. The time complexity of this operation is O(n), where n is the size of the array, as it might have to iterate all the elements to find the specified element to remove and then create a new array buffer.

LinkedList

The remove(element) of the LinkedList does exactly the same with the ArrayList, it removes the first occurrence of the specified element from the LinkedList, only if it is present. This operation is not used very often, as in a linked list data structure you would usually want to remove the first or last node of the list. The removeFirst() and removeLast() methods are used for that and run in O(1) as they make use of the head and tail.

5.3 Get Element By Index

ArrayList

The get(int index) method returns the element at the specified index of the ArrayList. If the index is out of range then it will throw an IndexOutOfBoundsException. The complexity of this operation is O(1).

LinkedList

Similarly, The get(index) method returns the element at the specified index of the LinkedList and throws an IndexOutOfBoundsException if the index is out of range. The complexity of this operation is O(n) as, in worst case, it will have to traverse all the nodes to find the specified element.

5.4 Contains Element

The contains(element) method for both ArrayList and LinkedList has to iterate the whole list to find the specified element so it runs in O(n) where n is the size of the list.

6. Complexity Comparison

Let's see below a comparison of the time complexity of the methods of the ArrayList and LinkedList we saw in the previous examples.

Add ElementRemove ElementGet By IndexContains Element
ArrayListO(1)O(n)O(1)O(n)
LinkedListO(1)O(1)O(n)O(n)

7. Performance Comparison

It's time to measure the performance of the methods we saw in the previous examples. To do that, we use the methods of the ArrayList and LinkedList classes provided by Java and we invoke the methods for both classes. The below class demonstrates that:

PerformanceComparison

public class PerformanceComparison {

    static final int COUNT = 1000000;

    public static void main(String[] args) {
        System.out.println("*** ArrayList Performance ***");
        performanceRun(new ArrayList());

        System.out.println("\n*** LinkedList Performance ***");
        performanceRun(new LinkedList());
    }

    static void performanceRun(List list) {
        for (int i = 0; i < COUNT; i++) {
            list.add(Integer.toString(i));
        }

        // add
        long now = System.currentTimeMillis();
        list.add("1");
        System.out.println("Add took: " + (System.currentTimeMillis() - now) + " ms");

        // get
        now = System.currentTimeMillis();
        list.get(COUNT / 2);
        System.out.println("Get took: " + (System.currentTimeMillis() - now) + " ms");

        // remove
        now = System.currentTimeMillis();
        list.remove(Integer.toString(1));
        System.out.println("Remove took: " + (System.currentTimeMillis() - now) + " ms");

        // contains
        now = System.currentTimeMillis();
        list.contains(Integer.toString(COUNT / 2));
        System.out.println("Contains took: " + (System.currentTimeMillis() - now) + " ms");
    }
}

In the above class, we initialise a new ArrayList and LinkedList objects and we add 1 million elements. Then we invoke the add(int element), remove(int element), get(int index) and contains(int element)methods and print the time each operation takes. Let's see the output and verify the time complexity of the methods.

Output

*** ArrayList Performance ***
Add took: 0 ms
Get took: 0 ms
Remove took: 3 ms
Contains took: 10 ms

*** LinkedList Performance ***
Add took: 0 ms
Get took: 8 ms
Remove took: 0 ms
Contains took: 10 ms

In the above output, the add method in both the ArrayList and LinkedList run in O(1) constant time. The get method in the ArrayList is very fast, it runs in O(1), whereas in the LinkedList it runs in O(n) as it has to traverse the list. The remove method, on the other hand, is faster in the LinkedList as it removes the head and acts like the removeFirst method which runs in O(1) time, whereas in the ArrayList it has to reorder the elements. Finally, the contains method runs in O(n) in both classes as it has to iterate over the lists to find the specified element.

8. Synchronization

The ArrayList and LinkedList classes are not synchronized and should not be used in a multi-threading program. If multiple threads access the lists concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array.

To synchronize an ArrayList or a LinkedList we can use the Collections.synchronizedList(list) method. This is best done at creation time, to prevent accidental unsynchronized access to the lists. Another alternative for a thread-safe ArrayList is the CopyOnWriteArrayList class, which achieves thread-safety by making a fresh copy of the underlying array in all mutative operations. The LinkedList has many alternatives as shown in the Oracle documentation:

  • LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
  • ArrayBlockingQueue — a bounded FIFO blocking queue backed by an array
  • PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
  • DelayQueue - a time-based scheduling queue backed by a heap
  • SynchronousQueue - a simple rendezvous mechanism that uses the BlockingQueue interface

9. When to use ArrayList vs LinkedList?

In the previous sections we measured the performance of the most important methods of the ArrayList and LinkedList. Based on that, we should use each data structure in different use cases.

The ArrayList having a O(1) time complexity in add and get operation should be used when we have many add or search by index operations. It should be avoided if there is a requirement for frequent remove operations as this runs in O(n). A very common use case for using the ArrayList is when we want to display a list on a website and access each item based on the index of the list.

The LinkedList should be avoided when we have too many search operations as it has to traverse the whole list. It should be used when we want to add or remove elements from the head or tail nodes as these run in O(1). A real-world example of the LinkedList is a queue, in which adding and removing elements from it is essential compared to searching the list.

10. Java ArrayList vs LinkedList - Conclusion

In this post, we compared the most commonly used methods of the ArrayList and LinkedList and provided custom implementations. We measured the time complexity and performance of those methods and saw that as best practice we should avoid using those classes in a multi-threading environment.

11. Download the Eclipse project

Download
You can download the full source code of the above examples here: Java ArrayList vs LinkedList Example

Lefteris Karageorgiou

Lefteris is a Lead Software Engineer at ZuluTrade and has been responsible for re-architecting the backend of the main website from a monolith to event-driven microservices using Java, Spring Boot/Cloud, RabbitMQ, Redis. He has extensive work experience for over 10 years in Software Development, working mainly in the FinTech and Sports Betting industries. Prior to joining ZuluTrade, Lefteris worked as a Senior Java Developer at Inspired Gaming Group in London, building enterprise sports betting applications for William Hills and Paddy Power. He enjoys working with large-scalable, real-time and high-volume systems deployed into AWS and wants to combine his passion for technology and traveling by attending software conferences all over the world.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

4 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Ravindu
Ravindu
5 years ago

Really Helpful article thank you

Mel
Mel
5 years ago

In your ArrayList implementation, you actually did not implement a get(int element) method like you say you did after the coded example. Rather, it looks like you are trying to implement both remove and get methods at the same time in your remove(int element) method and should’t compile. However, I do see your downloaded code has the correction. You might want to make it here as well.

Back to top button