Information AboutArray |
| CATEGORIES ABOUT ARRAY | |
| arrays | |
|
Most Programming Language s have arrays as a built-in data type. Some programming languages (such as APL , some versions of Fortran , and J ) generalize the available operations and functions to work transparently over arrays as well as scalars, providing a higher-level manipulation than most other languages, which require loops over all the individual members of the arrays. ADVANTAGES AND DISADVANTAGES Arrays permit efficient (constant-time, O (1)) Random Access but not efficient insertion and deletion of elements (which are O(''n''), where ''n'' is the size of the array). Linked List s have the opposite trade-off. Consequently, arrays are most appropriate for storing a fixed amount of data which will be accessed in an unpredictable fashion, and linked lists are best for a list of data which will be accessed sequentially and updated often with insertions or deletions. Another advantage of 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 Table s, and in this case this is not a benefit. Arrays also are among 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 arrays have 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. For more information, see Bounds Checking . USES Although useful in their own right, arrays also form the basis for several more complex data structures, such as Heaps , Hash Table s, and VList s, and can be used to represent Strings , Stacks and Queue s. They also play a more minor role in many other data structures. All of these applications benefit from the compactness and locality of arrays. One of the disadvantages of an array is that it has a single fixed size, and although its size can be altered in many environments, this is an expensive operation. Dynamic Array s or ''growable arrays'' are arrays which automatically perform this resizing as late as possible, when the programmer attempts to add an element to the end of the array and there is no more space. To average the high cost of resizing over a long period of time (we say it is an Amortized Cost ), they expand by a large amount, and when the programmer attempts to expand the array again, it just uses more of this reserved space. |
|
|