3.3 Why Study Arrays

You will notice the array structure looks very similar to Python's list structure. That's because the two structures are both ordered sequences that are composed of multiple sequential elements that can be accessed by position. But there are two major differences between the array and the list. First, an array has a limited number of operations, which commonly include those for array creation, reading a value from a specific element, and writing a value to a specific element. The list, on the other hand, provides a large number of operations for working with the contents of the list. Second, the list can grow and shrink during execution as elements are added or removed while the size of an array cannot be changed after it has been created.

You may be wondering, if Python provides the list structure as its mutable sequence type, why are we bothering to discuss the array structure, much less plan to implement an abstract data type for working with arrays in Python? The short answer is that both structures have their uses. There are many problems that only require the use of a basic array in which the number of elements is known beforehand and the flexible set of operations available with the list is not needed.

The array is best suited for problems requiring a sequence in which the maximum number of elements are known up front, whereas the list is the better choice when the size of the sequence needs to change after it has been created. As you will learn later in the chapter, a list contains more storage space than is needed to store the items currently in the list. This extra space, the size of which can be up to twice the necessary capacity, allows for quick and easy expansion as new items are added to the list. But the extra space is wasteful when using a list to store a fixed number of elements. For example, suppose we need a sequence structure with 100,000 elements. We could create a list with the given number of elements using the replication operator:

But underneath, this results in the allocation of space for up to 200,000 elements, half of which will go to waste. In this case, an array would be a better choice.

The decision as to whether an array or list should be used is not limited to the size of the sequence structure. It also depends on how it will be used. The list provides a large set of operations for managing the items contained in the list. Some of these include inserting an item at a specific location, searching for an item, removing an item by value or location, easily extracting a subset of items, and sorting the items. The array structure, on the other hand, only provides a limited set of operations for accessing the individual elements comprising the array. Thus, if the problem at hand requires these types of operations, the list is the better choice.