arrays-konzept

Arrays

Kurz: Eine Datenstruktur, die mehrere Werte desselben Typs in einem zusammenhängenden Speicherbereich mit fester Größe ablegt — Zugriff auf jedes Element erfolgt über seinen Index.

Genauer: Weil die Größe eines Arrays bei den meisten Sprachen von Anfang an feststehen muss, sind Arrays sehr schnell im Zugriff, aber unflexibel, wenn sich die Anzahl der Elemente zur Laufzeit ändern soll — dafür gibt es dynamisch wachsende Strukturen wie Java’s ArrayList (siehe Dynamisches Array). Mehrdimensionale Arrays erweitern das Prinzip auf Tabellen oder Gitter (Array von Arrays).

Im Detail

Der Grund für die feste Größe liegt in der Speicherorganisation: Ein Array reserviert von Anfang an einen zusammenhängenden Speicherblock, dessen Größe sich aus Elementanzahl × Elementgröße ergibt. Genau dieser zusammenhängende, vorhersagbare Aufbau ist der Grund, warum der Zugriff auf ein beliebiges Element per Index in konstanter Zeit möglich ist (O(1), siehe Algorithmen) — die Speicheradresse eines Elements lässt sich direkt berechnen, ohne die Struktur durchsuchen zu müssen.

zahlen = [10, 20, 30, 40, 50]
zahlen[2]        # 30 - direkter Zugriff, unabhängig von der Array-Größe
zahlen[2] = 99    # Element ändern ist ebenfalls O(1)

Diese Effizienz hat ihren Preis: Ein Element in der Mitte einzufügen oder zu löschen erfordert, alle nachfolgenden Elemente zu verschieben (O(n)) — und die Größe nachträglich zu ändern ist bei einem klassischen Array gar nicht vorgesehen. Genau deshalb bauen fast alle Sprachen darüber eine komfortablere, dynamisch wachsende Struktur (ArrayList in Java, list in Python, Array/dynamisches Array in JavaScript), die intern ein Array verwaltet und bei Bedarf automatisch ein größeres neues Array anlegt und die Daten umkopiert — sichtbar für den Nutzer als “unbegrenzt wachsende Liste”. Mehr dazu unter Dynamisches Array.

Ein weiterer wichtiger Punkt: Alle Elemente eines Arrays müssen denselben Datentyp haben (in typisierten Sprachen wird das vom Compiler erzwungen). Das ist kein Zufall, sondern notwendig, damit jedes Element exakt gleich viel Speicherplatz belegt — nur so lässt sich die Adresse von array[i] aus i direkt berechnen.

Mehrdimensionale Arrays (z. B. für Schachbretter, Bilddaten oder Matrizen) sind im Grunde nichts anderes als “Arrays von Arrays” — ein zweidimensionales Array ist ein Array, dessen einzelne Elemente selbst wieder Arrays sind.

Siehe auch: Index, Mehrdimensionale Arrays, Dynamisches Array, Datenstrukturen