Array

Voor de astronomische betekenis van het woord, voor een opstelling van radiotelescopen, zie interferometrie.

Een array is bij het programmeren van computers een datastructuur die bestaat uit een lijst van elementen. Ieder element heeft een unieke index waarmee dat element wordt aangeduid. De verschillende elementen in een array kunnen dezelfde waarde hebben. Hoewel een array een eenvoudige datastructuur is, kan er veel mee worden gedaan. Vectoren in een meerdimensionale ruimte kunnen bijvoorbeeld met een eenvoudige array worden geïmplementeerd. Een array heeft als index de elementen van een gegeven indexverzameling. De elementen van een array worden meestal opeenvolgend in het geheugen opgeslagen. In de meeste programmeertalen wordt de eis gesteld, dat alle elementen van de array van hetzelfde datatype zijn.

De eenvoudigste implementatie van een array, zoals in C gebeurt, is een rij opeenvolgende geheugencellen. Wanneer arrays als een rij van opeenvolgende geheugencellen worden geïmplementeerd, wordt het adres van het i-de element van een array gegeven door b+(i-1)*s, waarbij b het beginadres van de array is en s de grootte, in geheugeneenheden, van ieder element in de array. De efficiëntie van de indexatie is dus ${\displaystyle O(1)}$. Het voordeel van deze manier van implementeren is dus dat het indexeren erg efficiënt gaat. Het nadeel is dat iedere array een enkel ononderbroken geheugenblok nodig heeft. Dit kan leiden tot fragmentatie van het geheugen. Het is ook mogelijk om een array te implementeren met behulp van een gelinkte lijst in plaats van een opeenvolgend geheugenblok. De efficiënte is in dit geval ${\displaystyle O(x)}$ in plaats van ${\displaystyle O(1)}$. De nadelen van zo'n implementatie zijn dat het indexeren minder efficiënt is en dat er meer geheugen nodig is, minimaal één extra pointer voor ieder element. Het voordeel is dat zo'n implementatie flexibeler is, zij hoeven niet homogeen te zijn en kunnen ook dynamisch zijn.

Een dynamische array kan van lengte veranderen. Dit kan impliciet gebeuren, door het toevoegen of verwijderen van elementen, zoals met het append-statement in Python, of expliciet zoals met het ReDim-statement in Visual Basic. Andere talen die dynamische arrays ondersteunen zijn Perl en Lisp.