Essential Algorithms: A Practical Approach to Computer Algorithms

CHAPTER 4

Arrays

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 way, but special-purpose arrays can be useful in certain cases, so they deserve some attention here.

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

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 boxes where a program can store values.

Typically a program declares a variable to be an array with a certain number of dimensions and certain bounds for each dimension. For example, the following code shows how a C# program might declare and allocate an array named numbers that has 10 rows and 20 columns:

int[,] ...