Sparse array - Definition

A sparse array in computing is an array where only very few indices are in practice used. Arrays are data structures used in programming languages. They map integer positions, or indices, less than the array's length, to values.

A typical implementation allocates space for the entire array, even if only a few indices are ever used. If the sparsity is known in advance, more space-efficient implementations can be used, only allocating space for the entries that are actually used.

Example: An array with length of one million, where only the indices 1, 3, 120 and 999999 are used, is sparse. It would be inefficient to allocate any space for the remaining 999996 possible array elements.

See also: sparse matrix