dynamisches-array

ArrayList (Dynamisches Array)

Kurz: Eine Liste, die intern auf einem Array basiert, das automatisch wächst (und typischerweise nie automatisch schrumpft), sobald mehr Platz gebraucht wird als aktuell verfügbar ist.

Genauer: Ist das interne Array voll, wird beim nächsten Einfügen automatisch ein größeres neues Array angelegt und der bisherige Inhalt hinüberkopiert — für den Nutzer der Liste unsichtbar. Dadurch bleibt der schnelle Indexzugriff eines Arrays erhalten, während die Größe nicht mehr im Voraus feststehen muss wie bei einem klassischen Array. Häufiges Einfügen in der Mitte der Liste bleibt dabei trotzdem langsamer als bei einer verketteten Liste.

Im Detail

Der Trick hinter einem dynamischen Array liegt in der Wachstumsstrategie: Wird das interne Array voll, verdoppelt (oder erhöht um einen ähnlichen Faktor) die Implementierung typischerweise die Kapazität, statt nur um genau ein Element zu wachsen:

Kapazität 4, voll -> neues Array mit Kapazität 8 anlegen, alle 4 Elemente umkopieren
Kapazität 8, voll -> neues Array mit Kapazität 16 anlegen, alle 8 Elemente umkopieren

Das mag verschwenderisch wirken (oft ist mehr Platz reserviert als aktuell gebraucht), ist aber der Grund, warum Einfügen am Ende im Durchschnitt trotzdem sehr schnell bleibt: Ein einzelnes Umkopieren ist zwar teuer (O(n)), passiert aber immer seltener, je größer die Liste wird — die Kosten verteilen sich über viele einzelne Einfüge-Operationen (“amortisierte Komplexität”), sodass das Einfügen am Ende im Mittel trotzdem O(1) kostet, obwohl gelegentlich ein teures Umkopieren dazwischenkommt.

zahlen = []          # Liste startet leer bzw. mit kleiner interner Kapazität
zahlen.append(1)     # praktisch immer O(1) - gelegentlich löst das ein internes Umkopieren aus

Der Unterschied zwischen “Größe” (Anzahl tatsächlich enthaltener Elemente) und “Kapazität” (Größe des intern reservierten Arrays) ist wichtig für das Verständnis, warum ein dynamisches Array manchmal mehr Speicher belegt, als für die aktuellen Elemente nötig wäre. Manche Implementierungen bieten deshalb eine explizite Methode an, um überschüssige Kapazität wieder freizugeben, wenn ein Programm weiß, dass die Liste nicht mehr wachsen wird.

Wichtig bleibt die Einschränkung aus dem zugrundeliegenden Array: Einfügen oder Löschen in der MITTE der Liste (nicht am Ende) erfordert weiterhin, alle nachfolgenden Elemente zu verschieben — das bleibt O(n), unabhängig von der cleveren Wachstumsstrategie. Wer hauptsächlich in der Mitte einfügt/löscht, ist mit einer verketteten Liste besser bedient.

Siehe auch: Arrays, List, LinkedList