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:
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.
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.
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 Element | Remove Element | Get By Index | Contains Element | |
| ArrayList | O(1) | O(n) | O(1) | O(n) |
| LinkedList | O(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
You can download the full source code of the above examples here: Java ArrayList vs LinkedList Example
Really Helpful article thank you
Thank you Ravindu I am glad you liked it
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.
You are right Mel, thanks for noticing that. I have updated the article so it should be ok now.