Unter welchen Umständen sind verknüpfte Listen nützlich?

Meistens sehe ich Leute, die versuchen, verknüpfte Listen zu verwenden. Es scheint mir eine schlechte (oder sehr schlechte) Wahl zu sein. Vielleicht wäre es nützlich, die Umstände zu untersuchen, unter denen eine verknüpfte Liste eine gute Wahl für die Datenstruktur ist oder nicht.

Im Idealfall werden in den Antworten die Kriterien erläutert, die bei der Auswahl einer Datenstruktur zu verwenden sind, und welche Datenstrukturen unter bestimmten Umständen wahrscheinlich am besten funktionieren.

Edit: Ich muss sagen, ich bin nicht nur von der Anzahl, sondern auch von der Qualität der Antworten ziemlich beeindruckt. Ich kann nur einen akzeptieren, aber es gibt noch zwei oder drei, von denen ich sagen müsste, dass es sich gelohnt hätte, sie zu akzeptieren, wenn etwas Besseres nicht da gewesen wäre. Nur ein paar (insbesondere das, das ich letztendlich akzeptiert habe) wiesen auf Situationen hin, in denen eine verknüpfte Liste einen echten Vorteil bot. Ich denke, Steve Jessop verdient eine lobende Erwähnung, weil er nicht nur eine, sondern drei verschiedene Antworten gefunden hat, die ich alle sehr beeindruckend fand. Natürlich, obwohl es nur als Kommentar und nicht als Antwort gepostet wurde, denke ich, dass Neils Blogeintrag auch lesenswert ist - nicht nur informativ, sondern auch sehr unterhaltsam.

Sie können für gleichzeitige Datenstrukturen nützlich sein. (Es gibt jetzt unten ein Beispiel für eine nicht gleichzeitige Verwendung in der realen Welt - das wäre nicht da, wenn @Neil FORTRAN nicht erwähnt hätte. ;-)

Zum Beispiel ConcurrentDictionary<TKey, TValue>verknüpfen in .NET 4.0 RC Verwendung Listen Ketten Artikel , dass Hash auf den gleichen Eimer.

Die zugrunde liegende Datenstruktur für ConcurrentStack<T>ist ebenfalls eine verknüpfte Liste.

ConcurrentStack<T>ist eine der Datenstrukturen, die als Grundlage für den neuen Thread-Pool dienen (wobei die lokalen "Warteschlangen" im Wesentlichen als Stapel implementiert sind). (Die andere Haupttragstruktur ist ConcurrentQueue<T>.)

Der neue Thread-Pool bildet wiederum die Grundlage für die Arbeitsplanung der neuen Task Parallel Library .

Sie können also durchaus nützlich sein - eine verknüpfte Liste dient derzeit als eine der wichtigsten unterstützenden Strukturen für mindestens eine großartige neue Technologie.

(Eine einfach verknüpfte Liste trifft in diesen Fällen eine überzeugende, sperrenfreie, aber nicht wartefreie Wahl, da Hauptoperationen mit einem einzigen CAS ausgeführt werden können (+ Wiederholungsversuche). In einer modernen GC-d-Umgebung - wie z Java und .NET - das ABA-Problem kann leicht vermieden werden. Packen Sie einfach Elemente, die Sie hinzufügen, in frisch erstellte Knoten und verwenden Sie diese Knoten nicht wieder - lassen Sie den GC seine Arbeit erledigen. Die Seite zum ABA-Problem bietet auch die Implementierung einer Sperre. Free Stack - das funktioniert tatsächlich in .Net (& Java) mit einem (GC-ed) Knoten, der die Elemente enthält.)

Edit : @Neil: Eigentlich hat mich das, was Sie über FORTRAN erwähnt haben, daran erinnert, dass die gleiche Art von verknüpften Listen in der wahrscheinlich am häufigsten verwendeten und missbrauchten Datenstruktur in .NET zu finden ist: dem einfachen .NET-Generikum Dictionary<TKey, TValue>.

Nicht eine, sondern viele verknüpfte Listen werden in einem Array gespeichert.

• Es werden viele kleine (De-) Zuweisungen für Einfügungen / Löschungen vermieden.
• Das anfängliche Laden der Hash-Tabelle ist ziemlich schnell, da das Array nacheinander gefüllt wird (spielt sich sehr gut mit dem CPU-Cache).
• Ganz zu schweigen davon, dass eine Verkettungs-Hash-Tabelle speicherintensiv ist - und dieser "Trick" halbiert "Zeigergrößen" auf x64.

Im Wesentlichen werden viele verknüpfte Listen in einem Array gespeichert. (eine für jeden verwendeten Bucket.) Eine freie Liste wiederverwendbarer Knoten wird zwischen ihnen "verwoben" (falls gelöscht wurde). Ein Array wird beim Start / beim erneuten Aufwärmen zugewiesen und Knoten von Ketten werden darin beibehalten. Es gibt auch einen freien Zeiger - einen Index in das Array - der auf Löschungen folgt. ;-) Also - ob Sie es glauben oder nicht - die FORTRAN-Technik lebt weiter. (... und nirgendwo anders als in einer der am häufigsten verwendeten .NET-Datenstrukturen ;-).

Verknüpfte Listen sind sehr nützlich, wenn Sie viele Einfügungen und Entfernungen, aber nicht zu viele Suchvorgänge in einer Liste beliebiger Länge (zur Kompilierungszeit unbekannt) durchführen müssen.

Das Teilen und Verbinden von (bidirektional verknüpften) Listen ist sehr effizient.

Sie können auch verknüpfte Listen kombinieren - z. B. können Baumstrukturen als "vertikale" verknüpfte Listen (Eltern-Kind-Beziehungen) implementiert werden, die horizontale verknüpfte Listen (Geschwister) miteinander verbinden.

Die Verwendung einer Array-basierten Liste für diese Zwecke unterliegt schwerwiegenden Einschränkungen:

• Das Hinzufügen eines neuen Elements bedeutet, dass das Array neu zugewiesen werden muss (oder Sie müssen mehr Speicherplatz zuweisen, als Sie benötigen, um zukünftiges Wachstum zu ermöglichen und die Anzahl der Neuzuweisungen zu verringern).
• Das Entfernen von Elementen verschwendet Platz oder erfordert eine Neuzuweisung
• Das Einfügen von Elementen an einer anderen Stelle als am Ende umfasst das (möglicherweise Neuzuweisen und) Kopieren vieler Daten an einer Position

Verknüpfte Listen sind sehr flexibel: Mit der Änderung eines Zeigers können Sie eine massive Änderung vornehmen, bei der dieselbe Operation in einer Array-Liste sehr ineffizient wäre.

Arrays sind die Datenstrukturen, mit denen verknüpfte Listen normalerweise verglichen werden.

Normalerweise sind verknüpfte Listen nützlich, wenn Sie viele Änderungen an der Liste selbst vornehmen müssen, während Arrays beim direkten Elementzugriff eine bessere Leistung erzielen als Listen.

Hier ist eine Liste von Operationen, die für Listen und Arrays ausgeführt werden können, verglichen mit den relativen Operationskosten (n = Liste / Array-Länge):

• Hinzufügen eines Elements:
  • In Listen müssen Sie nur Speicher für das neue Element zuweisen und Zeiger umleiten. O (1)
  • Auf Arrays müssen Sie das Array verschieben. Auf)
• Ein Element entfernen
  • Auf Listen leiten Sie nur Zeiger um. O (1).
  • Bei Arrays verbringen Sie O (n) Zeit damit, das Array zu verschieben, wenn das zu entfernende Element nicht das erste oder das letzte Element des Arrays ist. Andernfalls können Sie den Zeiger einfach auf den Anfang des Arrays verschieben oder die Arraylänge verringern
• Ein Element an eine bekannte Position bringen:
  • Bei Listen müssen Sie die Liste vom ersten Element zum Element an der jeweiligen Position verschieben. Schlimmster Fall: O (n)
  • Auf Arrays können Sie sofort auf das Element zugreifen. O (1)

Dies ist ein Vergleich dieser beiden gängigen und grundlegenden Datenstrukturen auf sehr niedriger Ebene. Sie können feststellen, dass Listen in Situationen, in denen Sie viele Änderungen an der Liste selbst vornehmen müssen (Entfernen oder Hinzufügen von Elementen), eine bessere Leistung erzielen. Andererseits sind Arrays besser als Listen, wenn Sie direkt auf die Elemente des Arrays zugreifen müssen.

Aus Sicht der Speicherzuordnung sind Listen besser, da nicht alle Elemente nebeneinander stehen müssen. Andererseits gibt es den (geringen) Aufwand, die Zeiger auf das nächste (oder sogar auf das vorherige) Element zu speichern.

Für Entwickler ist es wichtig, diese Unterschiede zu kennen, um in ihren Implementierungen zwischen Listen und Arrays zu wählen.

Beachten Sie, dass dies ein Vergleich von Listen und Arrays ist. Es gibt gute Lösungen für die hier gemeldeten Probleme (z. B. SkipLists, Dynamic Arrays usw.). In dieser Antwort habe ich die grundlegende Datenstruktur berücksichtigt, die jeder Programmierer kennen sollte.

Eine einfach verknüpfte Liste ist eine gute Wahl für die kostenlose Liste in einem Zellenzuweiser oder Objektpool:

1. Sie benötigen nur einen Stapel, daher ist eine einfach verknüpfte Liste ausreichend.
2. Alles ist bereits in Knoten unterteilt. Es gibt keinen Zuordnungsaufwand für einen aufdringlichen Listenknoten, vorausgesetzt, die Zellen sind groß genug, um einen Zeiger zu enthalten.
3. Ein Vektor oder eine Deque würde einen Overhead von einem Zeiger pro Block auferlegen. Dies ist insofern von Bedeutung, als beim ersten Erstellen des Heaps alle Zellen frei sind. Dies ist also ein Vorabpreis. Im schlimmsten Fall verdoppelt sich der Speicherbedarf pro Zelle.

Eine doppelt verknüpfte Liste ist eine gute Wahl, um die Reihenfolge einer Hashmap zu definieren, die auch eine Reihenfolge für die Elemente definiert (LinkedHashMap in Java), insbesondere wenn sie nach dem letzten Zugriff sortiert ist:

1. Mehr Speicheraufwand als ein zugehöriger Vektor oder eine zugehörige Deque (2 Zeiger anstelle von 1), aber bessere Leistung beim Einfügen / Entfernen.
2. Kein Zuordnungsaufwand, da Sie ohnehin einen Knoten für einen Hash-Eintrag benötigen.
3. Die Referenzlokalität ist im Vergleich zu einem Vektor oder einer Deque von Zeigern kein zusätzliches Problem, da Sie jedes Objekt in beide Richtungen in den Speicher ziehen müssten.

Sicher, Sie können darüber streiten, ob ein LRU-Cache überhaupt eine gute Idee ist, verglichen mit etwas Anspruchsvollerem und Optimierbarem, aber wenn Sie einen haben wollen, ist dies eine ziemlich anständige Implementierung. Sie möchten nicht bei jedem Lesezugriff ein Löschen aus der Mitte und ein Hinzufügen zum Ende eines Vektors oder einer Deque durchführen, aber das Verschieben eines Knotens zum Ende ist normalerweise in Ordnung.

Sie sind nützlich, wenn Sie schnelles Drücken, Pop und Drehen benötigen und die O (n) -Indizierung nichts ausmacht.

Einfach verknüpfte Listen sind die offensichtliche Implementierung des allgemeinen Datentyps "Liste" in funktionalen Programmiersprachen:

1. Das Hinzufügen zum Kopf ist schnell und (append (list x) (L))und(append (list y) (L)) kann fast alle Daten gemeinsam nutzen. Keine Notwendigkeit zum Kopieren beim Schreiben in einer Sprache ohne Schreibvorgänge. Funktionale Programmierer wissen, wie sie dies nutzen können.
2. Das Hinzufügen zum Schwanz ist leider langsam, aber auch jede andere Implementierung.

Im Vergleich dazu ist es normalerweise langsam, einen Vektor oder eine Deque an beiden Enden hinzuzufügen, was (zumindest in meinem Beispiel mit zwei unterschiedlichen Anhängen) erfordert, dass eine Kopie der gesamten Liste (Vektor) oder des Indexblocks und des Datenblocks erstellt wird angehängt werden an (deque). Tatsächlich kann dort auf großen Listen etwas zu sagen sein, das aus irgendeinem Grund am Ende hinzugefügt werden muss. Ich bin nicht ausreichend über funktionale Programmierung informiert, um beurteilen zu können.

Verknüpfte Listen sind eine der natürlichen Möglichkeiten, wenn Sie nicht steuern können, wo Ihre Daten gespeichert sind, aber dennoch irgendwie von einem Objekt zum nächsten gelangen müssen.

Wenn Sie beispielsweise die Speicherverfolgung in C ++ implementieren (Neu- / Löschersetzung), benötigen Sie entweder eine Steuerdatenstruktur, die nachverfolgt, welche Zeiger freigegeben wurden, und die Sie vollständig selbst implementieren müssen. Die Alternative besteht darin, eine verknüpfte Liste am Anfang jedes Datenblocks zu ordnen und hinzuzufügen.

Da Sie immer sofort wissen, wo Sie sich beim Aufruf von delete in der Liste befinden, können Sie den Speicher in O (1) leicht aufgeben. Das Hinzufügen eines neuen Blocks, der gerade mallociert wurde, befindet sich in O (1). Das Durchlaufen der Liste wird in diesem Fall sehr selten benötigt, daher sind die O (n) -Kosten hier kein Problem (das Durchlaufen einer Struktur ist ohnehin O (n)).

Ein Beispiel für eine gute Verwendung für eine verknüpfte Liste ist, wenn die Listenelemente sehr groß sind, d. H. groß genug, dass nur ein oder zwei gleichzeitig in den CPU-Cache passen. Zu diesem Zeitpunkt ist der Vorteil, den zusammenhängende Blockcontainer wie Vektoren oder Arrays für die Iteration haben, mehr oder weniger aufgehoben, und ein Leistungsvorteil kann möglich sein, wenn viele Einfügungen und Entfernungen in Echtzeit erfolgen.

Aus meiner Erfahrung, Implementierung von Sparse-Matrizen und Fibonacci-Haufen. Mit verknüpften Listen haben Sie mehr Kontrolle über die Gesamtstruktur solcher Datenstrukturen. Ich bin mir zwar nicht sicher, ob Sparse-Matrizen am besten mithilfe von verknüpften Listen implementiert werden können - wahrscheinlich gibt es einen besseren Weg, aber es hat wirklich geholfen, die Vor- und Nachteile von Sparse-Matrizen mithilfe von verknüpften Listen in Undergrad CS zu lernen :)

Es gibt zwei komplementäre Operationen, die in Listen trivial O (1) sind und in O (1) in anderen Datenstrukturen nur sehr schwer zu implementieren sind - Entfernen und Einfügen eines Elements aus einer beliebigen Position, vorausgesetzt, Sie müssen die Reihenfolge der Elemente beibehalten.

Hash-Maps können natürlich in O (1) einfügen und löschen, aber dann können Sie die Elemente nicht der Reihe nach durchlaufen.

In Anbetracht der obigen Tatsache kann die Hash-Map mit einer verknüpften Liste kombiniert werden, um einen raffinierten LRU-Cache zu erstellen: Eine Map, die eine feste Anzahl von Schlüssel-Wert-Paaren speichert und den Schlüssel, auf den zuletzt zugegriffen wurde, löscht, um Platz für neue zu schaffen.

Die Einträge in der Hash-Map müssen Zeiger auf die verknüpften Listenknoten haben. Beim Zugriff auf die Hash-Map wird der Knoten der verknüpften Liste von seiner aktuellen Position getrennt und an den Kopf der Liste verschoben (O (1), yay für verknüpfte Listen!). Wenn das zuletzt verwendete Element entfernt werden muss, muss das Element aus dem Ende der Liste entfernt werden (erneut O (1), vorausgesetzt, Sie behalten den Zeiger auf den Endknoten), zusammen mit dem zugehörigen Hash-Map-Eintrag (also Backlinks von Die Liste zur Hash-Map ist notwendig.)

Bedenken Sie, dass eine verknüpfte Liste bei der Implementierung eines Systems im Domain Driven Design-Stil, das Teile enthält, die mit Wiederholungen ineinander greifen, sehr nützlich sein kann.

Ein Beispiel, das Ihnen in den Sinn kommt, könnte sein, wenn Sie eine hängende Kette modellieren. Wenn Sie wissen möchten, wie hoch die Spannung an einem bestimmten Link ist, kann Ihre Benutzeroberfläche einen Getter für das "scheinbare" Gewicht enthalten. Die Implementierung würde einen Link beinhalten, der seinen nächsten Link nach seinem scheinbaren Gewicht fragt und dann sein eigenes Gewicht zum Ergebnis hinzufügt. Auf diese Weise wird die gesamte Länge bis zum Ende mit einem einzigen Aufruf vom Client der Kette ausgewertet.

Als Befürworter von Code, der sich wie eine natürliche Sprache liest, gefällt mir, wie der Programmierer ein Kettenglied fragen kann, wie viel Gewicht es trägt. Es bleibt auch das Anliegen, diese Kinder von Eigenschaften innerhalb der Grenzen der Link-Implementierung zu berechnen, wodurch die Notwendigkeit eines Dienstes zur Berechnung des Kettengewichts entfällt. "

Einer der nützlichsten Fälle, die ich für verknüpfte Listen finde, die in leistungskritischen Bereichen wie Netz- und Bildverarbeitung, Physik-Engines und Raytracing arbeiten, ist die Verwendung verknüpfter Listen, die die Referenzlokalität verbessern, die Heap-Zuweisungen reduzieren und manchmal sogar die Speichernutzung im Vergleich zu reduzieren die einfachen Alternativen.

Nun, das kann wie ein komplettes Oxymoron erscheinen, dass verknüpfte Listen all das tun könnten, da sie dafür berüchtigt sind, oft das Gegenteil zu tun, aber sie haben eine einzigartige Eigenschaft, da jeder Listenknoten eine feste Größe und Ausrichtungsanforderungen hat, die wir ausnutzen können, um dies zuzulassen Sie müssen zusammenhängend gespeichert und in konstanter Zeit auf eine Weise entfernt werden, die Dinge mit variabler Größe nicht können.

Nehmen wir als Ergebnis einen Fall, in dem wir das analoge Äquivalent zum Speichern einer Sequenz variabler Länge ausführen möchten, die eine Million verschachtelter Teilsequenzen variabler Länge enthält. Ein konkretes Beispiel ist ein indiziertes Netz, in dem eine Million Polygone (einige Dreiecke, einige Quads, einige Fünfecke, einige Sechsecke usw.) gespeichert sind. Manchmal werden Polygone von einer beliebigen Stelle im Netz entfernt und manchmal werden Polygone neu erstellt, um einen Scheitelpunkt in ein vorhandenes Polygon oder einzufügen entferne einen. Wenn wir in diesem Fall eine Million Winzlinge speichern std::vectors, sehen wir uns einer Heap-Zuweisung für jeden einzelnen Vektor sowie einer potenziell explosiven Speichernutzung gegenüber. Eine Million Winzlinge SmallVectorsleiden in normalen Fällen möglicherweise nicht so häufig unter diesem Problem, aber ihr vorab zugewiesener Puffer, der nicht separat auf dem Heap zugeordnet ist, kann dennoch zu einer explosiven Speichernutzung führen.

Das Problem hierbei ist, dass eine Million std::vectorInstanzen versuchen würden, eine Million Dinge variabler Länge zu speichern. Dinge mit variabler Länge möchten in der Regel eine Heap-Zuordnung, da sie nicht sehr effektiv zusammenhängend gespeichert und in konstanter Zeit entfernt werden können (zumindest auf einfache Weise ohne einen sehr komplexen Allokator), wenn sie ihren Inhalt nicht an anderer Stelle auf dem Heap gespeichert haben.

Wenn wir stattdessen Folgendes tun:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... dann haben wir die Anzahl der Heap-Zuweisungen und Cache-Fehler drastisch reduziert. Anstatt für jedes einzelne Polygon, auf das wir zugreifen, eine Heap-Zuordnung und möglicherweise obligatorische Cache-Fehlschläge zu erfordern, benötigen wir diese Heap-Zuordnung nur dann, wenn einer der beiden im gesamten Netz gespeicherten Vektoren ihre Kapazität überschreitet (amortisierte Kosten). Und während der Schritt von einem Scheitelpunkt zum nächsten immer noch zu einem Anteil von Cache-Fehlern führen kann, ist er oft immer noch geringer als wenn jedes einzelne Polygon ein separates dynamisches Array speichert, da die Knoten zusammenhängend gespeichert werden und die Wahrscheinlichkeit besteht, dass ein benachbarter Scheitelpunkt vorhanden ist vor der Räumung zugegriffen werden (insbesondere wenn man bedenkt, dass viele Polygone ihre Scheitelpunkte auf einmal hinzufügen, wodurch der Löwenanteil der Polygonscheitelpunkte perfekt zusammenhängend ist).

Hier ist ein weiteres Beispiel:

... wo die Gitterzellen verwendet werden, um die Partikel-Partikel-Kollision für beispielsweise 16 Millionen Partikel zu beschleunigen, die sich in jedem einzelnen Frame bewegen. In diesem Beispiel für ein Partikelgitter können wir mithilfe verknüpfter Listen ein Partikel von einer Gitterzelle in eine andere verschieben, indem wir nur 3 Indizes ändern. Das Löschen von einem Vektor und das Zurückschieben zu einem anderen kann erheblich teurer sein und mehr Heap-Zuweisungen einführen. Die verknüpften Listen reduzieren auch den Speicher einer Zelle auf 32 Bit. Ein Vektor kann abhängig von der Implementierung sein dynamisches Array bis zu dem Punkt vorab zuweisen, an dem er 32 Bytes für einen leeren Vektor benötigen kann. Wenn wir ungefähr eine Million Gitterzellen haben, ist das ein ziemlicher Unterschied.

... und hier finde ich verknüpfte Listen heutzutage am nützlichsten, und ich finde speziell die Variante "indizierte verknüpfte Liste" nützlich, da 32-Bit-Indizes den Speicherbedarf der Verknüpfungen auf 64-Bit-Computern halbieren und implizieren, dass die Knoten werden zusammenhängend in einem Array gespeichert.

Oft kombiniere ich sie auch mit indizierten freien Listen, um zeitlich konstante Entfernungen und Einfügungen überall zu ermöglichen:

In diesem Fall zeigt der nextIndex entweder auf den nächsten freien Index, wenn der Knoten entfernt wurde, oder auf den nächsten verwendeten Index, wenn der Knoten nicht entfernt wurde.

Und dies ist der Anwendungsfall Nummer eins, den ich heutzutage für verknüpfte Listen finde. Wenn wir beispielsweise eine Million Teilsequenzen variabler Länge speichern möchten, die durchschnittlich 4 Elemente bilden (manchmal jedoch Elemente entfernen und zu einer dieser Teilsequenzen hinzufügen), können wir in der verknüpften Liste 4 Millionen speichern verknüpfte Listenknoten zusammenhängend anstelle von 1 Million Containern, die jeweils einzeln einem Heap zugeordnet sind: ein Riesenvektor, dh nicht eine Million kleine.

Ich habe in der Vergangenheit in einer C / C ++ - Anwendung verknüpfte Listen (sogar doppelt verknüpfte Listen) verwendet. Dies war vor .NET und sogar stl.

Ich würde jetzt wahrscheinlich keine verknüpfte Liste in einer .NET-Sprache verwenden, da der gesamte benötigte Traversal-Code über die Linq-Erweiterungsmethoden für Sie bereitgestellt wird.