Array

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 $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 $O(x)$ in plaats van $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.

Voorbeeld in C

Voorbeeld van een array van integers in de programmeertaal C:

int array[2]; // Een array met 2 integers (geen van de elementen hebben (nog) een waarde)
array[0] = 1; // Geeft het allereerste element in de array waarde 1
array[1] = 3; // Geeft het tweede element in de array waarde 3

Hierbij is de naam van de array "array" en de opgeslagen waarden in de array zijn 1 en 3. Deze waarden zijn nu te gebruiken met behulp van array[0] en array[1]. De index van de eerste waarde in de array is in sommige programmeertalen nul, bijvoorbeeld C of PHP, maar in andere programmeertalen een. Er zijn ook talen waar men zelf de ondergrens kan bepalen, bijvoorbeeld Perl.

Meerdimensionele arrays

Het hierboven genoemde voorbeeld is een eendimensionale array, ook wel vector genoemd. Het is in veel programmeertalen ook mogelijk om meerdimensionale arrays te gebruiken. Een tweedimensionale array wordt ook wel een matrix genoemd.

Er bestaan verschillende manieren om een multidimensionale array te representeren in een computergeheugen. Eén mogelijkheid is om een array te maken met pointers naar andere arrays, zoals in de afbeelding is weergegeven. Als we een tweedimensionale array beschouwen als een tabel met rijen en kolommen, dan zijn de rijen afzonderlijke arrays. Een voordeel hiervan is dat de rijen niet allemaal even lang hoeven te zijn. Een array waarin deze rijen niet allemaal even lang hoeven te zijn heet een 'jagged array'. De lengte van de rijen kan dan dynamisch worden aangepast.

Een andere mogelijkheid is om de rijen achter elkaar op te slaan als elementen in een eendimensionale array. Een tweedimensionale array met m rijen en n kolommen wordt dan een eendimensionale van grootte m×n. De eerste rij is dan opgeslagen in elementen 1 tot en met n, de tweede in elementen n+1 tot en met 2n, enzovoort. Het voordeel van deze representatie is snelheid: alle elementen staan bij elkaar in het geheugen en er hoeven geen pointers naar andere delen van het geheugen te worden gevolgd.

De uitbreiding naar drie- en meerdimensionale arrays is in beide gevallen is mogelijk door een array van tweedimensionale arrays te maken, enzovoort.

Associatieve arrays

Voor een associatieve array gelden minder restricties op de index: het is toegestaan om niet-discrete waarden als index te gebruiken. In een taal als Perl kunnen bijvoorbeeld arrays van pointers naar hashes, associatieve arrays, worden gemaakt. De waarden hoeven ook in veel talen met associatieve arrays niet van hetzelfde type te zijn. Voorbeelden van talen met associatieve arrays zijn PHP, Perl en JavaScript.

Associatieve arrays worden over het algemeen geïmplementeerd met behulp van hashtabellen en zijn in de praktijk altijd dynamisch.

Arrayondersteuning in enkele talen

Een lijstje van arrayondersteuning in enkele talen:

C: alleen pure, homogene, niet-dynamische arrays ― Deze zijn noodzakelijk geïmplementeerd als een opeenvolgend blok geheugen omdat er in C een een-op-eenverband tussen arrays en pointerbewerkingen is.
Pascal: alleen pure, homogene, niet-dynamische arrays ― Deze zijn in tegenstelling tot bij C niet met behulp van pointers te bewerken.
Perl, Python, Ruby: Zowel pure, heterogene, dynamische arrays, of lists als associatieve arrays, of hashes.
C++ en Java: Pure, homogene, niet-dynamische arrays ― C++ biedt ondersteuning voor dynamische en associatieve arrays via de STL en Java via de standaard library. Het is verder in beide talen mogelijk om met behulp van containers heterogene arrays na te bootsen.
JavaScript, Lua en PHP: alleen associatieve arrays ― Deze associatieve arrays kunnen echter ook als gewone arrays worden gebruikt.
Haskell: Pure en associatieve arrays zijn deel van de standaard library.
Niet-pure functionele talen zoals Ocaml: pure, homogene, dynamische arrays en associatieve arrays

Literatuur

DA Watt. Programming Language Design Concepts, 2004. ISBN 0470853204
ML Scott. Programming Language Pragmatics, 2006, ISBN 0126339511
Stubbs en Webre. Data Structures with Abstract Data Types and Modula-2, 1987. ISBN 0534073026

Zie de categorie Array data structure van Wikimedia Commons voor mediabestanden over dit onderwerp.