The Array: The Foundational Data Structure

The array is one of the most basic data structures in computer science. (In Python, the built-in array-like data structure is called a list, but I’ll refer to them as arrays, keeping in line with the more general computer science term.) I assume you’ve worked with arrays before, so you’re aware that an array is a list of data elements. The array is versatile and can serve as a useful tool in many situations, but let’s take a look at one quick example.

If you’re looking at the source code for an application that allows users to create and use shopping lists for the grocery store, you might find code like this:

This array happens to contain five strings, each representing something that I might buy at the supermarket. (You’ve got to try elderberries.)

Arrays come with their own technical jargon.

The size of an array is how many data elements the array holds. Our grocery list array has a size of 5 since it contains five values.

The index of an array is the number that identifies where a piece of data lives inside the array.

In most programming languages, we begin counting the index at 0. So for our example array, "apples" is at index 0, and "elderberries" is at index 4, like this:

Data Structure Operations

To understand the performance of any data structure—such as the array—we need to analyze the common ways our code might interact with that data structure.

Many data structures are used in four basic ways, which we refer to as operations. These operations are:

• Read: Reading refers to looking something up at a particular spot within the data structure. With an array, this means looking up a value at a particular index. For example, looking up which grocery item is located at index 2 would be reading from the array.

• Search: Searching refers to looking for a particular value within a data structure. With an array, this means looking to see if a particular value exists within the array and, if so, at which index. For example, looking up the index of "dates" in our grocery list would be searching the array.

• Insert: Insertion refers to adding a new value to our data structure. With an array, this means adding a new value to an additional slot within the array. If we were to add "figs" to our shopping list, we’d be inserting a new value into the array.

• Delete: Deletion refers to removing a value from our data structure. With an array, this means removing one of the values from the array. For example, if we removed "bananas" from our grocery list, this value would be deleted from the array.

In this chapter, we’ll analyze how fast each of these operations is when applied to an array.