Things every software engineer should know: Array Lists

7 min readMar 2, 2020

TL:DR

Array Lists are a good general purpose list that typically get used in place of a bare array, usually because they are easier to work with. They are good when there is a use case involving access of the element at position i and adding / removing elements from the end of the list. Use an alternative option when the use case involves adding / removing from somewhere that isn’t the end of the list.

Who dis?

Hi, I’m Doogal, I’m a Tech Lead at Babylon Health, I’m the founder of doodl.la, I’ve also spent a bunch of years learning software engineering from a several very talented people and these stories are my way of trying to pay it forward.

During my time as a Tech Lead I have mentored a lot of new software engineers and I have found there is often a situation where engineers don’t know what they don’t know. So this “Things every software engineer should know” series is a cheatsheet of the information I’d give myself in my first year of doing software.

Software is a large subject and the golden rule is that the answer to any question can start with “It depends, …”, as a result, the information in these stories is not complete. It is an attempt to give the bare essential information, so as you read these stories, please keep in mind that the rabbit hole goes deeper than the subject matter displayed here.

Basic Structure

Array Lists, as the name may suggest, are backed by an array. They are also referred to as Growable Arrays or Dynamic Arrays. The basic concept is that you have a list with the same kind of capabilities of an array but you don’t need to be wary of the size of the array and if you are going to try and add an element that will go beyond the max size allocated for the array.

The implementation of an Array List is relatively simple, it is an array containing the items of the list. When you try to get an item from an index in the list, that is passed directly to the index of the underlying array. The difference between an Array List and an ordinary array is that when you add more items to the list than the underlying array has room for, a whole new (larger) array is created and all of the items from the smaller array are copied into the new larger array.

In order to avoid having to do an expensive resizing every single time a new element is added, Array Lists tend to increase their size by a large amount, usually somewhere between 1.5 and 2 times the current size of the backing array.

The basic operations

Getting the item at index i

Getting an item in a random location is pretty easy to implement, the index that was passed to the list is used as the index to pass into the backing array. The Array List effectively just does an array index lookup.

What about the time complexity of this operation?

It’s O(1), which means that it is constant time, the time to retrieve an object at a random index does not vary based on the size of the list. The reason it is O(1) is because retrieving an item from an array is an O(1) operation, the reason that is O(1) would require going into the details of how arrays work which could fill a whole separate story. If you are interested then more information can be found here.

Adding / Removing an item to the end of the list

Adding an element to the end of the list is, for the majority of the time, very easy. The new element is added into an empty space in the backing array at the index that is the max size of the list. Similarly, when removing an item from the end of the list, the element in the last index of the backing array is removed. However, what happens if we try to add 5 items to an Array List that has a backing array of size 4? Then, we need to allocate a whole new backing array and copy all 5 elements into that new array.

The time complexity for adding / removing an item from the end of the list is O(1) most of the time, because the operations are being performed against the backing array alone. In the case where we are having to copy a new array because we have exceeded the size of the backing array, the time complexity is O(N) because the number of elements we are copying over is equal to the size of the Array List. So what is the overall time complexity? Most of the time it’s O(1) but sometimes it’s O(N), what does that average out to? The short answer is something called “amortized” O(1), it can be thought of as O(1) for practical purposes, but if you are interested in more detail, it can be found here.

Adding / Removing an item to the beginning of the list

Adding or removing an element to the beginning of an Array List is more complex than at the end. We cannot simply add / remove space from the start of the backing array. Instead, all the elements in the backing array need to be shifted. The elements are shifted one index up when adding to the beginning, the new element is then placed into the space that has now been created at the first index. The elements are shifted one index down when removing from the beginning, in shifting down, the element in the first index is overwritten and removed.

The time complexity of these operations is O(N), this is because the time taken in shifting all the elements in an array up or down increases proportionally with the size of the array.

Inserting / Removing an item somewhere into the list

This operation is very similar to adding / removing from the beginning of the list. The slight difference is that only the elements after the index being inserted / removed are shifted. So if we are inserting / removing at the end of the list, no elements need to be shifted.

Similar to adding / removing from the beginning of the list, the time complexity is O(N) because the number of elements that need to be shifted increases proportionally with the size of the array. The total number of elements being shifted is usually going to be less than the number being shifted if an element is added / removed from the beginning. However, even if the time is less, the growth in complexity grows with the size of the array and so the time complexity is still O(N).

What are Array Lists good for

Array lists tend to be good generic usage lists, they are basically arrays where you don’t need to worry about resizing them. So anything that arrays are good for, Array Lists are also probably good for. They tend to be the de-facto collection in languages like Java. If I am doing a code review and someone has used an Array List, I don’t tend to question it (unless they are doing something interesting with it). If someone uses a different implementation, like Linked List, then I tend to ask why, to find out what behaviour they are after that an Array List wouldn’t provide.

More specifically, in use cases where there is a lot of access of elements by their index, and the list is growing / shrinking only by manipulating the end of the list. Then an Array List is probably a good choice.

In the use case of adding elements to a list and then iterating through that list from beginning to end, both Linked List and Array List have very similar complexities, so which should you choose? You could use either, for this use case they are broadly the same. However, typically I’d expect someone to use an Array List, partly because Array Lists are more memory efficient (but usually that isn’t a huge concern), but mainly because Array Lists tend to be the default list and using something different adds a bit of cognitive load to the reader to try work out why the writer used something other than an Array List.

What are Array Lists not good for

Array Lists are not a good choice if the use case involves a lot of adding / removing of elements from a position in the list that is not the end. If the use case involves a lot of adding / removing from the beginning of the list then something like a Linked List is a good alternative. If the use case involves a lot of adding and removing from the middle of the list then potentially using something like a Hash Map with integer keys might work.