Antwort.

Historie der Frage

Listen (list) sind einer der grundlegenden eingebauten Datentypen in Python seit den frühen Versionen der Sprache. Im Laufe der Zeit wurde ihre interne Struktur verbessert, um insbesondere die Leistung und die Benutzerfreundlichkeit zu erhöhen.

Problem

Es ist wichtig zu verstehen, dass Listen in Python nicht als verknüpfte, sondern als dynamische Arrays implementiert sind. Diese fehlerhafte Vorstellung führt zu ineffizientem Code oder falschen Berechnungen der Komplexität von Operationen.

Lösung

Listen werden als dynamische Arrays implementiert, die bei Bedarf "sprunghaft" (erweiternd) die Größe des zugewiesenen Speichers erhöhen, um ständige Kosten beim Hinzufügen von Elementen zu vermeiden. Dies ermöglicht das Einfügen und Löschen von Elementen am Ende der Liste in amortisierten O(1) Zeit. Das Einfügen oder Löschen in der Mitte/zu Beginn erfordert das Verschieben von Elementen, was O(n) Zeit in Anspruch nimmt.

Beispielcode:

my_list = [1, 2, 3]
my_list.append(4)      # Hinzufügen zum Ende
my_list.insert(1, 'a') # Einfügen an einem Index
print(my_list)

Hauptmerkmale:

Dynamische Größenänderung ohne explizite Zuweisung/Freigabe von Speicher durch den Benutzer.
Einfügen und Löschen am Ende ist schnell, am Anfang/Mitte ist langsam.
Eine Liste kann Elemente beliebigen Typs enthalten (Heterogenität).

Trickfragen.

Kann man list in Python als Analogon zu Arrays in C betrachten? Wo liegt der Unterschied?

Nein, ein Array in C enthält Elemente eines festen Typs, die aufeinanderfolgend im Speicher angeordnet sind. Eine Python-Liste ist ein Array von Zeigern auf Objekte, von denen jedes auf ein eigenständiges Objekt beliebigen Typs im Heap verweist.

Was passiert, wenn man in einer Schleife Elemente am Anfang der Liste einfügt? Ist das schnell?

Nein, das ist langsam: Beim Einfügen am Anfang (Position 0) werden jedes Mal alle bestehenden Elemente nach rechts verschoben. Die amortisierte Komplexität beträgt O(n) pro Operation, was bei großen Listen zu Leistungseinbußen führt.

Was ist der Unterschied zwischen den Operatoren + und append/extend für Listen?

erstellt eine neue Liste, ohne die alten zu ändern. append fügt ein Element am Ende der ursprünglichen Liste hinzu. extend fügt alle Elemente aus einer anderen Sequenz zur Liste hinzu und verändert das Objekt selbst.

lst1 = [1, 2]
lst2 = [3, 4]
lst3 = lst1 + lst2     # lst3 ist eine neue Liste
lst1.append(lst2)      # lst1 wird [1, 2, [3, 4]]
lst1.extend(lst2)      # lst1 wird [1, 2, 3, 4], wenn lst1 nach der vorherigen Append nicht zurückgesetzt wurde

Typische Fehler und Anti-Pattern

Verwendung von list für häufiges Einfügen/Löschen am Anfang der Liste (besser collections.deque nutzen)
Falsche Erwartung, dass list wenig Speicher benötigt und "dichte" Daten wie C/Java-Arrays enthält
Zufälliges Einfügen von Listen in sich selbst (Append einer Liste in die Liste)

Beispiel aus dem Leben

Negativer Fall

In einem Projekt wurde eine Liste verwendet, um die ersten Elemente zu speichern und ständig zu löschen. Man bemerkte eine merkliche Verlangsamung bei großen Datenmengen.

Vorteile:

Einfacher Einstieg, viele eingebaute Methoden.

Nachteile:

Die Leistung verschlechterte sich, Gedächtnisprobleme bei großen Mengen.

Positiver Fall

Nach Identifizierung des Problems wurde die Liste durch collections.deque ersetzt, die für solche Operationen optimiert ist.