Page 3 : 28

Forelæsningsnoter i Objekt-orienteret Programmering Arrays og Lister * Arrays Introduktion til arrays Karakteristik af arrays Arrays i Java Eksempler på arrays i Java Direkte notation for array objekter i Java Flerdimensionelle arrays i Java Fleksible arrays i Java: Vectorer Eksempler på brug af Vector i Java * Associative arrays Associative arrays * Lister Introduktion til lister Enkeltkædede lister Indsættelse af et element i en kædet liste Sletning af et element fra en kædet liste Identitet af lister: Listen som objekt. Indsættelse og sletning af første element i en liste uden identitet Java programeksempler Dobbeltkædede lister Cirkulære lister Associationslister * Gennemløb af arrays og lister Iteratorbegrebet Enumerations i Java * Organisering af Liste klasserne med indlejring Indlejring af Linkable i LinkedList Indlejring af Linkable mv. i LinkedList

Karakteristik af arrays

På denne side karakteriserer vi mere omhyggeligt det klassiske arraybegreb.

Vi opfatter et array som en abstrakt datatype, der repræsenterer en homogen tabel At array'et er homogent betyder at alle elementer har samme type

Et array er en tabel, hvor alle elementer er af samme type. Homogenitetsegenskaben af arrays er relativ til programmeringssprogets regler for typesammenlignelighed. Homogenitetsegenskaben kan også ses som en kontrast til records, hvori felterne jo kan være af forskellige typer.

Vigtige array-operationer: hent det i-te element gem et nyt objekt i i-te element

Hent og gem operationerne er effektive, med konstant tidskompleksitet Opslag i et array sker direkte, uden nogen form for søgning eller gennemløb

Konstant tidskompleksitet af hent og gem operationerne betyder at uanset hvor stor array'et er tager det samme tid at hente eller gemme et element i tabellen, uanset hvilken plads (første, sidste, midterste osv.) i arrayet vi arbejder på

Et array kan have én eller flere dimensioner

Hvis man ønsker det kan man tænke på 'almindelige data' som 0-dimensionelle arrays. Éndimensionelle arrays er det mest almindelige. Flerdimensionale arrays kan opfattes som éndimensionalle arrays, hvor elementtypen er en arraytype (af dimension én mindre end den oprindelige arraytype)

Et array har faste øvre og nedre grænser, og dermed en fast størrelse

Kravet om fast størrelse af arrays kan forstås på flere måder: Det er statisk bestemmeligt, hvor stort et array skal være. Dvs. at inden programmet kører kan man bestemme, hvor grænserne for programmets arrays. Det er dynamisk bestemmeligt, hvor stort et array skal være. Størrelsen kan f.eks. afhænge af bruger-input. Men når et array først er allokeret, kan det ikke ændre størrelse. Det første alternativ afspejler det klassiske array begreb. Ved statisk at låse indeks intervallet af et array fast kan man generere den mest effektive kode for tilgang til array'et elementer. Det andet alternativ er mere fleksibel, idet størrelsen af et array kan gøres afhængig af andre data i programmet. Endelig er der variationer af array begrebet, som tillader at udvide indeksintervallet af et array på køretidspunktet. Ifølge vores karakteristik er en sådan datatype strengt taget ikke et array. Java's Vector begreb (som behandles nedenfor) er et eksempel på et dynamisk udvideligt 'array'.

Underliggende lagres elementerne i et array konsekutivt Konsekutiv lagring indebærer at elementerne placeres i umiddelbar forlængelse af hinanden i maskinens arbejdslager

Et array kan implementeres som en konsekutiv mængde af lagerceller, hvor positionen af et element i array'et kan beregnes ud fra indekset. Det befordrer den konstante tidskompleksitet af de to fundamentale operationer: hent og gem på arrays. Med andre ord: hent og gem operationerne beregner positionen af et element i arrayet, og henter/gemmer dette element direkte, uden nogen som helst form for søgning eller gennemløb af arrayet. Det er vigtigt at slå fast, at denne garanterede effektivitet af de basale operationer på et array er et væsentlig karakteristika ved selve array ideen.