Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

6.1. Arrays

An array is a sequence of variables of the same type arranged contiguously in a block of memory. Because arrays play an important role in every major language used in commercial development, we assume you're at least somewhat familiar with their syntax and usage. With that in mind, this discussion focuses on the theory and application of arrays.

Like a linked list, an array provides an essentially linear form of storage, but its properties are significantly different. In a linked list, lookup is always an O(n) operation, but array lookup is O(1) as long as you know the index of the element you want. The provision regarding the index is important — if you know only the value, lookup is still O(n) in the worst case. For example, suppose you have an array of characters. Locating the sixth character is O(1), but locating the character with value 'w' is O(n).

Of course, multidimensional arrays are not exactly linear, but they are implemented as linear arrays of linear arrays (of linear arrays . . . repeated as needed), so even multidimensional arrays are linear in each dimension.

The price for this improved lookup is significantly decreased efficiency in the insertion and deletion of data in the middle of the array. Because an array is essentially a block of contiguous memory, it's not possible to create or eliminate storage between any two elements as it is with a linked list. Instead, you must physically move data within the array to make room for an insertion or to close ...