The Self-Taught Computer Scientist

9Arrays

We salute the coders, designers, and programmers already hard at work at their desks, and we encourage every student who can't decide whether to take that computer science class to give it a try.

Michael Bloomberg, former mayor, New York City

A list is an abstract data type that describes a data structure that stores ordered values. Lists usually have an operation for creating a new, empty list, testing if it is empty, prepending an item, appending an item, and accessing an element at an index. You are already familiar with Python lists, one of many different implementations of the list abstract data type, which is a type of array. In this chapter, you will learn more about arrays.

An array is a data structure that stores elements with indexes in a contiguous block of memory. Arrays are often homogeneous and static. A homogeneous data structure can hold only a single data type, such as integers or strings. A static data structure is a data structure you cannot resize after you create it. When you create an array in a low-level programming language like C, you decide how many elements of a particular data type you want to store in it. Then, your computer assigns a block of memory for your array based on the number of elements and how much memory one element of that data type requires. This block consists of items stored one after the other in your computer's memory.

A Python list is a heterogeneous variable-length array. A variable-length array is one with a size that ...