Was ist ein Array?

Eine Wetter-App, die die Temperaturen der Woche anzeigt, braucht sieben Zahlen. Sie könnte sieben einzelne Variablen verwenden, monday, tuesday und so weiter, aber dann könnte keine Schleife sie durchlaufen, und ein achter Tag hieße neuen Code schreiben. Ein Array legt alle sieben Zahlen unter einem Namen ab, temperatures, in nummerierten Plätzen von 0 bis 6.

Wie ein Array funktioniert

Ein Array hält seine Elemente nebeneinander in einem einzigen Speicherblock, und jedes Element belegt gleich viele Bytes. Durch diese Anordnung findet der Computer jedes Element mit einer einzigen Rechnung:

address of element i = start address + i × element size

Angenommen, ein Array aus 32-Bit-Ganzzahlen (je 4 Bytes) beginnt an der Speicheradresse 1000. Element 0 liegt bei 1000, Element 1 bei 1004, Element 2 bei 1008 und Element 3 bei 1012. Element 3 oder Element 3.000.000 zu erreichen, kostet denselben einzelnen Schritt. Deshalb nennt man das Lesen eines Arrays über den Index konstante Zeit, geschrieben O(1).

Pythons Modul array speichert rohe Zahlen genau so, also kannst du die Rechnung überprüfen:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

Diese Formel erklärt auch, warum die meisten Sprachen bei 0 zu zählen beginnen. Der Index ist ein Versatz (Offset): wie viele Elemente vom Anfang aus zu überspringen sind. Das erste Element ist 0 Elemente vom Anfang entfernt, also ist sein Index 0, und das letzte Element eines Arrays der Länge n hat den Index n − 1. Einige Sprachen, etwa Lua, MATLAB, R und Fortran, beginnen stattdessen bei 1.

Ein Array in Python verwenden

Der meiste Python-Code verwendet die eingebaute list als Array. Du legst sie mit eckigen Klammern an, liest und änderst Elemente über den Index und fragst ihre Länge mit len() ab:

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

Ein negativer Index zählt vom Ende, also ist temperatures[-1] das letzte Element. Diese Abkürzung gibt es nur in Python; C und Java kennen keine negativen Indizes.

Was Array-Operationen kosten

Die zusammenhängende Anordnung macht manche Operationen schnell und andere langsam. Die Kosten wachsen mit n, der Anzahl der Elemente:

Einfügen am Anfang ist langsam, weil jedes Element einen Platz weiterrücken muss, um Platz zu schaffen. Ein unsortiertes Array zu durchsuchen bedeutet eine lineare Suche, die jedes Element der Reihe nach prüft, während ein sortiertes Array eine binäre Suche erlaubt, die den verbleibenden Bereich bei jedem Schritt halbiert.

Ein Array durchlaufen

Arrays und Schleifen gehören zusammen: Eine Schleife besucht jedes Element der Reihe nach, was man Iteration nennt. Dieselben paar Zeilen bewältigen ein Array mit 5 Elementen oder mit 5 Millionen.

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Arrays in anderen Sprachen

In C hat ein Array eine feste Größe, die bei der Deklaration festgelegt wird, und es enthält rohe Werte eines einzigen Typs. sizeof gibt seine Größe in Bytes an:

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Auch Java-Arrays haben eine feste Länge, und neue Elemente starten mit einem Standardwert, etwa 0 bei Zahlen. Brauchst du in Java ein Array, das wächst, verwendest du ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

JavaScript-Arrays wachsen und schrumpfen frei und können Typen mischen, etwa [1, "two", true].

Arrays, die wachsen, wie Pythons list, Javas ArrayList und C++' std::vector, heißen dynamische Arrays. Sie reservieren am Ende zusätzlichen Platz. Ist dieser Platz aufgebraucht, belegen sie einen größeren Block, kopieren jedes Element hinein und machen weiter. Die Kopiervorgänge sind selten genug, dass das Anhängen im Durchschnitt schnell bleibt.

Ein Array kann auch andere Arrays enthalten. grid[row][col] liest eine Zelle eines zweidimensionalen Arrays, die Anordnung, die man für Spielbretter, Tabellen und Bilder verwendet. Die C-Anleitung zu mehrdimensionalen Arrays zeigt, wie sie im Speicher liegen.

Typische Fehler

Um eins daneben (off by one). Ein Array mit 3 Elementen hat die Indizes 0, 1 und 2, also liegt Index 3 hinter dem Ende. Python bricht mit einem Fehler ab:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java wirft eine ArrayIndexOutOfBoundsException, und JavaScript gibt stillschweigend undefined zurück. C prüft gar nichts: Über das Ende hinaus zu lesen ist undefiniertes Verhalten, das Datenmüll liefern oder das Programm mit einem Segmentation Fault abstürzen lassen kann.

Kopieren durch Zuweisung. In Python, Java und JavaScript kopiert b = a kein Array; beide Namen verweisen auf dasselbe, also ändert eine Änderung an b auch a. Für eine echte Kopie verwende a.copy() in Python oder [...a] in JavaScript. Die Seite zur Variablen erklärt, warum.

Wie es weitergeht

Ein Array ist nur mit einer Schleife nützlich, die es durchläuft, also lies als Nächstes, was Iteration ist, und was ein Byte ist, für die Einheit hinter den Elementgrößen oben. Die Anleitung zu Python-Listen behandelt Slicing, Sortieren und Listenmethoden, und die Visualisierung der verketteten Liste zeigt die Struktur, die schnellen Indexzugriff gegen schnelles Einfügen tauscht.