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

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. (Multidimensional arrays are not exactly linear, but they are implemented as linear arrays of linear arrays.) 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 average 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).

The price for this improved lookup is significantly decreased efficiency for 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 the gap left by a deletion; this is an O(n) operation.

Arrays are not dynamic data structures: They have a finite, fixed ...