Array lists

From Schoolcoders wiki
Jump to: navigation, search
Level: A Level Computing


An array list is a data structure that implements a list abstract data type that is 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.


Array-list-implementation-1.png


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 elemnt 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.


Array-list-implementation-2.png


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 aray 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.


Array-list-implementation-3.png


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