Sparse array

In computer science, a sparse array is an array in which most of the elements have the default value (usually 0 or null). The occurrence of zero-value elements in a large array is inefficient for both computation and storage. An array in which there is a large number of zero elements is referred to as being sparse.

In the case of sparse arrays, one can ask for a value from an "empty" array position. If one does this, then for an array of numbers, a value of zero should be returned, and for an array of objects, a value of null should be returned.

A naive implementation of an array may allocate space for the entire array, but in the case where there are few non-default values, this implementation is inefficient. Typically the algorithm used instead of an ordinary array is determined by other known features (or statistical features) of the array. For instance, if the sparsity is known in advance or if the elements are arranged according to some function (e.g., the elements occur in blocks).
A heap memory allocator in a program might choose to store regions of blank space in a linked list rather than storing all of the allocated regions in, say a bit array.

Representation

Sparse Array can be represented as

`Sparse_Array[{pos1 -> val1, pos2 -> val2,...}]` or
`Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]`

which yields a sparse array in which values ${\displaystyle val_{i}}$ appear at positions ${\displaystyle pos_{i}}$.

`double arr[1000][1000]`