Hoe zijn arrays opgebouwd in programmeren?

Arrays zijn geordende collecties van elementen van hetzelfde type, opgeslagen in aangrenzende (sequentiële) geheugenlocaties.

Belangrijkste kenmerken:

• Indexering: Toegang tot elementen gebeurt via een index die begint bij 0. De index geeft de verschuiving vanaf het begin van de array aan.
• Grootte: De grootte van de array (aantal elementen) is vast bij creatie in statisch getypeerde talen of kan dynamisch veranderen in talen met dynamische typing (bijvoorbeeld in Swift Array).
• Gegevenstype: Alle elementen in de array moeten hetzelfde gegevenstype hebben.
• Aaneengeslotenheid: Het opslaan van elementen in aangrenzende geheugenlocaties zorgt voor snelle toegang tot elk element via de index.

Operaties:

• Toegang via index: O(1) - constante tijd.
• Toevoegen/verwijderen aan het einde: O(1) gemiddeld voor dynamische arrays (Swift Array).
• Toevoegen/verwijderen aan het begin of in het midden: O(n) - lineaire tijd, omdat het verschuiven van elementen nodig kan zijn.

Voorbeeld in Swift:

// Aanmaken van een array van strings
var names: [String] = ["Alice", "Bob", "Charlie"]

// Toegang tot een element via index
let first_name = names[0] // "Alice"

// Element toevoegen
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Element verwijderen
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iteratie over de array
for name in names {
    print(name)
}

Interne structuur (voor dynamische arrays van het type Swift Array):

Dynamische arrays worden meestal geïmplementeerd op een statisch toegewezen geheugenbuffer. Wanneer de capaciteit van de buffer wordt bereikt, wordt een nieuwe, grotere buffer toegewezen en worden de oude elementen gekopieerd (reallocatie). Dit zorgt voor een geamortiseerde O(1) complexiteit voor toevoegen aan het einde.