Arrays und verkettete Listen (Linked Lists) sind Datenstrukturen, die Elemente eines bestimmten Typs sequenziell 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 sind 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 Element eines Arrays beträgt somit: O(1).
Das ist auch der Grund, warum die binäre Suche in Java auf Arrays so schnell ist: Sie kann direkt in die Mitte des Suchbereichs springen.
Bei einer verketteten Liste hingegen können wir nur auf das erste Element direkt zugreifen (und bei einer doppelt verketteten Liste, die eine Referenz auf ihr Ende hält, auch auf das letzte). 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 amortisierten 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 Ringpuffer (englisch: „ring buffer“ oder „circular buffer“) 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 hingegen 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.
Das O(1) für Einfügen und Entfernen in der Linked List gilt allerdings nur, wenn die Position bereits als Referenz auf den Knoten vorliegt – in Java z. B. über einen ListIterator. Musst du die Position erst suchen, kommt der Aufwand für die Suche, O(n), hinzu.
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 8 Byte für den Objekt-Header des Knotenobjekts hinzu.¹ Insgesamt benötigen wir also 16 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 8 Byte für den Objekt-Header hinzu – macht 20 Byte. Da Objekte ein Vielfaches von 8 Byte belegen müssen, kommen 4 Füllbytes dazu, insgesamt also 24 Byte pro Knoten. Die doppelt verkettete Liste kostet in Java damit 50 % mehr Speicher als die einfach verkettete.
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 Byte | 8 Byte | 12 Byte |
| JVM-Sprache (ab Java 27): | 4 Byte | 16 Byte¹ | 24 Byte¹ |
| JVM-Sprache (bis Java 26): | 4 Byte | 24 Byte¹ | 24 Byte¹ |
Bis hierhin spricht der Speicherverbrauch für das Array – ganz besonders in Java.
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 Vier- bis 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 lädt die CPU nicht nur das angeforderte Element, sondern die gesamte Cache Line (auf den meisten CPUs 64 Byte) in den CPU-Cache – bei einem int-Array also 16 benachbarte Elemente auf einmal. Sobald wir auf ein Array-Element zugegriffen haben, können wir also sehr schnell auf die benachbarten Elemente zugreifen.
Die Knoten einer verketteten Liste hingegen werden an beliebigen Stellen im Speicher allokiert, können also über den gesamten Speicher verteilt sein. Beim Traversieren einer verketteten Liste muss also im Worst Case für jeden Knoten eine neue Cache Line aus dem Hauptspeicher geladen werden – ein sogenannter Cache Miss, der ein Vielfaches eines Cache-Treffers kostet.
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 4–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 – zumindest bei manueller Speicherverwaltung wie in C/C++. Kompaktierende Garbage Collectors räumen das auf.
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 kann eine verkettete Liste die bessere Wahl sein – vorausgesetzt, du hältst die Einfügeposition bereits als Referenz auf den Knoten in der Hand (in Java z. B. über einen ListIterator). Musst du die Position erst suchen, ist der Aufwand ohnehin O(n) – und dann gewinnt wegen des Lokalitätseffekts in der Regel das Array.
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.
War dieser Artikel hilfreich für dich? Dann freue ich mich, wenn du dir kurz Zeit für eine Bewertung auf meinem ProvenExpert-Profil nimmst.
Wenn du informiert werden möchtest, sobald der nächste Artikel erscheint, klicke hier und trage dich für den HappyCoders-Newsletter ein.
