En sparse array er en abstrakt repræsentation af en almindelig array , hvor dataene ikke præsenteres kontinuerligt, men fragmenteret; de fleste af dets elementer har samme værdi (standardværdien, normalt 0 eller null). Desuden er lagring af et stort antal nuller i et array ineffektivt både til lagring og behandling af arrayet.
Et sparsomt array kan få adgang til udefinerede elementer. I dette tilfælde vil arrayet returnere en eller anden standardværdi.
Den enkleste implementering af dette array tildeler plads til hele arrayet, men når der er få ikke-standardværdier, er denne implementering ineffektiv. Funktioner til at arbejde med almindelige arrays anvendes ikke på dette array i tilfælde, hvor sparsitet er kendt på forhånd (for eksempel ved lagring af data i blokke).
Et sparsomt array er normalt repræsenteret som et associativt array :
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]eller Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],hvor hver position pos i svarer til værdien val i . Denne metode bruges til at spare hukommelse (både nøglen og værdien bærer information).
En sammenkædet liste bruges her i stedet for en almindelig matrix, fordi en almindelig matrix for det første kræver plads til at gemme udefinerede værdier. For eksempel, når du erklærer:
double arr[1000][1000];8 MB hukommelse vil blive allokeret på én gang (8 bytes pr. værdi × 1.000.000 værdier), hvilket er et uberettiget spild af hukommelse. I tilfælde af en linket liste gemmes tomme værdier ikke, og plads til nye værdier tildeles automatisk, når elementer tilføjes eller fjernes (i dette tilfælde kan vi tale om dynamisk hukommelsesallokering ).