Array vs. Linked List
23. Mai 2022Arrays und verkettete Listen (Linked Lists) sind Datenstrukturen, die Elemente eines bestimmten Typs sequentiell anordnen.
Allerdings gibt es große Unterschiede, und abhängig von den Anforderungen hat die Auswahl der Datenstruktur einen erheblichen Einfluss auf den Speicherbedarf und die Performance der Anwendung.
Dieser Artikel beantwortet die folgenden Fragen:
- Was sind die Unterschiede zwischen Array und Linked List?
- Was sie die Vor- und Nachteile der jeweils einen Datenstruktur gegenüber der anderen?
- Welche Zeitkomplexität haben die verschiedenen Operationen (wie Zugriff auf ein Element, Einfügen, Entfernen, Bestimmen der Größe)?
- Wann solltest du welche Datenstruktur verwenden?
Beginnen wir mit einem Vergleich beider Datenstrukturen...
Unterschied zwischen Array und Linked List
Die folgende Grafik zeigt den grundsätzlichen Aufbau beider Datenstrukturen, wobei ich die verkettete Liste sowohl als einfach als auch als doppelt verkettete Liste dargestellt habe:
Ein Array ist ein zusammenhängender Speicherblock, der die Datenelemente¹ direkt enthält.
Eine verkettete Liste besteht aus Listenknoten, die jeweils ein Datenelement¹ enthalten sowie eine Referenz auf den nächsten Knoten (und – bei einer doppelt verketteten Liste – auf den vorherigen Knoten).
Die folgenden Abschnitte vergleichen die Konsequenzen, die sich aus dem Aufbau der beiden Datenstrukturen ergeben, in Bezug auf den Aufwand beim Einfügen und Entfernen von Elementen, den benötigten Speicherplatz und den Lokalitätseffekt (was das bedeutet, erkläre ich im entsprechenden Abschnitt).
¹ Ein Datenelement kann ein primitives Element sein, z. B. ein int, double oder char, oder eine Referenz auf ein Objekt.
Array vs. Linked List: Zeitkomplexität
Beginnen wir mit dem Aufwand für die verschiedenen Operationen.
(Eine Einführung in das Thema Zeitkomplexität findest du im Artikel "O-Notation und Zeitkomplexität – anschaulich erklärt".)
Zugriff auf ein bestimmtes Element ("Random Access")
Bei einem Array können wir jedes Element direkt adressieren. Es macht vom Aufwand her keinen Unterschied, wie lang das Array ist oder an welcher Position wir ein Element lesen oder schreiben.
Im Array-Beispiel macht es keinen Unterschied, ob wir auf das "a" oder das "p" zugreifen:
Der Aufwand ist also konstant. Die Zeitkomplexität für den (schreibenden oder lesenden) Zugriff auf ein bestimmtes Elements eines Array beträgt somit: O(1)
Bei einer verketteten Liste hingegen können wir nur auf das erste Element direkt zugreifen. Für alle anderen müssen wir der Liste Knoten für Knoten folgen, bis wir das gewünschte Element erreicht haben.
Im Linked-List-Beispiel benötigen wir mehr Schritte, um das "p" zu erreichen als um das "a" zu erreichen:
Bei einem zufällig verteilten Zugriff auf die Elemente ist der mittlere Aufwand proportional zur Länge der Liste. Die Zeitkomplexität beträgt also: O(n)
Hinzufügen oder Entfernen eines Elements
Bei einer Linked List können wir an jeder beliebigen Stelle Knoten einfügen und entfernen. Der Aufwand dafür ist immer gleich, unabhängig davon, wie lang die Liste ist und an welcher Position wir einfügen (vorausgesetzt, wir haben eine Referenz auf den Knoten, an dem wir einfügen/entfernen wollen).
Die Zeitkomplexität für das Einfügen in und Entfernen aus einer verketteten Liste lautet also: O(1)
Ein Array kann seine Größe nicht ändern. Um ein Element einzufügen oder zu entfernen müssen wir das Array immer in ein neues, größeres oder kleineres Array umkopieren:
Der Aufwand dafür ist proportional zur Länge des Arrays. Die Zeitkomplexität lautet somit: O(n)
Datenstrukturen wie z. B. Javas ArrayList haben eine Strategie zur Verringerung der durchschnittlichen Zeitkomplexität beim Einfügen und Entfernen von Elementen: Indem sie im Array Platz für neue Elemente reservieren, sowohl beim Anlegen als auch beim Vergrößern, können sie die Zeitkomplexität – zumindest für das Einfügen und Entfernen am Ende einer Array-basierten Datenstruktur – auf O(1) reduzieren.
Mit einem Ringbuffer (englisch: "circular array") können wir auch die Zeitkomplexität für das Einfügen und Entfernen am Anfang einer array-basierten Datenstruktur auf O(1) reduzieren. So wird z. B. das Java ArrayDeque realisiert.
Größenbestimmung
Die Größe eines Arrays ist bekannt und kann z. B. in Java über array.length abgefragt werden. Der Aufwand dafür ist unabhängig von der Länge des Arrays, also konstant.
Die Zeitkomplexität für die Bestimmung der Länge eines Arrays lautet somit: O(1)
Bei einer verketteten Liste hingegeben müssen wir die gesamte Liste ablaufen und die Listenknoten zählen. Je länger die Liste, desto länger dauert das Zählen.
Die Zeitkomplexität für die Bestimmung der Länge einer Linked List lautet somit: O(n)
Einige auf verketteten Listen basierende Datenstrukturen (z. B. die Java LinkedList) speichern die Größe zusätzlich in einem Feld ab, das sie beim Einfügen und Entfernen aktualisieren – so kann auch die Größe solcher Datenstrukturen mit konstantem Aufwand, also O(1), abgefragt werden.
Übersicht Zeitkomplexität
Die folgende Tabelle fasst die Zeitkomplexitäten der verschiedenen Operationen zusammen:
| Operation | Array | Linked List |
|---|---|---|
| Zugriff auf das n-te Element: | O(1) | O(n) |
| Einfügen eines Elements: | O(n) | O(1) |
| Entfernen eines Elements: | O(n) | O(1) |
| Bestimmung der Länge: | O(1) | O(n) |
Der Zugriff auf ein Element (lesend oder schreibend) und die Längenbestimmung sind also bei einem Array günstiger – Einfügen und Entfernen hingegen bei einer Linked List.
Array vs. Linked List: Speicherverbrauch
Bei einem Array benötigt jedes Feld so viel Speicherplatz wie der darin enthaltene Datentyp. Ein Array mit int-Primitiven beispielsweise benötigt 4 Byte pro Eintrag:
Bei einer verketteten Liste hingegen müssen für jeden Knoten sowohl das Datenelement als auch Referenzen auf Nachfolger- und ggf. Vorgängerknoten gespeichert werden.
Bleiben wir bei den int-Primitiven und gehen wir von 4 Byte¹ pro Referenz aus, dann kommen wir bei einer einfach verketteten Liste auf 8 Byte pro Element.
Bei JVM-Sprachen kommen allerdings pro Knoten noch 12 Byte für den Header des Knotenobjekts hinzu – sowie 4 Füllbytes, da Objekte ein Vielfaches von 8 Bytes an Speicher belegen müssen.¹ Insgesamt benötigen wir also 24 Byte pro Listenknoten.
Bei einer doppelt verketteten Liste benötigen wir eine weitere Referenz, wir kommen also auf 12 Byte pro Eintrag.
Bei JVM-basierten Sprachen kommen die 12 Byte für den Objekt-Header hinzu. Insgesamt bleibt es aber bei 24 Byte, da die zusätzlichen vier Bytes den Platz einnehmen, den vorher die Füllbytes belegt haben.
Die folgende Tabelle zeigt den Speicherbedarf pro Feld für ein Array und eine Linked List – jeweils für C/C++ und JVM-basierte Sprachen:
| Sprache | Array | Einfach verkettete Liste | Doppelt verkettete Liste |
|---|---|---|---|
| C/C++: | 4 Bytes | 8 Bytes | 12 Bytes |
| JVM-Sprache: | 4 Bytes | 24 Bytes¹ | 24 Bytes¹ |
Bis hierhin spricht der Speicherverbrauch für das Array – ganz besonders in Java.
(¹ Ich gehe bei den Speicherbetrachtungen von einer 64-Bit-JVM mit aktivierten Compressed Class Pointers und aktivierten Compressed Oops aus.)
Speichereffizienz
So eindeutig fällt der Vergleich allerdings nur aus, wenn wir die Größe der Datenstruktur vorab kennen und sie sich nicht ändert.
Bei einer Array-basierten Datenstruktur, deren Größe sich ändern kann, z. B. der Java ArrayList, wird – wie oben erwähnt – meist eine Reserve für neue Elemente freigehalten. Bei einer verketteten Liste hingegen wird erst dann, wenn ein Element eingefügt wird, der Speicher für dieses Element – und nur für dieses Element – allokiert.
Analoges gilt für das Entfernen von Elementen. Bei einer Array-basierten Datenstruktur wird das Feld in der Regel für zukünftige Einfügeoperationen freigelassen. Bei einer Linked List wird es sofort gelöscht (bzw. für das Löschen durch den Garbage Collector freigegeben).
Linked Lists sind also speichereffizienter als Arrays.
Zusammengefasst: bei gleicher Länge benötigt eine Linked List mindestens doppelt so viel Speicherplatz wie ein Array – in Java sogar das Sechsfache! Bei variierender Länge kann eine Array-basierte Datenstruktur jedoch ungenutzten Speicherplatz blockieren, so dass diese beiden Faktoren gegeneinander abgewägt werden müssen.
Array vs. Linked List: Lokalitätseffekt
Um die Frage "Was ist schneller – ein Array oder eine Linked List?" zu beantworten, müssen wir noch einen weiteren Faktor berücksichtigen: den Lokalitätseffekt.
Da der Speicher für ein Array am Stück allokiert wird, liegen dessen Elemente an aufeinanderfolgenden Speicheradressen. Beim Zugriff auf den Hauptspeicher werden alle Array-Elemente, die auf derselben Memory Page liegen, gleichzeitig in den CPU-Cache geladen. Sobald wir auf ein Array-Element zugegriffen haben, können wir also sehr schnell auf die benachbarten Elemente zugreifen.
Die Knoten einer verketteten Listen hingegen werden an beliebigen Stellen im Speicher allokiert, können also über den gesamten Speicher verteilt sein. Beim Traversieren einer verketteten Liste müsste also im worst case für jedes Element eine neue Memory Page geladen werden.
Vorteile der Linked List gegenüber dem Array
In diesem und dem nächsten Abschnitt fasse ich die Vor- und Nachteile von Array und Linked List noch einmal zusammen.
Warum ist eine Linked List besser als ein Array?
- Elemente können mit konstantem Aufwand eingefügt und entfernt werden.
- Die Linked List belegt keinen ungenutzten Speicher.
Vorteile des Arrays gegenüber der Linked List
Und wann ist ein Array besser als eine Linked List?
- Wir können auf jedes beliebige Element des Arrays ("random access") in konstanter Zeit zugreifen.
- Wir können ein Array von hinten nach vorne traversieren – das ist bei einer einfach verketteten Liste nicht möglich, nur bei einer doppelt verketteten.
- Ein Array belegt – bei gleicher Anzahl Elemente – deutlich weniger Speicher als eine verkettete Liste (C/C++: Faktor 2–3; Java: Faktor 6).
- Durch den Lokalitätseffekt können wir bei einem Array auf nah nebeneinander liegende Elemente deutlich schneller zugreifen.
- Der Garbage Collector kann bei einem Array eine Reachability-Analyse deutlich schneller durchführen als bei einer Linked List.
- Beim Löschen eines Arrays wird ein zusammenhängender Speicherbereich freigegeben, während das Löschen einer verketteten Liste einen fragmentierten Speicher zurücklässt.
Fazit: Wann ein Array benutzen und wann eine Linked List?
Die Frage "Welche Datenstruktur ist besser – Array oder Linked List?" lässt sich, wie so vieles, nur mit einem "Es kommt darauf an" beantworten.
Wenn oft Elemente in der Mitte der Datenstruktur eingefügt oder entfernt werden, dann sollte eine verkettete Liste die bessere Wahl sein.
Für alle anderen Anwendungsfälle liefern in der Regel Array-basierte Datenstrukturen eine bessere Performance und einen besseren Memory Footprint und sollten daher bevorzugt eingesetzt werden.
Wenn du vermutest, dass für deinen Einsatzzweck eine Linked List besser geeignet ist, dann probier es einfach aus. Führe Messungen durch, und entscheide dich basierend auf den Messergebnissen.
Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.