The elements in an array must be of the same basic data type but why must they be stored in contiguous memory?

Answer 1

An array is nothing more than a block of contiguous memory addresses divided into one or more units of equal length. We call these units elements. As a result, all elements of an array must be allocated contiguously.

Other than padding for memory alignment purposes, an array offers the most compact storage for multiple elements of the same type. And because the elements are allocated contiguously, it is trivial to traverse the array from one element to the next using nothing more than a pointer variable of the same type as the array. Each increment or decrement of the pointer increases or decreases the address by 1 element. The array suffix operator [] does the same thing, except the index is a zero-based offset from the start of the array. The first element is index 0 because it is 0 elements from the start of the array while the nth element is found at index n-1.

When we create an array we have the choice of storing the objects themselves in the array or storing a pointer to the objects. With the latter, the objects need not be allocated contiguously, however we consume more memory because the array of pointers consumes additional memory that we wouldn't need to consume were all the objects allocated in the array itself. We also have the additional cost of dereferencing those pointers in order to access the objects being referred to. However, arrays of pointers are advantageous when the objects are larger than a pointer (in bytes) or are of polymorphic type. Copying or moving a large object in memory is more expensive than copying or moving a pointer, so if we need to sort an array of large objects, an array of pointers is generally more efficient despite the indirection. But with polymorphic types we have to use pointers because polymorphic types are not guaranteed to be the same length so we must store a pointer to the common base type if we wish to retain polymorphic behaviour.