Array lists

An array list is a data structure that implements a list based on a normal array. Internally, an array list contains:

• An array. The array is usually a bit longer than the initial list, so there is some room to add extra elements.
• An integer variable to store the current length of the list.

This page describes how array lists work internally. If you are using a list type in Python, Java, or some other language, all of this is done automatically. The description below explains what is happening under the hood.

Creating the list

Suppose we created a list with 5 elements:

LIST k = [8, 6, 4, 2, 0]

When the list is created, an array will be allocated automatically to store the list contents. But to allow the list to grow, the array would usually be larger than the initial size of the list. Typically, the initial array is about twice the size required to hold required elements.

The variable Length is stored as part of the list. This variable keeps track of how long the list is - although the array is 10 elements long, the list itself is only 5 elements long.

Adding elements

Suppose we want to add a new element, for example adding a value 5 at index 3 in the list. Since the array is longer than the required list, the extra element is added by copying the existing elements 2 and 0 one space to the right to create a gap. Then the value 5 is written at index 3.

The Length variable is incremented to 6, because the list is now 6 elements long.

Adding more elements

We can continue adding elements until the length gets to 10. At that point, the internal array is full. So what happens of we want to add another element? For example suppose our list looked like this, and we wanted to insert a value 7 at position 8:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

When the array is full, an array list automatically creates a new, larger array. Usually, the new array will be about twice the size of the previous array (so, 20 elements in this case). If the array needed to be resized again it would increase to 40 elements, then 80 and so on.

The elements from the old array are copied into the new array, and then the extra element is added as before.

The old array is no longer needed, so that memory is freed - it is given back to the system so it can be used for something else.

Removing elements

If you remove an element from the list, the array elements to the right of the removed element will be shifted to the left by one place, and the Length variable will be reduced by 1.

As we saw before, as we add elements we sometimes have to create a new bigger array (when the old one gets too small). You might think that if we remove elements we might sometimes free our larger array and start using a smaller one. In fact, array lists don't usually do this, because it could lead to memory continuously being allocated and freed, which can cause performance problems.

There may be a function your code can call to force the array to release memory. For example Java has a function trimToSize() that does this.

Benefits of array lists

An array list has the advantage that the elements are stored in a normal array, so it is very quick find an element by index. It is also memory efficient.

It has the disadvantage that adding or removing elements can be slow for large lists, because parts of the list have to be copied to a different place in memory. However, modern CPUs can do this very quickly.

See also

• Abstract data types
• Arrays
• Lists
• Linked lists
• Static vs dynamic data structures
• Queues
• List based queues
• Circular queues