Ist es möglich, einen Zyklus in einer unveränderlichen verketteten Liste zu machen?
Angenommen, wir haben die folgende Struktur in Java:
%Vor%Scala hat eingebaute Unterstützung für unveränderliche einfach verknüpfte Liste. Es wäre:
%Vor%Also, ist es möglich, einen Zyklus in dieser Art von Listen zu machen (unveränderliche einfach verknüpfte Liste). Mit dem Zyklus meine ich Folgendes:
4 Antworten
Es ist nicht möglich, einfach durch Design. Scalas Liste ist unveränderlich, und alles, was Sie mit einer bestehenden Liste tun können, ist im Grunde genommen den Kopf (der den Schwanz ergibt, mit anderen Worten eine Liste, die selbst unveränderlich ist) oder ein Element voranzustellen, was eine neue unveränderliche Liste ergibt. Sie können ein Element einer Liste übernehmen und es erneut voranstellen. Dadurch wird jedoch nur eine längere Liste erstellt, in der zwei Elemente dieselbe Instanz sind. Dadurch wird kein Zyklus erstellt.
Sie könnten auch zwei Listen haben, die Teile (oder alle) ihrer Schwänze teilen, aber Sie können immer noch keine Schleifen erstellen.
Das liegt einfach daran, dass Sie zur Erstellung einer längeren Liste nur eine bereits existierende Liste vorgeben müssen, was bedeutet, dass in einer Liste Kopf Knoten ältere Instanzen sind, die Knoten
Also ist die kurze Antwort nein, Sie können keine Zyklen mit der Liste der skalaren (unveränderlichen) erstellen.
Abgesehen davon ist der Grund, warum es möglich ist mit Stream s (wie in senias Antwort gezeigt) und nicht mit List s (obwohl beide unveränderbare Sammlungen sind), dass Stream s eine kritische Zutat hinzufügen : Faulheit. Stream-Knoten werden träge konstruiert (ein Knoten speichert im Grunde einen thumb auf den Inhalt des aktuellen Knotens), der es einem späteren Knoten erlaubt, einen früheren (und noch nicht erstellten) Knoten zu referenzieren und somit Schleifen zu ermöglichen.
Eine andere Möglichkeit besteht darin, die Tatsache zu verwenden, dass der 'this' -Zeiger bereits existiert, bevor der Konstruktor die Ausführung beendet hat, und als Teil des Konstruktors können Sie eine Funktion aufrufen, die als Parameter übergeben wurde in der direkten Bezugnahme auf den 'nächsten' Knoten) übergibt der 'this' Zeiger auf diese Funktion. Die Funktion ist verantwortlich für das Erzeugen des Verweises auf den nächsten Knoten, möglicherweise basierend auf dem übergebenen Knotenwert. Ein ungefähres Beispiel ist wie folgt:
%Vor%Natürlich, wenn Sie nicht genug Kontrolle darüber haben, wann dieser Konstruktor aufgerufen wird, könnten alle Arten von Unsinn als genNext-Funktion übergeben werden ...
Wie bereits erwähnt, können Sie keine unveränderliche, zyklische Struktur ohne Faulheit schaffen. Sie können jedoch einen Vorteil von scalazs Name . Es hat mehrere Implementierungen, von denen Need faul ausgewertete Werte liefert. Dadurch können wir eine verkettete Liste definieren, deren next zurückgestellt werden kann:
Damit können wir Funktionen wie cycle definieren, die die Auswertung der letzten zyklischen Referenz mit Need verzögern. Alle anderen Referenzen müssen nicht faul sein, also wickeln wir sie einfach in Value (was nichts verschiebt).
Tags und Links scala algorithm java linked-list