Sparse array

Arrays are datastructures 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 some indices are ever used.

A sparse array is an array where only very few indices are used. If this is known in advance, more space-efficient implementations can be used, which only allocates space for the entries that are actually used.

Example: An array with length 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.