You may enjoy using an ArrayList over an array in Java since the size can change dynamically. But the same could be said about linked lists. So how are they different and when would you want to use one over the other?

ArrayList

As you may know, an ArrayList is a convenience wrapper for arrays. When you want to add a new element to an already full ArrayList, the ArrayList library will copy over its internal array into a larger array. This copying can be a slow process, particularly if you have lots of elements.

In Java, the elements in an ArrayList, like arrays, are stored sequentially (one element after another with no gaps in between). This has the benefit of quick random access. Suppose you had the following code:

ArrayList<Integer> shoeSizes = new ArrayList<>();

...

shoeSizes.get(299);

In this snippet, we access the 300th element (at index 299). Behind the scenes, this can be retrieved without needing to traverse through the first 299 elements.

Since an ArrayList is stored sequentially, removing an element in the middle of it can also be expensive. Say we wanted to delete the 100th element (stored at the 101st index position) in the ArrayList above. The elements at the index position from 0 to 100 (inclusive) stay put and the 101st element is deleted. Recall that I said that there could be no gaps. Consequently, this means that the elements at the index position 102 onwards need to move back one position. With a lot of elements, this is a slow operation.

Linked lists

Unlike an ArrayList, linked lists are not stored sequentially. Each element is stored in a node that contains the data. In Java, linked lists are doubly linked lists. As such, each node stores both a link to the next node in the sequence as well as the previous.

LinkedList<Integer> shoeSizes = new LinkedList<>();

One of the downsides of using a LinkedList over an ArrayList is that you don’t get random access. If you wanted to access the 300th element, you would need to traverse the linked list from the beginning. The LinkedList class does provide a get method for convenience:

LinkedList<Integer> shoeSizes = new LinkedList<>();
Integer shoeSize = shoeSizes.get(300);

Don’t be fooled! This is still an inefficient method.

When to use an ArrayList over a LinkedList

An ArrayList should be used over a LinkedList when you need to access specific elements inside it (random access).

When to use a LinkedList over an ArrayList

A LinkedList should be used over a ArrayList when you need to add or remove an element in the middle of the list. This is probably not an issue if you’re dealing with a small number of elements. For a large number of elements, this would be inefficient. With a LinkedList, the elements don’t move, only the links to the previous and next elements change.

Instead of using an ArrayList, you could use a Vector. This is preferable for when you need to access the elements from multiple threads. If you don’t, an ArrayList is more efficient.

Photo by Manuel Sardo on Unsplash