Arrays und verkettete Listen

Arrays und verkettete Listen sind die beiden grundlegenden Methoden zur Speicherung einer geordneten Abfolge von Elementen: Arrays platzieren sie in zusammenhängendem Speicher für den indizierten Zugriff in konstanter Zeit, während verkettete Listen sie über Zeiger verketten, um das Einfügen und Löschen kostengünstig zu gestalten.

Definition

Ein Array speichert Elemente an zusammenhängenden Speicheradressen, indiziert nach Position, was einen wahlfreien Zugriff in konstanter Zeit ermöglicht; eine verkettete Liste speichert Elemente in separaten Knoten, wobei jeder Knoten eine Referenz auf den nächsten (und möglicherweise vorherigen) Knoten enthält, was ein Einfügen oder Entfernen in konstanter Zeit ermöglicht, wenn eine Knotenreferenz gegeben ist.

Scope

Dieses Thema behandelt lineare, sequenzbasierte Strukturen und die darauf aufbauenden abstrakten Datentypen – statische und dynamische Arrays, einfach und doppelt verkettete Listen sowie die ADTs Stapel und Warteschlange. Es vergleicht deren Kosten für Zugriff, Einfügen und Löschen, behandelt die Größenanpassung dynamischer Arrays und deren amortisierte Analyse und erläutert die Auswirkungen der Speicheranordnung, wie z. B. die Cache-Lokalität. Assoziative und hierarchische Strukturen, die unter Hash-Tabellen und Suchbäumen behandelt werden, sind ausgeschlossen.

Core questions

• Wann übertrifft die zusammenhängende (Array-)Speicherung die zeigerverknüpfte (Listen-)Speicherung?
• Wie erreicht ein dynamisches Array eine amortisierte konstante Zeit für das Anhängen trotz gelegentlicher Größenanpassung?
• Welche Kosten-Kompromisse ergeben sich bei Arrays im Vergleich zu verketteten Listen für das Einfügen, Löschen und den Zugriff?
• Wie werden Stapel und Warteschlangen auf diesen Strukturen implementiert?
• Wie beeinflusst die Speicheranordnung die reale Leistung durch das Cache-Verhalten?

Key concepts

• zusammenhängender Speicher
• indizierter Zugriff
• Größenanpassung dynamischer Arrays
• einfach und doppelt verkettete Listen
• Stapel (LIFO)
• Warteschlangen (FIFO)
• amortisierte Kosten
• Cache-Lokalität

Key theories

Direktzugriff versus sequentielle Verknüpfung

Arrays unterstützen den indizierten Zugriff in O(1), aber das Einfügen oder Löschen in der Mitte in O(n), während verkettete Listen das Einfügen in O(1) bei gegebenem Knoten unterstützen, aber den Zugriff nach Position in O(n); die richtige Wahl hängt von der Mischung der Operationen ab.

Amortisiertes Wachstum dynamischer Arrays

Ein dynamisches Array, das seine Kapazität verdoppelt, wenn es voll ist, führt gelegentlich O(n)-Kopien durch, amortisiert sich aber über jede Operationsfolge auf O(1) pro Anhängen, mittels der Aggregat- oder Potenzialmethode.

Clinical relevance

Arrays und Listen sind die Grundlage nahezu jedes Programms: Dynamische Arrays implementieren die Standard-Listen-/Vektortypen in den meisten Sprachen, Warteschlangen liegen der Zeitplanung und der Breitensuche zugrunde, Stapel liegen der Funktionsaufrufverwaltung und der Ausdrucksauswertung zugrunde, und der Kompromiss zwischen Array und Liste ist eine routinemäßige praktische Entwurfsentscheidung, die die Leistung beeinflusst.

History

Arrays gehören zu den frühesten Datenstrukturen, die in den ersten Programmiersprachen vorhanden waren, und verkettete Listen wurden Ende der 1950er Jahre für die symbolische und Listenverarbeitung (insbesondere in Newell, Shaw und Simons IPL und später Lisp) eingeführt. Knuths systematische Behandlung in The Art of Computer Programming etablierte ihre kanonische Analyse.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

Warum sollte man eine verkettete Liste verwenden, wenn Arrays einen schnellen Direktzugriff ermöglichen?

Verkettete Listen ermöglichen das Einfügen oder Löschen in konstanter Zeit, wenn eine Referenz auf einen Knoten vorliegt, ohne andere Elemente zu verschieben, was Arrays in der Mitte nicht können. Sie sind nützlich, wenn sich die Sequenz häufig ändert und kein positionsbezogener Direktzugriff erforderlich ist.

Warum werden Array-Anhängungen als konstante Zeit betrachtet, wenn die Größenanpassung alles kopiert?

Die Größenanpassung erfolgt selten, da sich die Kapazität typischerweise verdoppelt, sodass der gesamte Kopieraufwand über n Anhängungen proportional zu n ist. Über alle Anhängungen verteilt ergibt dies amortisierte konstante Kosten pro Anhängen, auch wenn einzelne Größenanpassungen O(n) sind.