I’ve been reviewing some material for interviews and something new I learned today is the difference between ArrayList and LinkedList.

The Big O Notes

For just review, the Big O for the operations for each data structure is:

For LinkedList

1
2
3
4

* get is O(n)
* add is O(1)
* remove is O(n)
* Iterator.remove is O(1)

For ArrayList <div class=’bogus-wrapper’>

But why the difference?

Well, something that’s obvious to me now, but wasn’t before is that ArrayList is actually backed by an array.

So what does that mean? That means that on average, adding an element to the ArrayList is constant time, since it just adds it to the next empty index. But there can be a case when the backing array is full and it needs to be made bigger. So then a new array is made, the elements are copied over, which leads to an operation of O(n).

And now the reason why remove is O(n) makes sense, if the first element was to be removed, the whole array must be shifted.

Conclusions

So when does LinkedList make sense? When you want to quickly add something to a data structure and the difference between ArrayList is that the operation is always O(1) instead of amortized O(1).

ArrayList is good for when O(1) operations are needed for adding/getting, but remember that if the list grows by a large amount that reinitializing the backing array will be costly.

By the way, an alternative for LinkedList is ArrayDeque which gives constant operations for adding/removing at both ends of the queue. I was first exposed to this data structure in Python, where it was called deque.

Update

I recently added notes for Java Collections on my GitHub Notes Repository. Check it out!