Essential Algorithms, 2nd Edition

CHAPTER 4Arrays

Arrays are extremely common data structures. They are intuitive, easy to use, and supported well by most programming languages. In fact, arrays are so common and well understood that you may wonder whether there's much to say about them in an algorithms book. Most applications use arrays in a relatively straightforward manner, but special-purpose arrays can be useful in certain cases, so they deserve some attention here.

This chapter explains algorithmic techniques that you can use to make arrays with nonzero lower bounds, save memory, and manipulate arrays more quickly than you can normally.

NOTE

Python does not have arrays, but lists can do the same things in most cases.

Python also does not have multidimensional lists, but you can use a list of lists instead. For example, instead of an array with an entry at position [i, j], you can use a list of lists with an entry at position [i][j].

Basic Concepts

An array is a chunk of contiguous memory that a program can access by using indices—one index per dimension in the array. You can think of an array as an arrangement of boxes where a program can store values.

Figure 4.1 illustrates one-, two-, and three-dimensional arrays. A program can define higher-dimensional arrays, but trying to represent them graphically is hard.

Figure 4.1: You can think of one-, two-, and three-dimensional arrays as arrangements of ...