Array (data structure): Difference between revisions

Revision as of 20:25, 23 November 2003

Revision as of 20:28, 23 November 2003

Line 7:

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 there is no benefit.

Arrays also are among the most compact data structures; if you store 100 integers in an array, it takes only as much space as the 100 integers, and no more. Any pointer-based data structure, on the other hand, must keep its pointers somewhere, and these occupy space. This effect is magnified the smaller the data elements become; for example, an array of 100 [[character (computing)|character]]s usually takes 100 bytes, while on a 32-bit platform an aligned linked list of 100 characters takes 800 bytes, eight times as many. Conversely, for very large elements, the space difference becomes negligible.

A drawback of the simplicity of arrays is the possibility of referencing a non-existent element by using an index outside the range of valid indices. This is known as ''exceeding the array bounds''. The result is, at best, a program working with incorrect data. At worst, the whole system can [[crash]]. This problem is particularly felt in the [[C programming language]], the powerful syntax of which is unfortunately prone to this kind of error. Some other languages have built-in [[bounds checking]], and will refuse to index an array outside of its permitted range.

Line 13:

Although useful in their own right, arrays also form the basis for several more complex data structures, such as [[heap]]s, [[hash table]]s, and [[vlist (computer science)|vlist]]s, and can be used to represent [[string]]s, [[stack]]s 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 benefits of arrays.

In the [[C programming language]], one-dimensional [[character (computing)|character]] arrays are used to store null-terminated [[string]]s, so called because the end of the string is indicated with a special reserved character called a [[null character]] ('\0').

See also: [[Monge array]], [[set]], [[collection]]