Was ist der Unterschied zwischen einem Array und einer Liste?

Das Array hat eine feste Größe, die bei der Erstellung festgelegt wird. Die Liste passt ihre Größe dynamisch an, wenn Elemente hinzugefügt oder entfernt werden.

Der Zugriff auf Array-Elemente erfolgt nach Index in O(1). Der Zugriff auf Listenelemente kann variieren, z.B. hat eine einfach verkettete Liste einen Indexzugriff in O(n), während ArrayList im Durchschnitt in O(1) ist.

In einem Array werden die Elemente in zusammenhängenden Speicherbereichen gespeichert, was eine bessere Cache-Leistung gewährleistet. In einer Liste können die Elemente im Speicher verstreut sein, verbunden durch Zeiger.

Insert- und Delete-Operationen in der Mitte eines Arrays erfordern das Verschieben aller nachfolgenden Elemente, was teuer sein kann (O(n)). In Listen können diese Operationen effizienter sein (z.B. bei verketteten Listen O(1), wenn ein Zeiger auf das Element vorhanden ist, sonst O(n) für die Suche), aber sie erfordern die Aktualisierung der Zeiger.

Arrays können primitive Typen direkt speichern. Listen speichern in der Regel Referenzen auf Objekte (Wrapper für primitive Typen).

// Beispiel für Array
int[] array = new int[5];
array[0] = 10; // Zugriff O(1)

// Beispiel für ArrayList (Liste in Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Hinzufügen O(1) im Durchschnitt
list.get(0); // Zugriff O(1) im Durchschnitt

# Beispiel für Array (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Feste Größe

# Beispiel für Liste
daten_liste = [1, 2, 3]
daten_liste.append(4) # Dynamische Größe

daten_liste[0] # Zugriff O(1)

Vergleich:

Merkmal	Array	Liste
Größe	Feste Größe	Dynamisch
Zugriff nach Index	O(1)	Variiert (oft O(1) oder O(n))
Speicher	Kontinuierlich	Kann verstreut sein
Einfügen/Löschen	O(n) in der Mitte	Variiert (kann O(1) sein)
Datentypen	Primitive und Objekte	Normalerweise Referenzen auf Objekte