Deutsch
Menü

Array vs. verkettete Liste: Zugriff, Einfügen und Löschen, Speicherlayout, Cache und Zeitkomplexität

Ein Array legt Elemente desselben Typs lückenlos hintereinander im Speicher ab, sodass sich die Position jedes Elements aus seinem Index berechnen und in konstanter Zeit lesen oder schreiben lässt. Eine verkettete Liste ist eine Datenstruktur, in der jedes Element einen Wert und einen Zeiger auf das nächste Element enthält und die Elemente durch das Verfolgen dieser Zeiger verbunden sind; sie können daher an getrennten Stellen im Speicher liegen. Ein Array liest schnell, doch Einfügen oder Löschen in der Mitte bedeutet, die dahinterliegenden Elemente zu verschieben. Eine verkettete Liste kann einfügen oder löschen, indem nur Zeiger geändert werden, sobald die Position bekannt ist, doch zum Lesen des i-ten Elements muss man sie vom Anfang an durchlaufen. Die Grundregel: ein Array, wenn meist per Index gelesen wird, und eine verkettete Liste, wenn oft an bekannten Positionen eingefügt oder gelöscht wird.

MerkmalArrayVerkettete Liste
SpeicherlayoutDie Elemente liegen in einem zusammenhängenden Block direkt nebeneinanderDie Elemente liegen verstreut und sind über Zeiger verbunden
Lesen des i-ten ElementsO(1): Die Adresse ist Startadresse + i × ElementgrößeO(n): vom Anfang aus i-mal den Zeigern folgen
Suche nach einem WertO(n) mit linearer Suche, wenn unsortiert; O(log n) mit binärer Suche, wenn sortiertO(n) auch bei Sortierung; binäre Suche ist nicht möglich, da man nicht direkt in die Mitte springen kann
Einfügen oder Löschen in der MitteO(n): Die dahinterliegenden Elemente werden einzeln verschobenO(1), wenn die Position (das vorhergehende Element) bekannt ist; nur Zeiger ändern sich
Anhängen am EndeO(1), wenn Platz frei ist; ein dynamisches Array, das seine Kapazität jeweils verdoppelt, kopiert gelegentlich alles, ist im Mittel aber O(1) (amortisiert)O(1), wenn ein Zeiger auf das letzte Element gehalten wird
GrößenänderungDie Größe eines Arrays fester Länge wird beim Anlegen festgelegt; zum Vergrößern wird ein neuer Block angelegt und kopiertSpeicher wird pro Element belegt, daher wächst sie nur so weit wie nötig
SpeicherbedarfNur die Elemente selbst (ein dynamisches Array hält etwas Reservekapazität)Zusätzlicher Platz für einen Zeiger pro Element (zwei bei einer doppelt verketteten Liste)
Cache-FreundlichkeitGut: Die Elemente liegen zusammenhängend, daher nutzen sequenzielle Lesezugriffe Caches und Prefetching gutSchlecht: Die Elemente liegen oft verstreut, daher kann selbst derselbe O(n)-Durchlauf viel langsamer sein als bei einem Array
Typischer EinsatzTabellen mit Zugriff per Index, Matrizen und Bilder, Daten zum Sortieren oder für binäre Suche, Implementierung von Stacks und WarteschlangenFolgen mit häufigem Einfügen und Löschen, Verkettung in Hashtabellen, Verwaltung freien Speichers

Die Zahlenwerte sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welche Variante?

Array
Wenn Elemente meist per Index gelesen und geschrieben oder der Reihe nach vom Anfang gelesen werden. Weil Caches mit ihnen gut funktionieren, sind Arrays (einschließlich dynamischer Arrays) auf heutigen Rechnern in vielen Situationen schneller.
Verkettete Liste
Wenn viel in der Mitte eingefügt und gelöscht wird und man bereits einen Zeiger auf die Position hält. Da Elemente ohne Verschieben neu verknüpft werden, wird sie auch verwendet, wenn sich die Adressen der Elemente nicht ändern dürfen.

Häufige Fragen

Einfügen in eine verkettete Liste ist O(1) – warum sind Arrays in der Praxis trotzdem manchmal schneller?

Aus zwei Gründen. Erstens: Muss die Einfügestelle vom Anfang aus gesucht werden, kostet diese Suche O(n), sodass der gesamte Vorgang O(n) ist, genau wie beim Array, auch wenn das Einfügen selbst O(1) ist. Zweitens: Das Verschieben von Array-Elementen ist eine Kopie zusammenhängenden Speichers, die Caches gut nutzt und sehr schnell ist, während das Durchlaufen einer verketteten Liste Element für Element verstreute Adressen liest und den Cache oft verfehlt. Die Zeitkomplexität beschreibt, wie die Kosten mit der Datenmenge wachsen; die tatsächliche Geschwindigkeit sollte man messen.

Wie unterscheiden sich einfach und doppelt verkettete Listen?

In einer einfach verketteten Liste hat jedes Element nur einen Zeiger auf das nächste Element, sie lässt sich daher nur von vorn nach hinten durchlaufen. Eine doppelt verkettete Liste hat zusätzlich einen Zeiger auf das vorherige Element, lässt sich also auch rückwärts durchlaufen, und mit einem Zeiger auf ein Element kann dieses in O(1) gelöscht werden. Dafür hat jedes Element einen Zeiger mehr, und es müssen mehr Zeiger angepasst werden.

Was ist ein dynamisches Array?

Ein Array, das seine Größe ändern kann: Reicht die Kapazität nicht mehr aus, legt es einen größeren Block an und kopiert alles hinüber. Verdoppelt sich die Kapazität jedes Mal, entspricht die Gesamtzahl der Kopien nur etwa der Anzahl der Elemente, sodass das Anhängen am Ende im Mittel O(1) ist. Das Lesen per Index ist wie bei einem gewöhnlichen Array O(1).

Verständnis prüfen

Welche Aussage beschreibt eine verkettete Liste (eine Liste, in der jedes Element einen Zeiger auf das nächste Element enthält) im Vergleich zu einem Array richtig?

  1. AIst das Element direkt vor der Einfügestelle bekannt, lässt sich ein neues Element allein durch Umsetzen von Zeigern einfügen, ohne andere Elemente zu verschieben; um das i-te Element zu lesen, muss die Liste aber von vorn durchlaufen werden
  2. BDie Position des i-ten Elements lässt sich berechnen, daher kann jedes Element in konstanter Zeit O(1) gelesen werden
  3. CDie Elemente liegen lückenlos hintereinander im Speicher, daher wirken Cache und Prefetching beim sequenziellen Lesen gut
Antwort und Erläuterung anzeigen

Antwort: A. Ist das Element direkt vor der Einfügestelle bekannt, lässt sich ein neues Element allein durch Umsetzen von Zeigern einfügen, ohne andere Elemente zu verschieben; um das i-te Element zu lesen, muss die Liste aber von vorn durchlaufen werden

In einer verketteten Liste genügt es zum Einfügen und Löschen an einer bekannten Stelle, die benachbarten Zeiger umzuschreiben; das kostet O(1). Um das i-te Element zu lesen, muss man dagegen von vorn i Zeigern folgen, was O(n) dauert. Ein Array berechnet die Adresse des i-ten Elements aus der Startadresse und der Elementgröße und liest jedes Element in O(1); das Einfügen in der Mitte kostet aber O(n), weil die nachfolgenden Elemente verschoben werden müssen. Da die Elemente eines Arrays zusammenhängend liegen, wirken außerdem Cache und Prefetching gut, während die Knoten einer verketteten Liste oft im Speicher verstreut sind; selbst ein Durchlauf mit gleichem O(n) kann dann deutlich langsamer sein.

Ein dynamisches Array legt, wenn ein Element hinzugefügt wird, während es voll ist, einen neuen Bereich mit doppelter Kapazität an und kopiert alle Elemente dorthin. Wie viele Elementkopien entstehen insgesamt, wenn einem leeren Array mit der Kapazität 1 nacheinander 1000 Elemente hinzugefügt werden?

  1. A10
  2. B1023
  3. C499.500
Antwort und Erläuterung anzeigen

Antwort: B. 1023

Die Kapazität verdoppelt sich jedes Mal, wenn sie erschöpft ist, also 1, 2, 4, …, 512, und jedes Mal werden alle vorhandenen Elemente kopiert; die Gesamtzahl der Kopien beträgt daher 1 + 2 + 4 + … + 512 = 1023. Bei 1000 Hinzufügungen ist das etwa eine Kopie pro Element, der Aufwand pro Hinzufügen ist im Mittel also konstant: amortisiert O(1). Wüchse die Kapazität jedes Mal nur um 1, ergäben sich 1 + 2 + … + 999 = 499.500 Kopien, also O(n²). 10 ist die Zahl der Neuanlagen des Speicherbereichs, nicht die Zahl der kopierten Elemente.

Welche Aussage vergleicht die Verkettung (Chaining: Elemente derselben Position werden in einer verketteten Liste verbunden) und die offene Adressierung (eine andere freie Position innerhalb der Tabelle wird gesucht) als Verfahren zur Kollisionsauflösung in Hashtabellen richtig? Der Belegungsfaktor ist die Zahl der gespeicherten Elemente geteilt durch die Tabellengröße.

  1. AMit Verkettung lassen sich auch bei einem Belegungsfaktor über 1 Elemente speichern; bei offener Adressierung können nicht mehr Elemente gespeichert werden, als die Tabelle groß ist, und die Zahl der Sondierschritte steigt stark an, wenn sich der Belegungsfaktor 1 nähert
  2. BBei offener Adressierung treten keine Kollisionen auf, daher genügt unabhängig vom Belegungsfaktor stets ein Sondierschritt
  3. CBei Verkettung bleibt der Suchaufwand gleich, wie hoch der Belegungsfaktor auch wird
Antwort und Erläuterung anzeigen

Antwort: A. Mit Verkettung lassen sich auch bei einem Belegungsfaktor über 1 Elemente speichern; bei offener Adressierung können nicht mehr Elemente gespeichert werden, als die Tabelle groß ist, und die Zahl der Sondierschritte steigt stark an, wenn sich der Belegungsfaktor 1 nähert

Die Verkettung verbindet die Elemente derselben Position zu Listen und kann daher mehr Elemente speichern, als die Tabelle groß ist; die mittlere Listenlänge wächst aber proportional zum Belegungsfaktor und mit ihr der Suchaufwand. Die offene Adressierung speichert alles innerhalb der Tabelle und fasst daher höchstens so viele Elemente, wie die Tabelle groß ist; die Zahl der Sondierschritte bis zu einem freien Platz steigt stark an, wenn sich der Belegungsfaktor 1 nähert. Bei beiden Verfahren ist es üblich, die Tabelle zu vergrößern und alle Elemente neu einzufügen (Rehashing), sobald der Belegungsfaktor einen gewählten Grenzwert wie etwa 0,5 bis 0,75 überschreitet. Auch bei offener Adressierung treten Kollisionen auf; sie werden durch die Suche nach einer freien Position behandelt.

  1. Warum ist bei einer Hashtabelle mit vielen Elementen und einem Belegungsfaktor von etwa 0,5 die offene Adressierung mit linearem Sondieren am ehesten schneller als die Verkettung (Verbinden der Elemente durch verkettete Listen)?
  2. Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?

Übungsfragen zu Datenstrukturen und Algorithmen

Wichtige Begriffe erklärt

Array
Eine Datenstruktur, die Werte desselben Typs nacheinander speichert und jedes Element über einen Index anspricht. Weil die Elemente zusammenhängend im Speicher liegen, lässt sich die Position jedes Elements aus seinem Index berechnen, sodass jedes Element in konstanter Zeit gelesen oder geschrieben werden kann. Manche Sprachen beginnen die Indizes bei 0, manche Schreibweisen bei 1.
Verkettete Liste (Linked List)
Datenstruktur, in der jedes Element einen Wert und einen Zeiger auf das nächste Element enthält und die Elemente durch das Verfolgen der Zeiger verbunden sind. Ist die Position bekannt, sind Einfügen und Löschen Zeigeränderungen in O(1), doch das Lesen des i-ten Elements erfordert einen Durchlauf von vorn in O(n). Die Elemente liegen oft verstreut im Speicher, daher wirken Caches schlechter als bei Arrays.
Zeiger (Pointer)
Variable, deren Wert die Speicheradresse einer Variablen, eines Array-Elements, einer Funktion o. Ä. ist. In C wird ein Zeiger etwa als int *p deklariert; &x liefert die Adresse von x, und *p liest oder schreibt den Wert, auf den p zeigt. Addiert man eine Ganzzahl zu einem Zeiger, bewegt er sich in Einheiten der Größe des Typs, auf den er zeigt. Der Name eines Arrays wird in den meisten Ausdrücken in einen Zeiger auf das erste Element umgewandelt, und a[i] bedeutet dasselbe wie *(a + i). Der Wert, der für „zeigt auf nichts“ steht, heißt NULL-Zeiger.
Zeitkomplexität (O-Notation)
Beschreibung, wie der Aufwand (Zeitkomplexität) oder der Speicherbedarf (Platzkomplexität) eines Algorithmus mit der Zahl n der Datenelemente wächst. Angegeben wird sie in O-Notation, etwa O(n), O(n log n) oder O(n²), wobei konstante Faktoren und Terme niedrigerer Ordnung entfallen.
Binäre Suche (Binary Search)
Suchverfahren für sortierte Daten, das den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert. Es findet einen Wert unter n Elementen mit höchstens ⌊log₂ n⌋ + 1 Vergleichen, die Komplexität ist also O(log n). Die Daten müssen sortiert sein.
Hashtabelle (Hash Table)
Datenstruktur, die mit einer Hashfunktion aus einem Schlüssel eine Speicherposition berechnet und so Suchen, Einfügen und Löschen im Mittel in O(1) ermöglicht. Kollisionen, bei denen verschiedene Schlüssel auf dieselbe Position fallen, werden durch Verkettung (Chaining) oder offene Adressierung behandelt.
Räumliche Lokalität
Eigenschaft, dass nach dem Zugriff auf eine Adresse bald auch auf benachbarte Adressen zugegriffen wird. Beispiel ist das sequenzielle Lesen eines Arrays; Grund dafür, dass Daten in Cache-Zeilen gebündelt geladen werden.

Verwandte Vergleiche