73-8. What do you think are advantages and disadvantages of arrays?
Arrays permit efficient (constant time) random access butnot efficient insertion and deletion of elements. Consequently, arrays are most appropriate for storing a fixed amount of data which will be accessed in an unpredictable fashion. Another advantageof arrays that has become very important on modern architectures is that iterating through an array has good locality of reference, and so is much faster than iterating through (say) a linked list of the same size, which tends to jump around in memory. However, an array can also be accessed in a random way, as is done with large hash tables, and in this case this is not a benefit.
Arrays also areamong the most compact data structures; storing 100 integers in an array takes only 100 times the space required to store an integer, plus perhaps a few bytes of overhead for the whole array. Any pointer-based data structure, on the other hand, must keep its pointers somewhere, and these occupy additional space. This extra space becomes more significant as the data elements become smaller. For example, an array of ASCII characters takes up one byte per character, while on a 32-bit platform, which has 4-byte pointers, a linked list requires at least five bytes per character. Conversely, for very large elements, the space difference becomes a negligible fraction of the total space. Because arrayshave a fixed size, there are some indexes which refer to invalid elements - for example, the index 17 in an array of size 5. What happens when a program attempts to refer to these varies from language to language and platform to platform.