Řídké pole je abstraktní reprezentace běžného pole , ve kterém nejsou data prezentována nepřetržitě, ale fragmentována; většina jeho prvků má stejnou hodnotu (výchozí hodnota, obvykle 0 nebo null). Navíc ukládání velkého počtu nul do pole je neefektivní jak pro ukládání, tak pro zpracování pole.
Řídké pole může přistupovat k nedefinovaným prvkům. V tomto případě pole vrátí nějakou výchozí hodnotu.
Nejjednodušší implementace tohoto pole alokuje místo pro celé pole, ale pokud existuje několik nevýchozích hodnot, je tato implementace neefektivní. Funkce pro práci s běžnými poli se na toto pole neuplatňují v případech, kdy je řídkost předem známa (například při ukládání dat do bloků).
Řídké pole je obvykle reprezentováno jako asociativní pole :
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]nebo Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],kde každá pozice pos i odpovídá hodnotě val i . Tato metoda se používá pro úsporu paměti (klíč i hodnota nesou informace).
Zde je použit propojený seznam namísto běžného pole, protože za prvé, běžné pole vyžaduje prostor pro uložení nedefinovaných hodnot. Například při prohlášení:
double arr[1000][1000];Najednou bude přiděleno 8 MB paměti (8 bajtů na hodnotu × 1 000 000 hodnot), což je neopodstatněné plýtvání pamětí. V případě propojeného seznamu se prázdné hodnoty neukládají a místo pro nové hodnoty se přiděluje automaticky při přidání nebo odebrání prvků (v tomto případě můžeme mluvit o dynamické alokaci paměti ).