3.1 The Array Structure

At the hardware level, most computer architectures provide a mechanism for creating and using one-dimensional arrays. A one-dimensional array, as illustrated in Figure 3.1.1, is composed of multiple sequential elements stored in contiguous bytes of memory and allows for random access to the individual elements.

The array structure is another example of a mutable indexed ordered sequence in which the elements are arranged in linear order from front to back and the elements of the sequence are accessible by position. As you may remember, Python provides several indexed sequences, two immutable indexed sequences, strings and tuples, and one mutable indexed sequence, the list.

The entire contents of an array are identified by a single name. Individual elements within the array can be accessed directly by specifying an integer subscript or index value, which indicates an offset from the start of the array. This is similar to the mathematics notation $x_i$, which allows for multiple variables of the same name. The difference is that programming languages typically use square brackets following the array name to specify the subscript, x[i].

Figure 3.1.1: A sample 1-D array consisting of 11 elements.

The Array ADT

The array structure is commonly found in most programming languages as a primitive type, but Python only provides the list structure for creating mutable sequences. We can define the Array ADT to represent a one-dimensional array for use in Python that works similarly to arrays found in other languages. It will be used throughout the text when an array structure is required.

ADT Definition

Some computer scientists consider the array a physical structure and not an abstraction since arrays are implemented at the hardware level. But remember, there are only three basic operations available with the hardware-implemented array. As part of our Array ADT, we have provided for these operations but have also included an iterator and operations for obtaining the size of the array and for setting every element to a given value. In this case, we have provided a higher level of abstraction than that provided by the underlying hardware-implemented array.

Special Topic

The ezarrays Python Module

Python is a scripting language built using the C language, a high-level language that requires a program's source code be compiled into executable code before it can be used. The C language is a very powerful programming language that provides syntax for working with the complete functionality available by the underlying hardware. That syntax, however, can be somewhat cryptic compared to Python, especially for a Python programmer who may not be familiar with the C programming language. Many of the data types and classes available in Python are actually implemented using appropriate types from the C language. While Python does not provide the array structure as part of the language itself, it does include low-level modules that provide access to the diverse set of data types available in the C language. These low-level modules can be used to implement a true hardware array version of the Array ADT. The implementation details of a hardware array, however, are beyond the scope of this text. Thus, we have included the ezarrays module as part of this textbook. That module, provides the Array class that implements the Array ADT using a true hardware array along with the Array2D and MultiArray classes for creating arrays of larger dimensions. Documentation for the ezarrays module is available online at https://ezarrays.necaise.org