Dynamisches Array
Aus ProgrammingWiki
Dynamische Arrays bieten sowohl den Vorteil von Arrays, nämlich dass der Aufwand zum Zugriff $\mathcal{O}(1)$ beträgt, als auch den Vorteil von Linked Lists, dass die Länge der Liste variabel ist. Diese Datenstruktur wird beispielsweise in Java unter dem Namen ArrayList implementiert.
Inhaltsverzeichnis |
Grundlagen
Wird ein dynamisches Array initialisiert, so wird zunächst ein Array mit einer gewissen Länge angelegt. Man kann beispielsweise mit der Größe $1$ anfangen. Möchte man nun ein Element in das anfangs leere dynamische Array einfügen, so ist hierfür Platz. Aber danach ist das Array voll. Soll nun ein weiteres Element eingefügt werden, wird im Speicher ein neues Array eingerichtet. Die Elemente des "potenziell überfüllten" Arrays werden in das neue umgespeichert. Fügt man weitere Elemente an, so ist irgendwann auch das neue Array voll, so dass wiederum ein neues Array im Speicher angelegt wird usw. Jedes neue Array hat die doppelte Länge des vorherigen. Dieser Vorgang kann beliebig oft wiederholt werden.
Nun stellt sich die Frage, ob man auch beim Entfernen von Elementen die Länge durch Verwendung eines neuen Arrays anpassen sollte. Alternativ könnte man einfach das vorhandene Array weiterhin nutzen, der Platz ist ja ausreichend. Dies hätte allerdings zur Folge, dass man unnötig viel Platz im Speicher verbrauchen würde. Hat man beispielsweise sehr viele Elemente eingefügt und danach wieder die meisten entfernt, so sind nur noch sehr wenig Elemente im Array. Jedoch hat das Array dann im Speicher noch die volle Größe, die es jedoch nicht braucht.
Vorschlag: Immer wenn weniger als die Hälfte des Speicherplatzes des Arrays tatsächlich genutzt wird, geht man eine "Ausbaustufe" zurück und legt ein neues Array mit halber Länge an. Dies würde jedoch zu dem Problem führen, dass wenn man sich gerade an so einem Schwellenwert, also am Index $1, 2, 4, 8, 16, ... = 2^i$, befindet und im Wechsel Elemente hinzufügt und entfernt, ständig ein neues Array, mal mit doppelter und dann wieder mit ursprünglicher Länge, erstellt. Dies ist offensichtlich sehr ungünstig.
Besser ist es deshalb, noch eine weitere "Ausbaustufe" zurückzugehen und erst dann ein neues Array halber Länge anzulegen, wenn nur noch weniger als ein Viertel des Arrays genutzt wird. Dies führt dazu, dass man nach einer Verdopplungsoperation, auch bei folgenden Delete-Operationen, weit genug von einer erneuten Speicherallokation entfernt ist. Genau genommen ist man mindestens $\frac{m}{4}$ Operationen von der nächsten Operation mit Speicherallokation entfernt, wenn $m$ die Länge des alloziierten Arrays ist.
Komplexitätsanalyse
Access
Da es sich intern um Arrays handelt, kann man per Index auf das entsprechende Element zugreifen. Also beträgt der Aufwand je Zugriff $\mathcal{O}(1)$.
Insert
Da bei einer Insert-Operation mit Speicherallokation das komplette Array kopiert werden muss, beträgt die Komplexität im worst case $\mathcal{O}(n)$. Jedoch kann man mit Mitteln der amortisierten Analyse feststellen, dass man den Aufwand mit $\mathcal{O}(1)$ angeben kann, womit eine Insert-Operation in einem dynamischen Array im Wesentlichen nicht teurer ist als bei einer Linked List.
Delete
Hier verhält es sich ähnlich wie bei der Insert-Operation, im worst case ist der Aufwand $\mathcal{O}(n)$, jedoch kann man amortisiert $\mathcal{O}(1)$ angeben.
