The first data structure we are going to analyze is the array.

An array is a collection of items stored in a contiguous block of memory. This means the items are stored right next to each other in memory.

Here is a diagram of a memory block containing an array of numbers.

44

65

89

55

What's the difference between a Python list and an array?

When you write Python code you don't interact with arrays directly, instead you use lists.

Every Python list uses an array of memory under the hood to store the list items.

Lists are a Python specific construct built on top of arrays.

Lists manage the amount of memory the underlying array needs so you don't have to think about it.

Arrays have a fixed size

Arrays themselves have a fixed size. This means that when we write this Python code:

items = []

Under the hood an array of some default size, let's say 4, is allocated.

__

__

__

__

Now let's append 3 elements to our Python list:

items = [] items.append(54) items.append(82) items.append(90)

The underlying array now looks like this:

54

82

90

__

Now let's append 2 more elements to our Python list:

items = [] items.append(14) items.append(25)

Here is what the array looks like now:

54

82

90

14

25

We were able to append 14 to the list because there was 1 spot left in the underlying array, but there was not room for 25.

However, in practice we know that when using Python lists there is no limit on the amount of appends we can do. So what is going here?

A list will dynamically resize its array

When the underlying array of a Python list fills up, the list will do the following to make room for the additional item:

First, a second array is created that is twice as big as the current array.

54

82

90

14

__

__

__

__

__

__

__

__

Second, the elements from the first array are copied to the second array.

54

82

90

14

54

82

90

14

__

__

__

__

Third, there is now room for the additional item so it is appended to the new array.

54

82

90

14

54

82

90

14

25

__

__

__

Lastly, the old array is deleted.

54

82

90

14

25

__

__

__

Once this array of size 8 fills up, the process will repeat itself resulting in a new array of size 16.

Because of this resizing behavior, you will often hear a Python list referred to as a dynamic array, because it dynamically resizes the underlying array.

Concept Check

Arrays vs Lists