Wie speichern Arrays Daten und warum sind sie so schnell?
Arrays: Feste Speicherplätze für bekannte Datenmengen
Stell dir vor, du entwickelst eine Wetter-App und musst die Höchsttemperaturen für die sieben Tage einer Woche speichern. Da die Anzahl der Tage im Voraus exakt bekannt ist, ist ein Array (Datenfeld) die perfekte Datenstruktur für dieses Problem.
// Ein Array für exakt 7 Ganzzahlen wird deklariert
int[] temperaturen = new int[7];
// Werte werden über den Index zugewiesen
temperaturen[0] = 23; // Montag (Index 0)
temperaturen[1] = 25; // Dienstag (Index 1)
temperaturen[2] = 22; // Mittwoch (Index 2)Ein Array ist eine fundamentale Datenstruktur, die zwei strenge Regeln befolgt:
- Gleicher Datentyp: Alle Elemente innerhalb des Arrays müssen vom selben Datentyp sein (in diesem Beispiel
int). Du kennst primitive Datentypen bereits aus deinem Vorwissen. - Feste Größe: Die maximale Anzahl der Elemente wird bei der Erstellung unwiderruflich festgelegt. Das Array kann danach weder wachsen noch schrumpfen.
Der direkte Zugriff auf ein einzelnes Element erfolgt über seinen Index, der in den meisten modernen Programmiersprachen bei 0 beginnt.
Speicherorganisation und konstante Zugriffszeit
Warum sind Arrays beim Auslesen und Schreiben von Daten so extrem schnell? Die Antwort liegt in der Interaktion mit dem Arbeitsspeicher (RAM). Das System reserviert für ein Array einen zusammenhängenden Speicherbereich. Die Elemente liegen physisch direkt Block an Block hintereinander, wie Perlen an einer Kette.
Wenn du auf temperaturen[2] zugreifst, muss der Computer die Datenstruktur nicht durchsuchen. Er berechnet die exakte Speicheradresse mathematisch: Startadresse des Arrays + (Index * Größe eines Elements in Bytes).
Da du die Big-O-Notation bereits kennst, weißt du, was das bedeutet: Diese mathematische Berechnung dauert immer exakt gleich lang – unabhängig davon, ob das Array 10 oder 10 Millionen Elemente umfasst. Der direkte Zugriff per Index besitzt daher eine konstante Zeitkomplexität von O(1). Arrays sind unschlagbar performant, wenn du wahlfreien Zugriff auf eine im Vorfeld bekannte Datenmenge benötigst.
Warum nutzen wir Listen für flexible Datenmengen?
Listen: Dynamische Sammlungen für variable Anforderungen
Stell dir nun vor, du programmierst das Anmeldesystem für einen Workshop. Du weißt vorher nicht, ob sich 5 oder 50 Personen anmelden werden. Ein Array mit fester Größe wäre hier unpraktisch, da du entweder zu wenig Platz hast oder unnötig Speicher blockierst. Hier kommen Listen zum Einsatz.
# Eine leere, dynamische Liste wird erstellt
teilnehmende = []
# Elemente können zur Laufzeit beliebig hinzugefügt werden
teilnehmende.append("Anna Schmidt")
teilnehmende.append("Max Mustermann")
# Der Zugriff erfolgt weiterhin über den Index
print(f"Erste Person: {teilnehmende[0]}")Eine Liste (z. B. list in Python oder List<T> in C#) speichert ebenfalls eine geordnete Sammlung von Elementen. Du kannst die Daten sequenziell (nacheinander in einer Schleife) durchlaufen oder direkt über den Index zugreifen. Der entscheidende Unterschied zum Array: Ihre Größe ist dynamisch. Du kannst zur Laufzeit beliebig viele Elemente hinzufügen oder entfernen.
Interne Funktionsweise: Der Preis der Flexibilität
Diese Flexibilität hat jedoch einen technischen Preis. In vielen Programmiersprachen basieren Listen intern auf Arrays. Wenn das interne Array voll ist und du ein weiteres Element hinzufügst, führt die Liste im Hintergrund ein sogenanntes Resizing (Größenanpassung) durch:
- Es wird ein neues, größeres Array im Speicher angelegt (oft mit der doppelten Kapazität).
- Alle bestehenden Elemente werden aus dem alten in das neue Array kopiert.
- Das alte Array wird aus dem Speicher gelöscht.
Dieser Kopiervorgang kostet Rechenzeit. Zudem ist das Einfügen oder Löschen von Elementen am Anfang oder in der Mitte einer Liste aufwendig: Alle nachfolgenden Elemente müssen im Speicher verschoben werden, was eine Zeitkomplexität von O(n) bedeutet.
Der direkte Vergleich:
- Arrays bieten maximale Performance und Speichereffizienz bei statischen, bekannten Größen.
- Listen bieten maximalen Komfort und Flexibilität bei unbekannten oder schwankenden Datenmengen, nehmen dafür aber gelegentliche Performance-Einbrüche beim Vergrößern des internen Speichers oder beim Verschieben von Elementen in Kauf.
Teste dein Wissen
Du hast ein Array für 5 Highscores erstellt. Nun soll ein sechster Score hinzugefügt werden. Was passiert laut den Regeln für Arrays?