Collections: When to use an ArrayList over a LinkedList (& visa versa)
When and why you may want to use one over the other
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?
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 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:
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.
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.
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.
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:
Don’t be fooled! This is still an inefficient method.
When to use an ArrayList over a LinkedList
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
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