Wie sind Arrays in der Programmierung aufgebaut?

Arrays sind geordnete Sammlungen von Elementen desselben Typs, die in zusammenhängenden (sequenziellen) Speicherzellen gespeichert werden.

Hauptmerkmale:

• Indexierung: Der Zugriff auf Elemente erfolgt über einen Index, der bei 0 beginnt. Der Index gibt die Verschiebung vom Anfang des Arrays an.
• Größe: Die Größe des Arrays (Anzahl der Elemente) ist bei der Erstellung in statisch typisierten Sprachen fest oder kann in dynamisch typisierten Sprachen (z.B. Swift Array) dynamisch geändert werden.
• Datentyp: Alle Elemente des Arrays müssen denselben Datentyp haben.
• Kontiguität: Das Speichern der Elemente in zusammenhängenden Speicherzellen gewährleistet einen schnellen Zugriff auf jedes Element über seinen Index.

Operationen:

• Zugriff nach Index: O(1) - konstante Zeit.
• Hinzufügen/Entfernen am Ende: O(1) im Durchschnitt für dynamische Arrays (Swift Array).
• Hinzufügen/Entfernen am Anfang oder in der Mitte: O(n) - lineare Zeit, da das Verschieben von Elementen erforderlich sein kann.

Beispiel in Swift:

// Erstellen eines Arrays von Strings
var names: [String] = ["Alice", "Bob", "Charlie"]

// Zugriff auf ein Element nach Index
let first_name = names[0] // "Alice"

// Element hinzufügen
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

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

// Iteration über das Array
for name in names {
    print(name)
}

Innere Struktur (für dynamische Arrays vom Typ Swift Array):

Dynamische Arrays werden in der Regel auf einem statisch zugewiesenen Speicherpuffer implementiert. Wenn die Kapazität des Puffers erreicht ist, wird ein neuer, größerer Puffer zugewiesen und die alten Elemente werden kopiert (Reallokation). Dies gewährleistet eine amortisierte O(1)-Komplexität für das Hinzufügen am Ende.