Geordnete Sammlungen mit Index-Zugriff. Statisches Array (fixe Größe) vs dynamische Liste (ArrayList, list). Welche Operationen sind O(1), welche O(n)? Klausurwichtige Datenstruktur Nummer 1.
Ein statisches Array ist eine geordnete Sammlung von Elementen mit fester Größe, die beim Anlegen festgelegt wird. Du kannst Werte lesen und überschreiben, aber keine Elemente hinzufügen oder löschen. In Java die klassische int[]-Notation, in Python eher selten (dort sind Listen meist dynamisch).
Was du in der Klausur können musst:
arr[i] in O(1), null-basiert (erstes Element ist arr[0])arr.length in Java, len(arr) in Pythonint[] arr = new int[5]; legt 5 Felder an, alle mit 0int[][] matrix für 2D, Zugriff via matrix[i][j]In Klausuren ist die häufigste Falle: ArrayIndexOutOfBoundsException beim Zugriff auf arr[arr.length]. Plus die Frage welche Komplexität hat ein Array-Durchlauf? (O(n) für eine for-Schleife über alle Elemente).
// Größe direkt beim Anlegen festlegen
int[] noten = new int[5]; // [0, 0, 0, 0, 0]
// Mit Werten initialisieren
int[] tage = {31, 28, 31, 30, 31};
// Zugriff per Index
int erste = tage[0]; // 31
tage[1] = 29; // Schaltjahr — set
int laenge = tage.length; // 5 — feste Länge| Operation | Java | Komplexität |
|---|---|---|
| get(i) — Element an Position lesen | arr[i] | O(1) |
| set(i, x) — Element an Position überschreiben | arr[i] = x | O(1) |
| length — Größe abfragen | arr.length | O(1) |
Beide Hauptoperationen sind O(1): das Array kennt seinen Speicheradressen-Anfang, und Position liegt direkt Bytes weiter. Der Computer kann sofort dahin springen.
Wenn du diese Operationen brauchst, musst du auf eine dynamische Liste umsteigen. Mehr dazu im nächsten Tab.
Index-Zugriff und set in Aktion. Beide Operationen O(1), keine Größenänderung möglich.
Klausur-Trick: arr.length (Java) ist kein Methodenaufruf, sondern eine Eigenschaft. Daher ohne Klammern. Bei Strings und ArrayList sind es dagegen Methoden mit Klammern: s.length(), list.size().
Alle Tabs der Lerneinheit (Statisches Array · Dynamische Liste · Vergleich · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Du kannst Werte lesen und überschreiben, aber keine Elemente hinzufügen oder löschen. In Java die klassische -Notation, in Python eher selten (dort sind Listen meist dynamisch).
Wie speichert ein Programm Werte? Wie unterscheiden sich int, double, String und boolean?
if, else, else if. Wie trifft ein Programm Entscheidungen, und welche Vergleichsoperatoren brauchst du?
Funktionen, die sich selbst aufrufen. Mit Call-Stack-Visualisierung am Beispiel Fakultät.
int[]Was du in der Klausur können musst:
arr[i] in O(1), null-basiert (erstes Element ist arr[0])arr.length in Java, len(arr) in Pythonint[] arr = new int[5]; legt 5 Felder an, alle mit 0int[][] matrix für 2D, Zugriff via matrix[i][j]In Klausuren ist die häufigste Falle: ArrayIndexOutOfBoundsException beim Zugriff auf arr[arr.length]. Plus die Frage welche Komplexität hat ein Array-Durchlauf? (O(n) für eine for-Schleife über alle Elemente).
// Größe direkt beim Anlegen festlegen
int[] noten = new int[5]; // [0, 0, 0, 0, 0]
// Mit Werten initialisieren
int[] tage = {31, 28, 31, 30, 31};
// Zugriff per Index
int erste = tage[0]; // 31
tage[1] = 29; // Schaltjahr — set
int laenge = tage.length; // 5 — feste LängeJava int[]: Größe in eckigen Klammern beim Anlegen. tage.length ist read-only — Größe ist fix.
# Python hat keine echten statischen Arrays.
# Am nächsten kommt das array-Modul:
from array import array
zahlen = array('i', [1, 2, 3, 4, 5]) # 'i' = int
erste = zahlen[0] # 1
zahlen[1] = 99 # set
laenge = len(zahlen) # 5
# In der Praxis nutzt man fast immer list (siehe nächster Tab).Python: das array-Modul kommt am nächsten an statische Arrays heran. In der Praxis wird selten genutzt — list ist Standard.
| Operation | Java | Komplexität |
|---|---|---|
| get(i) — Element an Position lesen | arr[i] | O(1) |
| set(i, x) — Element an Position überschreiben | arr[i] = x | O(1) |
| length — Größe abfragen | arr.length | O(1) |
Beide Hauptoperationen sind O(1): das Array kennt seinen Speicheradressen-Anfang, und Position i liegt direkt i · Elementgröße Bytes weiter. Der Computer kann sofort dahin springen.
Wenn du diese Operationen brauchst, musst du auf eine dynamische Liste umsteigen. Mehr dazu im nächsten Tab.
Index-Zugriff und set in Aktion. Beide Operationen O(1), keine Größenänderung möglich.
Interaktive Visualisierung
Visualisiert statisches Array mit fester Größe, Index-Zugriff und Memory-Layout.
Klausur-Trick: arr.length (Java) ist kein Methodenaufruf, sondern eine Eigenschaft. Daher ohne Klammern. Bei Strings und ArrayList sind es dagegen Methoden mit Klammern: s.length(), list.size().
Eine dynamische Liste wächst und schrumpft automatisch. Du musst die Größe nicht vorher festlegen — das System reserviert intern Speicher und vergrößert/verkleinert ihn bei Bedarf.
In Java heißt sie ArrayList, in Python schlicht list. Beide funktionieren konzeptionell gleich.
Die meiste Zeit nimmst du in der Praxis dynamische Listen. Sie sind flexibel und schnell genug für fast alles.
import java.util.ArrayList;
ArrayList<Integer> noten = new ArrayList<>();
noten.add(15); // [15]
noten.add(12); // [15, 12]
noten.add(0, 8); // [8, 15, 12] — am Anfang einfügen
int erste = noten.get(0); // 8
noten.set(1, 16); // [8, 16, 12]
noten.remove(1); // [8, 12]
boolean hat = noten.contains(15); // false
int laenge = noten.size(); // 2Java ArrayList: typsicher mit Generics. Beachte: noten.get(i) statt noten[i]! Und size() mit Klammern, anders als length bei int[].
noten = []
noten.append(15) # [15]
noten.append(12) # [15, 12]
noten.insert(0, 8) # [8, 15, 12] — am Anfang einfügen
erste = noten[0] # 8
noten[1] = 16 # [8, 16, 12]
noten.pop(1) # [8, 12]
hat = 15 in noten # False
laenge = len(noten) # 2Python list: keine Type-Annotations nötig. Index-Zugriff direkt mit []. Sehr kompakt.
Das ist klausurwichtig: welche Operation ist O(1), welche O(n)?
| Operation | Java ArrayList | Python list | Komplexität |
|---|---|---|---|
| Zugriff per Index | list.get(i) | list[i] | O(1) |
| Am Ende anhängen | list.add(x) | list.append(x) | O(1) amortisiert |
| Vom Ende entfernen | list.remove(size-1) | list.pop() | O(1) |
// Klassische for-Schleife
for (int i = 0; i < noten.size(); i++) {
System.out.println(noten.get(i));
}
// For-Each (sauberer)
for (int note : noten) {
System.out.println(note);
}
// Mit Stream (modern)
noten.forEach(System.out::println);Drei gängige Wege. For-Each ist meist die sauberste Wahl, wenn du den Index nicht brauchst.
# Klassisch über Index
for i in range(len(noten)):
print(noten[i])
# Pythonisch: direkt iterieren
for note in noten:
print(note)
# Mit Index UND Wert
for i, note in enumerate(noten):
print(f"{i}: {note}")enumerate() ist das pythonische Pendant zur Java-for-i-Schleife wenn du beides brauchst.
Klick durch die Operationen und beobachte was passiert. Die Animation zeigt, welche Elemente bewegt werden bei jeder Operation.
Interaktive Visualisierung
Zeigt Array- und ArrayList-Operationen (push, pop, insert, remove) mit Index-Verschiebung.
Faustregel zum Mitnehmen: Am Ende ist billig, am Anfang ist teuer. Wer eine Liste oft vorne ergänzen muss, sollte eine andere Datenstruktur wählen (z.B. Deque oder LinkedList).
Beide Datenstrukturen speichern Werte mit Index-Zugriff. Der Unterschied liegt in der Größe: fest oder veränderbar.
| Statisches Array | Dynamische Liste | |
|---|---|---|
| Größe | fest (beim Anlegen) | wächst und schrumpft |
| Java | int[] | ArrayList<Integer> |
| Python | array.array (selten) | list |
| Index-Zugriff | O(1) | O(1) |
| Set an Position | O(1) | O(1) |
| Am Ende anfügen | nicht möglich | O(1) amortisiert |
| Am Anfang einfügen | nicht möglich | O(n) |
| Speicher | minimal, fest reserviert | etwas Overhead, dynamisch |
| Länge abfragen | arr.length (Property) | list.size() / len(list) |
| Anwendungsfall | Wähle |
|---|---|
| Größe ist vorher bekannt und fest (12 Monate, 7 Wochentage) | Statisches Array |
| Maximale Performance, minimaler Speicher | Statisches Array |
| 2D-Matrizen mit fixer Größe | Statisches 2D-Array |
| Du weißt vorher nicht wie viele Elemente | Dynamische Liste |
| Du musst oft anhängen/entfernen | Dynamische Liste |
| Standardfall in der Praxis | Dynamische Liste |
In 90% der praktischen Fälle nimmst du eine dynamische Liste. Statische Arrays nur wenn du explizit Performance/Speicher optimieren musst, oder wenn die Größe wirklich fest ist.
ArrayList ist intern selbst ein statisches Array — nur dass es bei Bedarf neu angelegt und kopiert wird:
ArrayList wird angelegt mit Capacity 10: [_,_,_,_,_,_,_,_,_,_] size=0
add(5): [5,_,_,_,_,_,_,_,_,_] size=1
add(8): [5,8,_,_,_,_,_,_,_,_] size=2
... (bis Capacity voll)
add(99) bei voller Capacity:
→ neues Array mit doppelter Capacity (20) anlegen
→ alle Werte kopieren (O(n))
→ 99 hinzufügen
Daher ist add() amortisiert O(1): die teure Kopier-Operation passiert nur alle log₂(n) Mal, gemittelt bleibt O(1) übrig.
Frage: Du musst eine Liste von 1000 Elementen 500-mal am Anfang ergänzen. Was ist der Gesamt-Aufwand?
Antwort: 500 × O(n) = 500 × 1000 = 500.000 Operationen. ArrayList ist dafür ungeeignet — eine LinkedList oder Deque wäre besser.
Klausurfragen mit Lösungen (8)
Antwort: Du kannst mit add(x) Elemente anhängen
Erklärung: int[] hat keine add-Methode — die Größe ist fix. Wenn du dynamisch wachsen willst, brauchst du ArrayList. Die anderen Aussagen stimmen.
Antwort: O(1)
Erklärung: Index-Zugriff ist O(1): das Array kann direkt zur Speicheradresse springen. Egal ob i=0 oder i=999, gleicher Aufwand. Das gilt für statische UND dynamische Arrays.
Antwort: 1.000.000
Erklärung: Beim Einfügen an Position 0 müssen alle 1.000.000 bestehenden Elemente eine Position nach rechts. Das ist O(n).
ArrayList<Integer> a = new ArrayList<>();
a.add(10); a.add(20); a.add(30);
a.add(1, 99);
System.out.println(a.get(2));Antwort: 20
Erklärung: Nach den drei add/append: [10, 20, 30]. Nach insert(1, 99): [10, 99, 20, 30]. a[2] ist 20.
Antwort: list.contains(x) / x in list
Erklärung: contains() bzw. der `in`-Operator macht eine lineare Suche durch alle n Elemente — O(n). Die anderen sind alle O(1) (size ist intern mitgezählt, get ist Index-Zugriff, add ans Ende ist amortisiert O(1)).
Antwort: Weil die Vergrößerung so selten passiert, dass amortisiert O(1) übrig bleibt
Erklärung: Wenn das Array voll ist, wird ein neues mit doppelter Größe angelegt und alle Elemente kopiert (O(n)). Aber das passiert nur alle log₂(n) Mal. Über alle Aufrufe gemittelt ergibt das O(1) amortisiert.
Antwort: Dynamische Liste (ArrayList / list)
Erklärung: Bei unbekannter Größe nimmst du eine dynamische Liste. Sie wächst automatisch. Statische Arrays nur wenn die Größe vorher feststeht.
Antwort: length ist eine Property (ohne Klammern), size() ist eine Methode (mit Klammern)
Erklärung: Klassischer Klausur-Trickfrage: arr.length ist eine Property (kein Klammern), list.size() ist eine Methode (mit Klammern). Verwechslung ist häufige Fehlerquelle in Klausuren.
Eine Klasse erbt von einer anderen: gemeinsamer Code wandert nach oben, Spezifisches bleibt unten. Override, super, dynamischer Dispatch — das Fundament für jede OOP-Architektur. Mit Tier-Hierarchie-Visualizer.
| Am Anfang einfügen |
list.add(0, x) |
list.insert(0, x) |
| O(n) |
| Vom Anfang entfernen | list.remove(0) | list.pop(0) | O(n) |
| An Position einfügen | list.add(i, x) | list.insert(i, x) | O(n) |
| An Position entfernen | list.remove(i) | list.pop(i) | O(n) |
| Linear suchen | list.contains(x) | x in list | O(n) |
| Länge | list.size() | len(list) | O(1) |
Warum sind Operationen am Anfang teuer?
Wenn du an Position 0 einfügst, müssen alle anderen Elemente um eine Position nach rechts wandern. Bei einer Million Elementen sind das eine Million Schreiboperationen.
Ans Ende anhängen ist meist O(1) — außer das Array muss intern vergrößert werden, dann ist es O(n) für diesen Schritt. Das passiert aber so selten, dass man von amortisiert O(1) spricht.