In der Informatik ist eine verbundene Liste eine Datenstruktur, die aus einer Gruppe von Knoten besteht, die zusammen eine Folge vertreten. Unter der einfachsten Form wird jeder Knoten aus einer Gegebenheit und einer Verweisung (mit anderen Worten, eine Verbindung) zum folgenden Knoten in der Folge zusammengesetzt; kompliziertere Varianten fügen zusätzliche Verbindungen hinzu. Diese Struktur berücksichtigt effiziente Einfügung oder Eliminierung von Elementen von jeder Position in der Folge.

Verbundene Listen sind unter den einfachsten und allgemeinsten Datenstrukturen. Sie können verwendet werden, um mehrere andere allgemeine abstrakte Datentypen, einschließlich Stapel, Warteschlangen, assoziativer Reihe und symbolischer Ausdrücke durchzuführen, obwohl es ziemlich üblich ist, die anderen Datenstrukturen direkt durchzuführen, ohne eine Liste als die Basis der Durchführung zu verwenden.

Der Hauptvorteil einer verbundenen Liste über eine herkömmliche Reihe ist, dass die Listenelemente leicht eingefügt oder ohne Wiederzuteilung oder Reorganisation der kompletten Struktur entfernt werden können, weil die Datensachen aneinander grenzend im Gedächtnis oder auf der Platte nicht versorgt zu werden brauchen. Verbundene Listen erlauben Einfügung und Eliminierung von Knoten an jedem Punkt in der Liste, und können so mit einer unveränderlichen Zahl von Operationen tun, wenn die Verbindung vor der Verbindung, die wird hinzufügt oder entfernt, während des Listentraversals aufrechterhalten wird.

Andererseits erlauben einfache verbundene Listen durch sich zufälligen Zugang zu den Daten oder jede Form des effizienten Indexierens nicht. So können viele grundlegende Operationen — wie das Erreichen des letzten Knotens der Liste (das Annehmen, dass der letzte Knoten als getrennte Knotenverweisung in der Listenstruktur nicht aufrechterhalten wird), oder Entdeckung eines Knotens, der eine gegebene Gegebenheit oder Auffinden des Platzes enthält, wo ein neuer Knoten eingefügt werden sollte — Abtastung am meisten oder alle Listenelemente verlangen.

Geschichte

Verbundene Listen wurden in 1955-56 von Allen Newell, Cliff Shaw und Herbert Simon an RAND Corporation als die primäre Datenstruktur für ihre Informationsverarbeitungssprache entwickelt. IPL wurde von den Autoren verwendet, um mehrere frühe Programme der künstlichen Intelligenz, einschließlich der Logiktheorie-Maschine, das Allgemeine Problem Solver und ein Computerschachprogramm zu entwickeln. Berichte über ihre Arbeit sind in ZORN-Transaktionen auf der Informationstheorie 1956 und mehreren Konferenzverhandlungen von 1957 bis 1959, einschließlich Verhandlungen der Gemeinsamen Westcomputerkonferenz 1957 und 1958 und Informationsverarbeitung (Verhandlungen der ersten UNESCO Internationale Konferenz für die Informationsverarbeitung) 1959 erschienen. Das jetzt klassische Diagramm, das aus Blöcken besteht, die Listenknoten mit Pfeilen vertreten, die zu aufeinander folgenden Listenknoten hinweisen, erscheint in der "Programmierung der Logiktheorie-Maschine" durch Newell und Shaw in Proc. WJCC, Februar 1957. Newell und Simon wurden mit dem ACM Turing Preis 1975 anerkannt, für grundlegende Beiträge zur künstlichen Intelligenz, der Psychologie des menschlichen Erkennens und Listenverarbeitung "geleistet zu haben".

Das Problem der maschinellen Übersetzung für die Verarbeitung der natürlichen Sprache hat Victor Yngve am Institut von Massachusetts für die Technologie (MIT) dazu gebracht, verbundene Listen als Datenstrukturen auf seiner COMIT Programmiersprache für die Computerforschung im Feld der Linguistik zu verwenden. Ein Bericht über diese Sprache betitelt "Eine Programmiersprache für die mechanische Übersetzung" ist in der Mechanischen Übersetzung 1958 erschienen.

LISPELN, für Listenverarbeiter eintretend, wurde von John McCarthy 1958 geschaffen, während er an MIT war und 1960 er sein Design in einer Zeitung in den Kommunikationen des ACM, betitelt "Rekursive Funktionen von Symbolischen Ausdrücken und Ihrer Berechnung durch die Maschine, erster Teil" veröffentlicht hat. Eine der Hauptdatenstrukturen des LISPELNS ist die verbundene Liste.

Bis zum Anfang der 1960er Jahre, des Dienstprogrammes sowohl von verbundenen Listen als auch von Sprachen, die diese Strukturen verwenden, weil wurde ihre primäre Datendarstellung gut gegründet. Bert Green von MIT Laboratorium von Lincoln hat einen Übersichtsartikel betitelt "Computersprachen für die Symbol-Manipulation" in ZORN-Transaktionen auf Menschlichen Faktoren in der Elektronik im März 1961 veröffentlicht, die die Vorteile der verbundenen Listenannäherung zusammengefasst hat. Ein späterer Übersichtsartikel, "Ein Vergleich von listenbearbeitenden Computersprachen" durch Bobrow und Raphael, ist in Kommunikationen des ACM im April 1964 erschienen.

Mehrere Betriebssysteme, die von Technischen Systemberatern (ursprünglich des Westens Lafayette Indiana, und später des Kapelle-Hügels, North Carolina) entwickelt sind, haben einzeln verbundene Listen als Dateistrukturen verwendet. Ein Verzeichniszugang hat zum ersten Sektor einer Datei hingewiesen, und folgende Teile der Datei wurden durch das Überqueren von Zeigestöcken gelegen. Systeme mit dieser eingeschlossenen Technik Beugen (für Motorola 6800 Zentraleinheit), beugen (dieselbe Zentraleinheit), und Flex9 (für Motorola 6809 Zentraleinheit) mini. Eine Variante, die durch TSC dafür entwickelt ist und durch das Rauch-Signal auf den Markt gebracht ist, das in Kalifornien, verwendete doppelt verbundene Listen auf dieselbe Weise Sendet.

Der TSS/360 Betriebssystem, das von IBM für das System 360/370 Maschinen entwickelt ist, hat eine doppelte verbundene Liste für ihren Dateisystemkatalog verwendet. Die Verzeichnisstruktur war Unix ähnlich, wo ein Verzeichnis Dateien und/oder andere Verzeichnisse enthalten und sich bis zu jede Tiefe ausstrecken konnte. Ein Dienstprogramm-Floh wurde geschaffen, um Dateisystemprobleme nach einem Unfall zu befestigen, seitdem modifizierte Teile des Dateikatalogs manchmal im Gedächtnis waren, als ein Unfall vorgekommen ist. Probleme wurden durch das Vergleichen des nachschicket und der rückwärts gerichteten Verbindungen für die Konsistenz entdeckt. Wenn eine Vorwärtsverbindung korrupt war, dann wenn eine rückwärts gerichtete Verbindung zum angesteckten Knoten gefunden wurde, wurde die Vorwärtsverbindung auf den Knoten mit der rückwärts gerichteten Verbindung gesetzt. Eine humorvolle Anmerkung in der Quelle codiert, wo dieses Dienstprogramm festgesetzt angerufen wurde, "Weiß jeder, dass ein Flohkragen Programmfehler in Katzen loswird".

Grundlegende Konzepte und Nomenklatur

Jede Aufzeichnung einer verbundenen Liste wird häufig ein Element oder Knoten genannt.

Das Feld jedes Knotens, der die Adresse des folgenden Knotens enthält, wird gewöhnlich die folgende Verbindung' oder den folgenden Zeigestock genannt'. Die restlichen Felder sind als die Daten, die Information, der Wert, die Ladung oder die Nutzlast-Felder bekannt.

Der Kopf einer Liste ist sein erster Knoten. Der Schwanz einer Liste kann sich entweder auf den Rest der Liste nach dem Kopf, oder zum letzten Knoten in der Liste beziehen. Im Lispeln und einigen abgeleiteten Sprachen kann der folgende Knoten genannt werden der cdr (ausgesprochen hat - er gekonnt) der Liste, während die Nutzlast des Hauptknotens das Auto genannt werden kann.

Postschließfach-Analogie

Das Konzept einer verbundenen Liste kann durch eine einfache Analogie zu wirklichen Postschließfächern erklärt werden. Nehmen Sie an, dass Alice ein Spion ist, der einen codebook geben möchte, um Sich Auf und ab zu bewegen, indem er es in einem Postschließfach stellt und ihm dann den Schlüssel gibt. Jedoch ist das Buch zu dick, um ein einzelnes Postschließfach einzufügen, also stattdessen teilt sie das Buch in zwei Hälften und kauft zwei Postschließfächer. Im ersten Kasten stellt sie die erste Hälfte des Buches und eines Schlüssels zum zweiten Kasten, und im zweiten Kasten stellt sie die zweite Hälfte des Buches. Sie gibt dann Bob einen Schlüssel zum ersten Kasten. Egal wie groß das Buch ist, kann dieses Schema zu jeder Zahl von Kästen erweitert werden, indem es immer den Schlüssel zum folgenden gestellt wird, schließen den vorherigen Kasten ein.

In dieser Analogie entsprechen die Kästen Elementen oder Knoten, die Schlüssel entsprechen Zeigestöcken, und das Buch selbst ist die Daten. Der Bob gegebene Schlüssel ist der Hauptzeigestock, während diejenigen, die in den Kästen versorgt sind, folgende Zeigestöcke sind. Das Schema, ist wie beschrieben, oben eine einzeln verbundene Liste (sieh unten).

Geradlinige und kreisförmige Listen

Im letzten Knoten einer Liste enthält das Verbindungsfeld häufig eine ungültige Verweisung, ein spezieller Wert hat gepflegt, den Mangel an weiteren Knoten anzuzeigen. Eine weniger allgemeine Tagung ist, es zum ersten Knoten der Liste hinweisen zu lassen; in diesem Fall, wie man sagt, ist die Liste kreisförmig oder kreisförmig verbunden; sonst, wie man sagt, ist es offen oder geradlinig.

Einzeln, doppelt, und multiplizieren verbundene Listen

Einzeln verbundene Listen enthalten Knoten, die ein Datenfeld sowie ein folgendes Feld haben, das zum folgenden Knoten in der verbundenen Liste hinweist.

In einer doppelt verbundenen Liste enthält jeder Knoten, außer der Verbindung des folgenden Knotens, ein zweites Verbindungsfeld, das zum vorherigen Knoten in der Folge hinweist. Die zwei Verbindungen können fortgeschritten (s) und umgekehrt, oder als nächstes und prev (ious) genannt werden.

Eine als XOR-Verbindung bekannte Technik erlaubt einer doppelt verbundenen Liste, mit einem einzelnen Verbindungsfeld in jedem Knoten durchgeführt zu werden. Jedoch verlangt diese Technik die Fähigkeit, Bit-Operationen auf Adressen zu tun, und kann deshalb auf einigen höheren Programmiersprachen nicht verfügbar sein.

In einem Multiplizieren der verbundenen Liste enthält jeder Knoten zwei oder mehr Verbindungsfelder, jedes Feld, das wird pflegt, denselben Satz von Datenaufzeichnungen in einer verschiedenen Ordnung (z.B, namentlich, durch die Abteilung, durch das Geburtsdatum, usw.) zu verbinden. (Während doppelt verbundene Listen als spezielle Fälle dessen gesehen werden können, multiplizieren verbundene Liste, die Tatsache, dass die zwei Ordnungen gegenüber einander sind, führt zu einfacheren und effizienteren Algorithmen, so werden sie gewöhnlich als ein getrennter Fall behandelt.)

Im Fall von einem Rundschreiben hat doppelt Liste verbunden, die einzige Änderung, die vorkommt, ist, dass Ende oder "Schwanz", vorerwähnter Liste zurück mit der Vorderseite oder "Kopf" von der Liste und umgekehrt verbunden wird.

Wächter-Knoten

In einigen Durchführungen können ein Extrawächter oder Scheinknoten vor der ersten Datenaufzeichnung und/oder nach der letzten hinzugefügt werden. Diese Tagung vereinfacht und beschleunigt einige listenbehandelnde Algorithmen durch das Sicherstellen, dass alle Verbindungen sicher dereferenced sein können, und dass jede Liste (sogar diejenige, die keine Datenelemente enthält) immer einen "ersten" und "letzten" Knoten hat.

Leere Listen

Eine leere Liste ist eine Liste, die keine Datenaufzeichnungen enthält. Das ist gewöhnlich dasselbe, sagend dass es Nullknoten hat. Wenn Wächter-Knoten verwendet werden, wie man gewöhnlich sagt, ist die Liste leer, wenn sie nur Wächter-Knoten hat.

Kuddelmuddel-Verbindung

Die Verbindungsfelder brauchen nicht physisch ein Teil der Knoten zu sein. Wenn die Datenaufzeichnungen in einer Reihe versorgt und durch ihre Indizes Verweise angebracht werden, kann das Verbindungsfeld in einer getrennten Reihe mit denselben Indizes wie die Datenaufzeichnungen versorgt werden.

Listengriffe

Da eine Verweisung auf den ersten Knoten Zugang zur ganzen Liste gibt, wird diese Verweisung häufig die Adresse, den Zeigestock oder den Griff der Liste genannt. Algorithmen, die verbundene Listen gewöhnlich manipulieren, bekommen solche Griffe zu den Eingangslisten und geben die Griffe in die resultierenden Listen zurück. Tatsächlich, im Zusammenhang solcher Algorithmen, bedeutet das Wort "Liste" häufig "Listengriff". In einigen Situationen, jedoch, kann es günstig sein, sich auf eine Liste durch einen Griff zu beziehen, der aus zwei Verbindungen besteht, auf seinen vor allen Dingen Knoten anspitzend.

Das Kombinieren von Alternativen

Die Alternativen, die oben verzeichnet sind, können auf fast jede Weise willkürlich verbunden werden, so kann man Rundschreiben haben, doppelt hat Listen ohne Wächter verbunden, Rundschreiben hat einzeln Listen mit Wächtern usw. verbunden.

Umtausche

Als mit den meisten Wahlen in der Computerprogrammierung und dem Design wird keiner Methode allen Verhältnissen gut angepasst. Eine verbundene Listendatenstruktur könnte gut in einem Fall arbeiten, aber Probleme in einem anderen verursachen. Das ist eine Liste von einigen der allgemeinen Umtausche, die mit verbundenen Listenstrukturen verbunden sind.

Verbundene Listen gegen die dynamische Reihe

Eine dynamische Reihe ist eine Datenstruktur, die alle Elemente aneinander grenzend im Gedächtnis zuteilt, und eine Zählung der aktuellen Zahl der Elemente behält. Wenn der für die dynamische Reihe vorbestellte Raum überschritten wird, wird es neu zugeteilt und (vielleicht), eine teure Operation kopiert.

Verbundene Listen haben mehrere Vorteile gegenüber der dynamischen Reihe. Einfügung oder Auswischen eines Elements an einem spezifischen Punkt einer Liste, annehmend, dass wir einen Zeigestock zum Knoten haben (bevor derjenige, der, oder vor dem Einfügungspunkt zu entfernen ist) bereits, eine unveränderlich-malige Operation ist, wohingegen die Einfügung in einer dynamischen Reihe aufs Geratewohl Positionen bewegende Hälfte der Elemente durchschnittlich und aller Elemente im Grenzfall verlangen wird. Während man ein Element von einer Reihe in der unveränderlichen Zeit "löschen" kann, indem man irgendwie sein Ablagefach als "frei" kennzeichnet, verursacht das Zersplitterung, die die Leistung der Wiederholung behindert.

Außerdem willkürlich können viele Elemente in eine verbundene Liste, beschränkt nur durch das verfügbare Gesamtgedächtnis eingefügt werden; während eine dynamische Reihe schließlich seine zu Grunde liegende Reihe-Datenstruktur voll füllen wird und — eine teure Operation, diejenige wird neu zuteilen müssen, die nicht sogar möglich sein kann, wenn Gedächtnis gebrochen wird, obwohl die Kosten der Wiederzuteilung über Einfügungen durchschnittlich sein können, und die Kosten einer Einfügung wegen der Wiederzuteilung würden noch O (1) amortisiert. Das hilft mit dem Befestigen von Elementen am Ende der Reihe, aber das Einfügen in (oder das Entfernen von) mittlere Positionen trägt noch untersagende Kosten wegen Daten, die sich bewegen, um Berührung aufrechtzuerhalten. Eine Reihe, von der viele Elemente entfernt werden, kann auch in der Größe angepasst werden müssen, um zu vermeiden, zu viel Raum zu vergeuden.

Andererseits erlaubt dynamische Reihe (sowie Reihe-Datenstrukturen der festen Größe) unveränderlich-maligen zufälligen Zugang, während verbundene Listen nur folgenden Zugang zu Elementen erlauben. Einzeln verbundene Listen können nur tatsächlich in einer Richtung überquert werden. Das macht verbundene Listen unpassend für Anwendungen, wo es nützlich ist, ein Element durch seinen Index schnell wie heapsort nachzuschlagen. Der folgende Zugang auf der Reihe und dynamischen Reihe ist auch schneller als auf verbundenen Listen auf vielen Maschinen, weil sie optimale Gegend der Verweisung haben und so guten Gebrauch des Datenversteckens machen.

Ein anderer Nachteil von verbundenen Listen ist die für Verweisungen erforderliche Extralagerung, der sie häufig unpraktisch für Listen von kleinen Datensachen wie Charaktere oder Boolean-Werte macht, weil die Lagerung oben für die Verbindungen durch einen Faktor zwei oder mehr die Größe der Daten zu weit gehen kann. Im Gegensatz verlangt eine dynamische Reihe nur den Raum für die Daten selbst (und ein sehr kleiner Betrag von Kontrolldaten). Es kann auch, und mit einem naiven Verteiler langsam, verschwenderisch sein, um Gedächtnis getrennt für jedes neue Element, ein Problem allgemein gelöste Verwenden-Speicherlachen zuzuteilen.

Einige hybride Lösungen versuchen, die Vorteile der zwei Darstellungen zu verbinden. Entrollte verbundene Listen versorgen mehrere Elemente in jedem Listenknoten, Leistung des geheimen Lagers vergrößernd, während sie Gedächtnis oben für Verweisungen vermindern. Das CDR Codieren tut beide diese ebenso, durch das Ersetzen von Verweisungen durch die wirklichen Verweise angebrachten Daten, der sich vom Ende der Verweise anbringenden Aufzeichnung ausstreckt.

Ein gutes Beispiel, das das Pro und Kontra hervorhebt, dynamische Reihe gegen verbundene Listen zu verwenden, ist durch das Einführen eines Programms, das das Problem von Josephus auflöst. Das Problem von Josephus ist eine Wahlmethode, die arbeitet, indem sie eine Gruppe des Menschenstandplatzes in einem Kreis gehabt wird. An einer vorher bestimmten Person anfangend, zählen Sie um den Kreis n Zeiten auf. Sobald Sie die n-te Person erreichen, sie aus dem Kreis nehmen und die Mitglieder der Kreis schließen lassen. Dann die Zählung um den Kreis dieselben n Zeiten und Wiederholung der Prozess, bis nur eine Person verlassen wird. Diese Person gewinnt die Wahl. Das zeigt die Kräfte und Schwächen einer verbundenen Liste gegen eine dynamische Reihe, weil, wenn Sie die Leute als verbundene Knoten in einem Rundschreiben ansehen, Liste dann verbunden hat, zeigt es, wie leicht die verbundene Liste im Stande ist, Knoten zu löschen (weil es nur die Verbindungen zu den verschiedenen Knoten umordnen muss). Jedoch wird die verbundene Liste bei der Entdeckung der folgenden Person schwach sein umzuziehen und wird die Liste durchsuchen müssen, bis es diese Person findet. Eine dynamische Reihe wird andererseits beim Löschen von Knoten schwach sein (oder Elemente), weil es einen Knoten nicht entfernen kann, ohne alle Elemente die Liste durch eine individuell auszuwechseln. Jedoch ist es außergewöhnlich leicht, die n-te Person im Kreis zu finden, indem es in ihnen durch ihre Position in der Reihe direkt Verweise angebracht wird.

Die Liste, die Problem aufreiht, betrifft die effiziente Konvertierung einer verbundenen Listendarstellung in eine Reihe. Obwohl trivial, für einen herkömmlichen Computer, dieses Problem durch einen parallelen Algorithmus behebend, wird kompliziert und ist das Thema von viel Forschung gewesen.

Ein erwogener Baum hat ähnliche Speicherzugriffsmuster und Raum oben zu einer verbundenen Liste, während er das viel effizientere Indexieren erlaubt, O nehmend (loggen Sie n) die Zeit statt O (n) für einen zufälligen Zugang. Jedoch sind Einfügung und Auswischen-Operationen wegen der Gemeinkosten von Baummanipulationen teurer, um Gleichgewicht aufrechtzuerhalten. Effiziente Schemas bestehen für Bäume, um sich im Fast-Gleichgewichtszustand, wie AVL Bäume oder rot-schwarze Bäume automatisch zu unterstützen.

Einzeln verbundene geradlinige Listen gegen andere Listen

Während doppelt verbunden, und/oder sind kreisförmige Listen im Vorteil einzeln hat geradlinige Listen verbunden, geradlinige Listen bieten einige Vorteile an, die sie vorzuziehend in einigen Situationen machen.

Erstens einmal ist eine einzeln verbundene geradlinige Liste eine rekursive Datenstruktur, weil sie einen Zeigestock zu einem kleineren Gegenstand desselben Typs enthält. Deshalb haben viele Operationen auf einzeln verbundenen geradlinigen Listen (wie das Mischen von zwei Listen oder das Aufzählen der Elemente in umgekehrter Reihenfolge) häufig sehr einfache rekursive Algorithmen, die viel einfacher sind als jede Lösung mit wiederholenden Befehlen. Während man jene rekursiven Lösungen an doppelt verbundene und kreisförmig verbundene Listen anpassen kann, brauchen die Verfahren allgemein Extraargumente und mehr komplizierte Grundfälle.

Geradlinige einzeln verbundene Listen erlauben auch Schwanz-Teilen, den Gebrauch eines allgemeinen Endteils der Subliste als der Endteil von zwei verschiedenen Listen. Insbesondere wenn ein neuer Knoten am Anfang einer Liste hinzugefügt wird, bleibt die ehemalige Liste verfügbar als der Schwanz des neuen — ein einfaches Beispiel einer beharrlichen Datenstruktur. Wieder ist das mit den anderen Varianten nicht wahr: Ein Knoten kann zwei verschiedenem Rundschreiben oder doppelt verbundenen Listen nie gehören.

Insbesondere Endwächter-Knoten können unter einzeln verbundenen nichtkreisförmigen Listen geteilt werden. Man kann sogar denselben Endwächter-Knoten für jede solche Liste verwenden. Im Lispeln, zum Beispiel, endet jede richtige Liste mit einer Verbindung zu einem speziellen Knoten, der dadurch angezeigt ist, oder, dessen und Verbindungen zu sich hinweisen. So kann ein Lispeln-Verfahren oder jeder Liste sicher nehmen.

Tatsächlich werden die Vorteile der Fantasievarianten häufig auf die Kompliziertheit der Algorithmen beschränkt, nicht in ihrer Leistungsfähigkeit. Mit einer kreisförmigen Liste kann gewöhnlich insbesondere durch eine geradlinige Liste zusammen mit zwei Variablen wettgeeifert werden, die zu vor allen Dingen Knoten an keinen Extrakosten hinweisen.

Doppelt verbunden gegen einzeln verbundenen

Doppelt verbundene Listen verlangen mehr Raum pro Knoten (wenn man XOR-Verbindung nicht verwendet), und ihre elementaren Operationen teurer sind; aber sie sind häufig leichter zu manipulieren, weil sie folgenden Zugang zur Liste in beiden Richtungen erlauben. In einer doppelt verbundenen Liste kann man einfügen oder einen Knoten in einer unveränderlichen Zahl von Operationen gegeben nur dass die Adresse des Knotens löschen. Um in einer einzeln verbundenen Liste dasselbe zu machen, muss man die Adresse des Zeigestocks zu diesem Knoten haben, der irgendein der Griff für die ganze Liste (im Falle des ersten Knotens) oder das Verbindungsfeld im vorherigen Knoten ist. Einige Algorithmen verlangen Zugang in beiden Richtungen. Andererseits erlauben doppelt verbundene Listen Schwanz-Teilen nicht und können als beharrliche Datenstrukturen nicht verwendet werden.

Kreisförmig verbunden gegen geradlinig verbundenen

Eine kreisförmig verbundene Liste kann eine natürliche Auswahl sein, Reihe zu vertreten, die, z.B die Ecken eines Vielecks, eine Lache von Puffern natürlich kreisförmig ist, die verwendet und in der FIFO-Ordnung oder einer Reihe von Prozessen veröffentlicht werden, die in der Ordnung des gemeinsamen Antrags zeitgeteilt werden sollten. In diesen Anwendungen dient ein Zeigestock zu jedem Knoten als ein Griff der ganzen Liste.

Mit einer kreisförmigen Liste gibt ein Zeigestock zum letzten Knoten leichten Zugang auch zum ersten Knoten, durch den folgenden eine Verbindung. So in Anwendungen, die Zugang zu beiden Enden der Liste (z.B, in der Durchführung einer Warteschlange) verlangen, erlaubt eine kreisförmige Struktur, die Struktur durch einen einzelnen Zeigestock, statt zwei zu behandeln.

Eine kreisförmige Liste kann in zwei kreisförmige Listen, in der unveränderlichen Zeit, durch das Geben der Adressen des letzten Knotens jedes Stückes gespalten werden. Die Operation besteht im Tauschen des Inhalts der Verbindungsfelder jener zwei Knoten. Die Verwendung derselben Operation zu irgendwelchen zwei Knoten in zwei verschiedenen Listen schließt sich der zwei Liste in eine an. Dieses Eigentum vereinfacht außerordentlich einige Algorithmen und Datenstrukturen, wie der Viererkabelrand und Gesichtsrand.

Die einfachste Darstellung für eine leere kreisförmige Liste (wenn solch ein Ding Sinn hat) ist ein ungültiger Zeigestock, anzeigend, dass die Liste keine Knoten hat. Ohne diese Wahl müssen viele Algorithmen für diesen speziellen Fall prüfen, und es getrennt behandeln. Im Vergleich ist der Gebrauch der Null, um eine leere geradlinige Liste anzuzeigen, natürlicher und schafft häufig weniger spezielle Fälle.

Das Verwenden von Wächter-Knoten

Wächter-Knoten kann bestimmte Listenoperationen durch das Sicherstellen vereinfachen, dass die folgenden und/oder vorherigen Knoten für jedes Element bestehen, und dass sogar leere Listen mindestens einen Knoten haben. Man kann auch einen Wächter-Knoten am Ende der Liste mit einem passenden Datenfeld verwenden, um einige Tests des Endes der Liste zu beseitigen. Zum Beispiel, wenn die Abtastung der Liste, nach einem Knoten mit einem gegebenen Wert x suchend, das Datenfeld des Wächters auf x setzend, es unnötig macht, für das Ende der Liste innerhalb der Schleife zu prüfen. Ein anderes Beispiel ist das Mischen von zwei sortierten Listen: Wenn ihre Wächter Datenfelder auf +  setzen ließen, braucht die Wahl des folgenden Produktionsknotens das spezielle Berühren für leere Listen nicht.

Jedoch verbrauchen Wächter-Knoten Extraraum (besonders in Anwendungen, die viele kurze Listen verwenden), und sie andere Operationen (wie die Entwicklung einer neuen leeren Liste) komplizieren können.

Jedoch, wenn die kreisförmige Liste bloß verwendet wird, um eine geradlinige Liste vorzutäuschen, kann man etwas von dieser Kompliziertheit vermeiden, indem man einen einzelnen Wächter-Knoten zu jeder Liste, zwischen dem letzten und den ersten Datenknoten hinzufügt. Mit dieser Tagung besteht eine leere Liste aus dem Wächter-Knoten allein, zu sich über die Verbindung des folgenden Knotens hinweisend. Der Listengriff sollte dann ein Zeigestock zum letzten Datenknoten vor dem Wächter sein, wenn die Liste nicht leer ist; oder dem Wächter selbst, wenn die Liste leer ist.

Derselbe Trick kann verwendet werden, um das Berühren einer doppelt verbundenen geradlinigen Liste zu vereinfachen, dadurch sich zu verwandeln hat es in ein Rundschreiben doppelt Liste mit einem einzelnen Wächter-Knoten verbunden. Jedoch, in diesem Fall, sollte der Griff ein einzelner Zeigestock zum Scheinknoten selbst sein.

Verbundene Listenoperationen

Wenn

man verbundene Listen im Platz manipuliert, muss Sorge genommen werden, um Werte nicht zu verwenden, die Sie in vorherigen Anweisungen ungültig gemacht haben. Das macht Algorithmen, um verbundene etwas feine Listenknoten einzufügen oder zu löschen. Diese Abteilung gibt Pseudocode, um Knoten von einzeln, doppelt, und kreisförmig verbundene Listen im Platz hinzuzufügen oder zu entfernen. Überall werden wir ungültig verwenden, um uns auf einen Anschreiber des Endes der Liste oder Wächter zu beziehen, der auf mehrere Weisen durchgeführt werden kann.

Geradlinig verbundene Listen

Einzeln verbundene Listen

Unsere Knotendatenstruktur wird zwei Felder haben. Wir behalten auch eine Variable firstNode, der immer zum ersten Knoten in der Liste hinweist, oder für eine leere Liste ungültig ist.

registrieren Sie Knoten {\

Daten;//Die Daten, die im Knoten versorgen werden

Knoten als nächstes//Eine Verweisung auf den folgenden Knoten, der für den letzten Knoten ungültig

ist

}\

registrieren Sie Liste {\

Knoten firstNode//weist zum ersten Knoten der Liste hin; ungültig für die leere Liste

}\

Das Traversal einer einzeln verbundenen Liste ist einfach, am ersten Knoten und im Anschluss an jede folgende Verbindung beginnend, bis wir zum Ende kommen:

Knoten: = list.firstNode

während Knoten nicht ungültiger

(tun Sie etwas mit node.data)

Knoten: = node.next

Der folgende Code fügt einen Knoten nach einem vorhandenen Knoten in einer einzeln verbundenen Liste ein. Das Diagramm zeigt, wie es arbeitet. Wenn man einen Knoten bevor einfügt, kann ein vorhandener nicht direkt getan werden; statt dessen muss man den vorherigen Knoten nachgehen und einen Knoten danach einfügen.

fungieren Sie insertAfter (Knotenknoten, Knoten newNode)//fügen newNode nach dem Knoten ein

newNode.next: = node.next

node.next: = newNode

Das Einfügen am Anfang der Liste verlangt eine getrennte Funktion. Das verlangt aktualisierenden firstNode.

fungieren Sie insertBeginning (Listenliste, Knoten newNode)//Einsatz-Knoten vor dem aktuellen ersten Knoten

newNode.next: = list.firstNode

list.firstNode: = newNode

Ähnlich haben wir Funktionen, für den Knoten nach einem gegebenen Knoten zu entfernen, und für einen Knoten vom Anfang der Liste zu entfernen. Das Diagramm demonstriert den ersteren. Um einen besonderen Knoten zu finden und zu entfernen, muss man wieder das vorherige Element nachgehen.

fungieren Sie removeAfter (Knotenknoten)//entfernen Knoten vorbei an diesem

obsoleteNode: = node.next

node.next: = node.next.next

zerstören Sie obsoleteNode

fungieren Sie removeBeginning (Listenliste)//entfernen den ersten Knoten

obsoleteNode: = list.firstNode

list.firstNode: = list.firstNode.next//weisen vorbei am gelöschten Knoten hin

zerstören Sie obsoleteNode

Bemerken Sie dass Sätze dazu, wenn Sie den letzten Knoten in der Liste entfernen.

Da wir umgekehrt, effizient nicht wiederholen können oder

Das Befestigen einer verbundener Liste zu einem anderen kann ineffizient sein, wenn eine Verweisung auf den Schwanz als ein Teil der Listenstruktur nicht behalten wird, weil wir die komplette erste Liste überqueren müssen, um den Schwanz zu finden, und dann die zweite Liste daran anzuhängen. So, wenn zwei geradlinig verbundene Listen jede der Länge sind, hat das Listenbefestigen asymptotische Zeitkompliziertheit dessen. In der Lispeln-Sprachfamilie wird das Listenbefestigen durch das Verfahren zur Verfügung gestellt.

Viele der speziellen Fälle von verbundenen Listenoperationen können durch das Umfassen eines Scheinelements an der Front der Liste beseitigt werden. Das stellt sicher, dass es keine speziellen Fälle für den Anfang der Liste gibt und beide und unnötig macht. In diesem Fall werden die ersten nützlichen Daten in der Liste daran gefunden.

Kreisförmig verbundene Liste

In einer kreisförmig verbundenen Liste werden alle Knoten in einem dauernden Kreis verbunden, ohne ungültig zu verwenden. Für Listen mit einer Vorderseite und einem Rücken (wie eine Warteschlange) versorgt man eine Verweisung auf den letzten Knoten in der Liste. Der folgende Knoten nach dem letzten Knoten ist der erste Knoten. Elemente können zum Rücken der Liste hinzugefügt und von der Vorderseite in der unveränderlichen Zeit entfernt werden.

Kreisförmig verbundene Listen können entweder einzeln oder doppelt verbunden werden.

Beide Typen kreisförmig verbundener Listen ziehen aus der Fähigkeit einen Nutzen, die volle Liste zu überqueren, die an jedem gegebenen Knoten beginnt. Das erlaubt uns häufig zu vermeiden, firstNode und lastNode zu versorgen, obwohl, wenn die Liste leer sein kann, wir eine spezielle Darstellung für die leere Liste wie eine lastNode Variable brauchen, die zu einem Knoten in der Liste hinweist oder ungültig ist, wenn es leer ist; wir verwenden solch einen lastNode hier. Diese Darstellung vereinfacht bedeutsam das Hinzufügen und Entfernen von Knoten mit einer nichtleeren Liste, aber leere Listen sind dann ein spezieller Fall.

Algorithmen

Das Annehmen, dass someNode ein Knoten in einem nichtleeren Rundschreiben einzeln ist, hat Liste verbunden, dieser Code wiederholt durch diese Liste, die mit someNode anfängt:

Funktion wiederholt (someNode)

wenn someNode  ungültiger

Knoten: = someNode

tun Sie

tun Sie etwas mit node.value

Knoten: = node.next

während Knoten  someNode

Bemerken Sie, dass der Test, "während Knoten  someNode" am Ende der Schleife sein muss. Wenn der Test zum Anfang der Schleife bewegt würde, würde das Verfahren scheitern, wann auch immer die Liste nur einen Knoten hatte.

Diese Funktion fügt einen Knoten "newNode" in die verbundene Liste eines Rundschreibens nach einem gegebenen Knoten "Knoten" ein. Wenn "Knoten" ungültig ist, nimmt er an, dass die Liste leer ist.

fungieren Sie insertAfter (Knotenknoten, Knoten newNode)

wenn Knoten = ungültiger

newNode.next: = newNode

sonst

newNode.next: = node.next

node.next: = newNode

Nehmen Sie an, dass "L" eine Variable ist, die zum letzten Knoten der verbundenen Liste eines Rundschreibens hinweist (oder ungültig, wenn die Liste leer ist). "Um newNode" am Ende der Liste anzuhängen, kann man tun

insertAfter (L, newNode)

L: = newNode

"Um newNode" am Anfang der Liste einzufügen, kann man tun

insertAfter (L, newNode)

wenn L = ungültiger

L: = newNode

Verbundene Listen mit der Reihe von Knoten

Sprachen, die keinen Typ der Verweisung unterstützen, können noch Verbindungen durch das Ersetzen von Zeigestöcken durch Reihe-Indizes schaffen. Die Annäherung soll eine Reihe von Aufzeichnungen behalten, wo jede Aufzeichnung Felder der ganzen Zahl hat, die den Index des folgenden (und vielleicht vorherig) Knoten in der Reihe anzeigen. Nicht alle Knoten in der Reihe müssen verwendet werden. Wenn Aufzeichnungen auch nicht unterstützt werden, Reihe anpassen, kann häufig stattdessen verwendet werden.

Als ein Beispiel, denken Sie die folgende verbundene Listenaufzeichnung, die Reihe statt Zeigestöcke verwendet:

registrieren Sie Zugang {\

ganze Zahl als nächstes;//Index des folgenden Zugangs in der Reihe

ganze Zahl prev;//vorheriger Zugang (wenn doppelt verbunden)

Schnur-Name;

echtes Gleichgewicht;

}\

Durch das Schaffen einer Reihe dieser Strukturen und einer Variable der ganzen Zahl, um den Index des ersten Elements zu versorgen, kann eine verbundene Liste gebaut werden:

ganze Zahl listHead

Zugang-Aufzeichnungen [1000]

Verbindungen zwischen Elementen werden durch das Stellen des Reihe-Index des folgenden (oder vorherig) Zelle ins Folgende Feld oder Feld von Prev innerhalb eines gegebenen Elements gebildet. Zum Beispiel:

Im obengenannten Beispiel, würde auf 2, die Position des ersten Zugangs in der Liste gesetzt. Bemerken Sie, dass Zugang 3 und 5 bis 7 nicht ein Teil der Liste ist. Diese Zellen sind für irgendwelche Hinzufügungen zur Liste verfügbar. Durch das Schaffen einer Variable der ganzen Zahl konnte eine freie Liste geschaffen werden, um das nachzugehen, welche Zellen verfügbar sind. Wenn alle Einträge im Gebrauch sind, würde die Größe der Reihe vergrößert werden müssen, oder einige Elemente würden gelöscht werden müssen, bevor neue Einträge in der Liste versorgt werden konnten.

Der folgende Code würde die Liste und die Anzeigenamen und das Kontogleichgewicht überqueren:

i: = listHead

während ich  0//Schleife durch die Liste

drucken Sie i, Aufzeichnungen [ich].name, Aufzeichnungen [ich].balance//drucken Zugang

i: = Aufzeichnungen [ich].next

Wenn, mit einer Wahl konfrontierend, die Vorteile dieser Annäherung einschließen:

• Die verbundene Liste ist relokatierbar, bedeutend, dass sie im Gedächtnis nach Wunsch bewegt werden kann, und sie auch für die Lagerung auf der Platte oder Übertragung über ein Netz schnell und direkt in Fortsetzungen veröffentlicht werden kann.
• Besonders für eine kleine Liste können Reihe-Indizes bedeutsam weniger Raum besetzen als ein voller Zeigestock auf vielen Architekturen.
• Die Gegend der Verweisung kann durch das Halten der Knoten zusammen im Gedächtnis und durch das periodische Umordnen von ihnen verbessert werden, obwohl das auch in einer Gemischtwarenhandlung getan werden kann.
• Naive dynamische Speicherverteiler können einen übermäßigen Betrag der Oberlagerung für jeden zugeteilten Knoten erzeugen; fast keine Zuteilung oben wird pro Knoten in dieser Annäherung übernommen.
• Das Greifen eines Zugangs von einer vorzugeteilten Reihe ist schneller als das Verwenden dynamischer Speicherzuteilung für jeden Knoten, da dynamische Speicherzuteilung normalerweise eine Suche nach einem freien Speicherblock der gewünschten Größe verlangt.

Diese Annäherung hat einen Hauptnachteil jedoch: Es schafft und führt einen privaten Speicherraum für seine Knoten. Das führt zu den folgenden Problemen:

• Es vergrößert Kompliziertheit der Durchführung.
• Das Wachsen einer großen Reihe, wenn es voll ist, kann schwierig oder unmöglich sein, wohingegen die Entdeckung des Raums für einen neuen verbundenen Listenknoten in einer großen, allgemeinen Speicherlache leichter sein kann.
• Das Hinzufügen von Elementen zu einer dynamischen Reihe wird gelegentlich (wenn es voll ist), unerwartet nehmen geradlinig (O (n)) statt der unveränderlichen Zeit (obwohl es noch eine amortisierte Konstante ist).
• Das Verwenden einer allgemeinen Speicherlache verlässt mehr Gedächtnis für andere Daten, wenn die Liste kleiner ist als erwartet, oder wenn viele Knoten befreit werden.

Aus diesen Gründen wird diese Annäherung für Sprachen hauptsächlich verwendet, die dynamische Speicherzuteilung nicht unterstützen. Diese Nachteile werden auch gelindert, wenn die maximale Größe der Liste zurzeit bekannt ist, wird die Reihe geschaffen.

Sprachunterstützung

Viele Programmiersprachen wie Lispeln und Schema haben Listen einzeln verbunden, die darin gebaut sind. Auf vielen funktionellen Sprachen werden diese Listen von Knoten gebaut, jeder hat ein Lernen genannt oder lernt Zelle. Das Lernen hat zwei Felder: das Auto, eine Verweisung auf die Daten für diesen Knoten, und der cdr, eine Verweisung auf den folgenden Knoten. Obwohl Zellen lernt, kann verwendet werden, um andere Datenstrukturen zu bauen, das ist ihr primärer Zweck.

Auf Sprachen, die abstrakte Datentypen oder Schablonen, verbundene Liste unterstützen, sind ADTs oder Schablonen verfügbar, um verbundene Listen zu bauen. Auf anderen Sprachen werden verbundene Listen normalerweise mit Verweisungen zusammen mit Aufzeichnungen gebaut.

Innere und äußerliche Lagerung

Wenn

man eine verbundene Liste baut, konfrontiert man mit der Wahl dessen, ob man die Daten der Liste direkt in den verbundenen Listenknoten, genannt innere Lagerung versorgt, oder bloß eine Verweisung auf die Daten, genannt Außenlagerung zu versorgen. Innere Lagerung ist im Vorteil, Zugang zu den Daten effizienter zu machen, weniger Lagerung insgesamt verlangend, besser Gegend der Verweisung habend, und Speichermanagement für die Liste (seine Daten vereinfachend, wird zugeteilt und deallocated zur gleichen Zeit als die Listenknoten).

Außenlagerung ist andererseits im Vorteil, darin allgemeiner zu sein, dieselbe Datenstruktur und Maschinencode können für eine verbundene Liste verwendet werden, egal was die Größe der Daten ist. Es macht es auch leicht, dieselben Daten in vielfache verbundene Listen zu legen. Obwohl mit der inneren Lagerung dieselben Daten in vielfache Listen durch das Umfassen vielfacher folgender Verweisungen in der Knotendatenstruktur gelegt werden können, würde es dann notwendig sein, getrennte Routinen zu schaffen, um auf jedem Feld gestützte Zellen hinzuzufügen oder zu löschen. Es ist möglich, zusätzliche verbundene Listen von Elementen zu schaffen, die innere Lagerung durch das Verwenden der Außenlagerung verwenden, und die Zellen der zusätzlichen verbundenen Listen zu haben, Verweisungen auf die Knoten der verbundenen Liste versorgt, die die Daten enthält.

Im Allgemeinen, wenn eine Reihe von Datenstrukturen in vielfache verbundene Listen eingeschlossen werden muss, ist Außenlagerung die beste Annäherung. Wenn eine Reihe von Datenstrukturen in nur eine verbundene Liste eingeschlossen werden muss, dann ist innere Lagerung ein bisschen besser, wenn ein allgemeines verbundenes Listenpaket mit der Außenlagerung nicht verfügbar ist. Ebenfalls, wenn verschiedene Sätze von Daten, die in derselben Datenstruktur versorgt werden können, in eine einzelne verbundene Liste eingeschlossen werden sollen, dann würde innere Lagerung fein sein.

Eine andere Annäherung, die mit einigen Sprachen verwendet werden kann, ist mit habenden verschiedenen Datenstrukturen verbunden, aber alle haben die anfänglichen Felder, einschließlich des folgenden (und prev wenn doppelte verbundene Liste) Verweisungen in derselben Position. Nach dem Definieren getrennter Strukturen für jeden Typ von Daten kann eine allgemeine Struktur definiert werden, der die minimale Datenmenge enthält, die durch alle anderen Strukturen geteilt ist und am obersten (Anfang) der Strukturen enthalten ist. Dann können allgemeine Routinen geschaffen werden, die die minimale Struktur verwenden, um verbundene Listentyp-Operationen durchzuführen, aber getrennte Routinen können dann die spezifischen Daten behandeln. Diese Annäherung wird häufig in der Nachricht verwendet, die Routinen grammatisch analysiert, wo mehrere Typen von Nachrichten erhalten werden, aber der ganze Anfang mit demselben Satz von Feldern gewöhnlich einschließlich eines Feldes für den Nachrichtentyp. Die allgemeinen Routinen werden verwendet, um neue Nachrichten an eine Warteschlange hinzuzufügen, wenn sie erhalten werden, und sie von der Warteschlange entfernen, um die Nachricht zu bearbeiten. Das Nachrichtentyp-Feld wird dann verwendet, um die richtige Routine zu nennen, um den spezifischen Typ der Nachricht zu bearbeiten.

Beispiel der inneren und äußerlichen Lagerung

Nehmen Sie an, dass Sie eine verbundene Liste von Familien und ihren Mitgliedern haben schaffen wollen. Mit der inneren Lagerung könnte die Struktur wie der folgende aussehen:

registrieren Sie Mitglied {//Mitglied einer Familie

Mitglied als nächstes;

Schnur-Vorname;

Alter der ganzen Zahl;

}\

Rekordfamilie {//die Familie selbst

Familie als nächstes;

Schnur-Nachname;

Schnur-Adresse;

Mitglied-Mitglieder//Kopf der Liste von Mitgliedern dieser Familie

}\

Um eine ganze Liste von Familien und ihren Mitgliedern zu drucken, die innere Lagerung verwenden, konnten wir schreiben:

aFamily: = Familien//Anfang am Kopf von Familien verzeichnen

während aFamily  ungültig//Schleife durch die Liste von Familien

Druckinformation über die Familie

aMember: = aFamily.members//bekommen Kopf der Liste der Mitglieder dieser Familie

während aMember  ungültig//Schleife durch die Liste von Mitgliedern

Druckinformation über das Mitglied

aMember: = aMember.next

aFamily: = aFamily.next

Mit der Außenlagerung würden wir die folgenden Strukturen schaffen:

Rekordknoten {//allgemeine Verbindungsstruktur

Knoten als nächstes;

Zeigestock-Daten//allgemeiner Zeigestock für Daten am Knoten

}\

registrieren Sie Mitglied {//Struktur für das Familienmitglied

Schnur-Vorname;

Alter der ganzen Zahl

}\

Rekordfamilie {//Struktur für die Familie

Schnur-Nachname; Schnur-Adresse;

Knotenmitglieder//Kopf der Liste von Mitgliedern dieser Familie

}\

Um eine ganze Liste von Familien und ihren Mitgliedern zu drucken, die Außenlagerung verwenden, konnten wir schreiben:

famNode: = Familien//Anfang am Kopf von Familien verzeichnen

während famNode  ungültig//Schleife durch die Liste von Familien

aFamily: = (Familie) famNode.data//Extrakt-Familie vom Knoten

Druckinformation über die Familie

memNode: = aFamily.members//bekommen Liste von Familienmitgliedern

während memNode  ungültig//Schleife durch die Liste von Mitgliedern

aMember: = (Mitglied) memNode.data//Extrakt-Mitglied vom Knoten

Druckinformation über das Mitglied

memNode: = memNode.next

famNode: = famNode.next

Bemerken Sie, dass, wenn man Außenlagerung verwendet, ein Extraschritt erforderlich ist, um die Aufzeichnung aus dem Knoten herauszuziehen und es in den richtigen Datentyp zu werfen. Das ist, weil sowohl die Liste von Familien als auch die Liste von Mitgliedern innerhalb der Familie in zwei verbundenen Listen mit derselben Datenstruktur (Knoten) versorgt werden, und diese Sprache parametrische Typen nicht hat.

So lange die Zahl von Familien, denen ein Mitglied gehören kann, während der Übersetzung, innere feine Lagerungsarbeiten bekannt ist. Wenn, jedoch, ein Mitglied in eine beliebige Zahl von Familien, mit der spezifischen Zahl bekannt nur in der Durchlaufzeit eingeschlossen werden musste, würde Außenlagerung notwendig sein.

Suche beschleunigend

Die Entdeckung eines spezifischen Elements in einer verbundenen Liste, selbst wenn es normalerweise sortiert wird, verlangt O (n) Zeit (geradlinige Suche). Das ist einer der primären Nachteile von verbundenen Listen über andere Datenstrukturen. Zusätzlich zu den Varianten, die oben besprochen sind, sind unten zwei einfache Weisen, Suchzeit zu verbessern.

In einer nicht eingeordneten Liste ist ein einfacher heuristischer, um durchschnittliche Suchzeit zu vermindern, die heuristische Bewegung zur Vorderseite, der einfach ein Element zum Anfang der Liste bewegt, sobald es gefunden wird. Dieses Schema, das handlich ist, um einfache geheime Lager zu schaffen, stellt sicher, dass die am meisten kürzlich verwendeten Sachen auch am schnellsten sind, um wieder zu finden.

Eine andere einheitliche Methode soll eine verbundene Liste mit einer effizienteren Außendatenstruktur "mit einem Inhaltsverzeichnis versehen". Zum Beispiel kann man einen rot-schwarzen Baum oder Hash-Tabelle bauen, deren Elemente Verweisungen auf die verbundenen Listenknoten sind. Vielfach kann auf solche Indizes auf einer einzelnen Liste gebaut werden. Der Nachteil ist, dass diese Indizes eventuell jedes Mal aktualisiert werden müssen, wenn ein Knoten hinzugefügt oder entfernt wird (oder mindestens, bevor dieser Index wieder verwendet wird).

Zufällige Zugriffslisten

Eine zufällige Zugriffsliste ist eine Liste mit der Unterstützung für den schnellen zufälligen Zugang, um jedes Element in der Liste zu lesen oder zu modifizieren. Eine mögliche Durchführung ist ein Verdrehen binärer zufälliger Zugriffsliste mit dem verdrehen Binärzahl-System, das eine Liste von Bäumen mit speziellen Eigenschaften einschließt; das erlaubt Grenzfall unveränderliche Zeit geht Operationen und Grenzfall logarithmische Zeit zufälliger Zugang zu einem Element durch den Index/lernt). Zufällige Zugriffslisten können als beharrliche Datenstrukturen durchgeführt werden.

Zufällige Zugriffslisten können als unveränderliche verbundene Listen darin angesehen werden sie unterstützen ebenfalls denselben O (1) Kopf und Schwanz-Operationen.

Eine einfache Erweiterung auf zufällige Zugriffslisten ist die Minute-Liste, die eine zusätzliche Operation zur Verfügung stellt, die das minimale Element in der kompletten Liste in der unveränderlichen Zeit (ohne Veränderungskompliziertheiten) nachgibt.

Zusammenhängende Datenstrukturen

Sowohl Stapel als auch Warteschlangen werden häufig mit verbundenen Listen durchgeführt, und schränken einfach den Typ von Operationen ein, die unterstützt werden.

Die Hopser-Liste ist eine verbundene Liste, die mit Schichten von Zeigestöcken vermehrt ist, um über die große Anzahl von Elementen schnell zu springen, und dann zur folgenden Schicht hinunterzusteigen. Dieser Prozess geht unten zur untersten Schicht weiter, die die wirkliche Liste ist.

Ein binärer Baum kann als ein Typ der verbundenen Liste gesehen werden, wo die Elemente selbst verbundene Listen derselben Natur sind. Das Ergebnis besteht darin, dass jeder Knoten eine Verweisung auf den ersten Knoten von einer oder zwei anderen verbundenen Listen einschließen kann, die, zusammen mit ihrem Inhalt, die Subbäume unter diesem Knoten bilden.

Eine entrollte verbundene Liste ist eine verbundene Liste, in der jeder Knoten eine Reihe von Datenwerten enthält. Das führt zu verbesserter Leistung des geheimen Lagers, da mehr Listenelemente im Gedächtnis und reduzierten Gedächtnis oben aneinander grenzend sind, weil weniger metadata für jedes Element der Liste versorgt werden muss.

Eine Hash-Tabelle kann verbundene Listen verwenden, um die Ketten von Sachen dass Kuddelmuddel zu derselben Position in der Hash-Tabelle zu versorgen.

Ein Haufen teilt einige der Einrichtungseigenschaften einer verbundenen Liste, aber wird fast immer mit einer Reihe durchgeführt. Statt Verweisungen vom Knoten bis Knoten werden die folgenden und vorherigen Datenindizes mit dem Index der aktuellen Daten berechnet.

Eine selbstorganisierende Liste ordnet seine Knoten um, die auf einigen gestützt sind, heuristisch, der Suchzeiten für die Datenwiederauffindung durch das Halten von allgemein zugegriffenen Knoten an der Spitze der Liste reduziert.

Referenzen

Kommentare

Links

• Beschreibung aus dem Wörterbuch von Algorithmen und Datenstrukturen
• Einführung in verbundene Listen, Universitätsinformatik-Bibliothek von Stanford
• Verbundene Listenprobleme, Universitätsinformatik-Bibliothek von Stanford
• Offene Datenstrukturen - Kapitel 3 - Verbundene Listen
• Verbundene Listen sind eine schlechte Struktur für moderne Computersysteme.
• Das Patent für die Idee davon, Knoten zu haben, die in mehreren verbundenen Listen gleichzeitig sind (bemerken, dass diese Technik viele Jahrzehnte lang vor dem Patent weit verwendet wurde, wurde gewährt)