Was sind konkrete Regeln für die Verwendung einer verknüpften Liste anstelle eines Arrays?

18

Eine verknüpfte Liste kann verwendet werden, wenn Sie Elemente billig einfügen und löschen möchten und es keine Rolle spielt, dass die Elemente im Speicher nicht nebeneinander liegen.

Dies ist sehr abstrakt und ich möchte eine konkrete Erklärung dafür, warum eine verknüpfte Liste anstelle eines Arrays verwendet werden sollte. Ich bin nicht sehr erfahren im Programmieren, daher habe ich nicht viel (wenn überhaupt) Praxiserfahrung.

data-structures linked-list richtig falten
quelle
3
Ehrlich gesagt, ich glaube nicht, dass Beispiele Ihnen so viel bedeuten werden, bis Sie Erfahrung damit haben, etwas zu schreiben und dann zu sehen, wie sich das Ändern von Datenstrukturen auf Ihren Code auswirkt. Schreiben Sie entweder etwas, das Sie interessiert, und finden Sie heraus, welche Datenstrukturen und Container am besten passen, oder sehen Sie sich einen vorhandenen Code an und überlegen Sie, warum die einzelnen Container ausgewählt wurden und welche Auswirkungen eine Änderung haben würde.
Nutzlos
Ich glaube einfach nicht, dass es sinnvoll ist, die Kompromisse und Nebenwirkungen der Datenstrukturauswahl dem (unerfahrenen) OP mitzuteilen, ohne ein viel längeres Beispiel zu haben, als hier vernünftig ist. Die als Antworten gegebenen Beispiele sind in Ordnung und beantworten die gestellte Frage, aber nicht (was ich als gelesen habe) eine implizite Bitte um tatsächliches Verständnis.
Nutzlos

Antworten:

37

Hier liegt etwas zwischen einem Beispiel und einer Analogie. Sie müssen noch ein paar Besorgungen erledigen, schnappen sich also ein Stück Papier und schreiben:

  • Bank
  • Lebensmittel
  • chemisch reinigen lassen

Dann erinnerst du dich, dass du auch Briefmarken kaufen musst. Aufgrund der geografischen Lage Ihrer Stadt müssen Sie dies nach der Bank tun. Sie können Ihre gesamte Liste auf ein neues Blatt Papier kopieren:

  • Bank
  • Briefmarken
  • Lebensmittel
  • chemisch reinigen lassen

oder du könntest auf den kritzeln, den du hattest:

  • bank ....... BRIEFMARKEN
  • Lebensmittel
  • chemisch reinigen lassen

Wenn Sie an andere Besorgungen denken, können Sie sie am Ende der Liste schreiben, aber mit Pfeilen, die Sie daran erinnern, in welcher Reihenfolge Sie sie ausführen sollen. Dies ist eine verknüpfte Liste. Es ist schneller und einfacher als jedes Mal, wenn Sie etwas hinzufügen, die gesamte Liste zu kopieren.

Dann klingelt dein Handy, während du bei der Bank bist. "Hey, ich habe die Briefmarken, nimm nicht mehr ab." Sie streichen STAMPS einfach von der Liste, Sie schreiben kein ganz neues ohne STAMPS.

Jetzt können Sie tatsächlich eine Besorgungsliste im Code implementieren (möglicherweise eine App, mit der Ihre Besorgungen anhand Ihrer geografischen Lage in eine geordnete Reihenfolge gebracht werden), und es besteht eine vernünftige Chance, dass Sie tatsächlich eine verknüpfte Liste für diese Liste im Code verwenden. Sie möchten viele Elemente hinzufügen und entfernen sowie wichtige Informationen bestellen, möchten jedoch nicht nach jedem Einfügen oder Löschen die gesamte Liste neu kopieren.

Kate Gregory
quelle
3
Laut Bjarne Stroustrup sind LLs möglicherweise nicht so einfach und schnell, um die gesamte Liste zu kopieren, wie Sie denken .
Dennis
@ Tennis ja, ich weiß, dank Semantik bewegen. Dies gilt jedoch nicht für alle Sprachen, so dass das Beispiel steht.
Kate Gregory
1
@KateGregory ist fair genug, aber es ist trotzdem gut darauf hinzuweisen, dass "grundlegende" Datenstrukturen oft besser sind als die coolen Datenstrukturen, die wir in der Schule (oder anderswo) kennen. Ich möchte nicht, dass neue Absolventen LLs überall verwenden, da dies theoretisch angemessen ist und möglicherweise realistisch gesehen eine schlechte Wahl darstellt. Es ist wichtig, die richtige Datenstruktur zu verwenden, und manchmal wird sie von Menschen überkompliziert. Etwas verwandt ist dieser Vortrag von Jonathan Blow (Schöpfer von "Braid") über Datenstrukturen .
Dennis
1
@Ray: Eine verknüpfte Liste kann eine Baumstruktur übertreffen, wenn Sie erwarten, dass sie in der Größenordnung von 4 Elementen liegt und Vergleiche relativ billig sind. Ich weiß nicht genau, wo die Grenze liegt, wo dies nicht der Fall ist. Außerdem erfordert eine Baumstruktur, dass Ihre Daten sortiert werden können, wohingegen eine Listenstruktur es Ihnen ermöglicht, die Einfügereihenfolge (oder eine beliebige Reihenfolge) beizubehalten.
David Stone
2
Ich denke nicht, dass diese Analogie sehr genau ist. Als Mensch können wir (zumindest für eine so kurze Liste) ein Element in O (1) finden. Wenn Sie jedoch ein zufälliges Einfügen in eine verknüpfte Liste vornehmen möchten, müssen Sie durchschnittlich die Hälfte der Elemente durchlaufen, was Sie O (n) kostet, um nur die Position zu finden, an der Sie einfügen möchten. Die tatsächliche Einfügung kostet dann nur O (1), aber bei einem Array betragen Ihre Kosten auch "nur" O (n). Der Grund liegt also nicht nur in der Bewegungssemantik, sondern auch im Algorithmus. Der durch das Big-O verborgene konstante Faktor ist jedoch aufgrund des nicht zusammenhängenden Speicherzugriffs für die bevorzugte Liste viel größer.
5gon12eder
18
  • Hashtabellen, die Hash-Kollisionen mithilfe der Verkettung auflösen, enthalten normalerweise eine verknüpfte Liste pro Bucket für die Elemente in diesem Bucket.
  • Einfache Speicherzuordnungen verwenden eine freie Liste nicht verwendeter Speicherbereiche, im Grunde genommen eine verknüpfte Liste mit dem Listenzeiger im freien Speicher selbst
  • In einem FAT-Dateisystem sind die Metadaten einer großen Datei als verknüpfte Liste von FAT-Einträgen organisiert.
Michael Borgwardt
quelle
12

Der "Aufruf-Stapel" der C-Sprache ist als verknüpfte Liste in den x86-Binär-APIs (und den meisten anderen APIs) implementiert .

Das heißt, der Aufruf von Prozeduren in der C-Sprache folgt einer First-In-Last-Out-Disziplin. Das Ergebnis der Ausführung (möglicherweise rekursiver) Funktionsaufrufe wird als "Aufrufstapel" oder manchmal auch nur als "Stapel" bezeichnet.

Die CALLx86-Anweisung implementiert schließlich eine verknüpfte Liste mithilfe des "Aufrufstapels". Ein CALLBefehl überträgt den Inhalt des% EIP-Registers, die Adresse des Befehls nach dem CALLin den Stapelspeicher. Der Aufruf-Funktions-Prolog überträgt den Inhalt des% EBP-Registers, der niedrigsten Adresse der lokalen Variablen in der aufrufenden Funktion, in den Stapelspeicher. Dann setzt der aufgerufene Funktionsprolog% EBP auf die Stapelbasis der aktuellen Funktion.

Das bedeutet, dass% EBP ein Zeiger auf einen Speicherort ist, der die Adresse des% EBP-Werts der aufrufenden Funktion enthält. Das ist nichts weiter als eine verknüpfte Liste, die teilweise in Hardware über implementiert ist CALL.

Soweit dies sinnvoll ist, implementieren x86-CPUs Funktionsaufrufe, insbesondere Funktionsaufrufe, bei denen die Funktion über eine eigene Kopie von Argumenten und funktionslokalen Variablen verfügt. Bei jedem Funktionsaufruf werden Informationen auf dem "Aufrufstapel" abgelegt, mit denen die CPU dort weitermachen kann, wo sie in der aufrufenden Funktion aufgehört hat, ohne die aufgerufene Funktion oder die aufrufende Funktion zu beeinträchtigen.

Bruce Ediger
quelle
3

Eine verknüpfte Liste kann zum Implementieren einer Nachrichtenwarteschlange verwendet werden.

Eine Nachrichtenwarteschlange ist eine Struktur, in der Informationen zu Ereignissen für die spätere Verarbeitung gespeichert werden. Wenn der Benutzer beispielsweise eine Taste drückt oder die Maus bewegt, ist dies ein Ereignis. Eine Anwendung ist möglicherweise zum Zeitpunkt des Auftretens des Ereignisses ausgelastet, sodass nicht erwartet werden kann, dass sie das Ereignis zum genauen Zeitpunkt des Auftretens verarbeitet. Das Ereignis wird in eine Nachrichtenwarteschlange gestellt (Informationen darüber, welche Taste gedrückt wurde oder wo sich die Maus bewegt hat). Wenn die Anwendung etwas Zeit hat, überprüft sie die Nachrichtenwarteschlange, ruft Ereignisse ab und verarbeitet sie Sie. (Dies geschieht innerhalb eines Zeitrahmens von Millisekunden, sodass es nicht auffällt.)

Aus dem Nutzungsszenario, das ich gerade beschrieben habe, sollte ersichtlich sein, dass es uns egal ist, zufälligen Zugriff auf Ereignisse zu haben, die in der Nachrichtenwarteschlange gespeichert sind. Es ist uns nur ein Anliegen, Nachrichten darin zu speichern und abzurufen. Daher ist es sinnvoll, eine verknüpfte Liste zu verwenden, die eine optimale Einfüge- / Entfernungszeit bietet.

(Bitte melden Sie sich nicht an, um darauf hinzuweisen, dass eine Nachrichtenwarteschlange wahrscheinlich oder eher oder fast genauso wahrscheinlich mithilfe einer zirkulären Array-Liste implementiert wird. Dies ist ein technisches Detail und hat eine Einschränkung: Sie können nur speichern eine begrenzte Anzahl von Nachrichten.)

Mike Nakis
quelle