Sollten verknüpfte Listen immer einen Endzeiger haben?

Mein Verständnis...

Vorteile:

• Das Einfügen am Ende ist O (1) anstelle von O (N).
• Wenn es sich bei der Liste um eine doppelt verknüpfte Liste handelt, ist das Entfernen am Ende auch O (1) anstelle von O (N).

Nachteil:

• Nimmt eine unbedeutende Menge zusätzlichen Speichers in Anspruch : 4-8 Bytes .
• Der Implementierer muss den Schwanz verfolgen.

Wenn ich mir diese Vor- und Nachteile anschaue, kann ich nicht erkennen, warum eine verknüpfte Liste jemals die Verwendung eines Endzeigers vermeiden würde. Fehlt mir etwas?

Sie haben Recht, ein Schwanzzeiger tut nie weh und kann nur helfen. Es gibt jedoch eine Situation, in der man überhaupt keinen Endzeiger benötigt.

Wenn eine verknüpfte Liste zum Implementieren eines Stapels verwendet wird, ist kein Endzeiger erforderlich, da garantiert werden kann, dass alle Zugriffe, Einfügungen und Entfernungen am Kopf erfolgen. Davon abgesehen könnte man ohnehin eine doppelt verknüpfte Liste mit einem Endzeiger verwenden, da dies die Standardimplementierung in einer Bibliothek oder Plattform ist und der Speicher billig ist, aber nicht benötigt wird.

Verknüpfte Listen sind sehr häufig persistent und unveränderlich. Tatsächlich ist diese Verwendung in funktionalen Programmiersprachen allgegenwärtig. Schwanzzeiger brechen diese beiden Eigenschaften. Wenn Sie sich jedoch nicht für Unveränderlichkeit oder Beharrlichkeit interessieren, hat das Einfügen eines Endzeigers kaum Nachteile.

Ich verwende selten einen Endzeiger für verknüpfte Listen und verwende häufig einfach verknüpfte Listen, wenn ein stapelartiges Push / Pop-Muster zum Einfügen und Entfernen (oder nur zum Entfernen in linearer Zeit aus der Mitte) ausreicht. Dies liegt daran, dass in meinen üblichen Anwendungsfällen der Endzeiger tatsächlich teuer ist, genauso wie es teuer ist, die einfach verknüpfte Liste in eine doppelt verknüpfte Liste umzuwandeln.

Oft speichert meine häufig verwendete Verwendung für eine einfach verknüpfte Liste Hunderttausende verknüpfter Listen, die jeweils nur wenige Listenknoten enthalten. Ich verwende im Allgemeinen auch keine Zeiger für verknüpfte Listen. Ich verwende stattdessen Indizes in einem Array, da die Indizes 32-Bit sein können, z. B. die Hälfte des Platzes eines 64-Bit-Zeigers einnehmen. Im Allgemeinen ordne ich Listenknoten im Allgemeinen auch nicht einzeln zu. Stattdessen verwende ich einfach ein großes Array, um alle Knoten zu speichern, und verwende dann 32-Bit-Indizes, um die Knoten miteinander zu verknüpfen.

Stellen Sie sich als Beispiel ein Videospiel vor, das ein 400 x 400-Raster verwendet, um eine Million Partikel zu partitionieren, die sich bewegen und voneinander abprallen, um die Kollisionserkennung zu beschleunigen. In diesem Fall besteht eine ziemlich effiziente Möglichkeit zum Speichern darin, 160.000 einfach verknüpfte Listen zu speichern, was in meinem Fall 160.000 32-Bit-Ganzzahlen (~ 640 Kilobyte) und einen 32-Bit-Ganzzahl-Overhead pro Partikel bedeutet. Wenn sich Partikel auf dem Bildschirm bewegen, müssen wir nur noch einige 32-Bit-Ganzzahlen aktualisieren, um ein Partikel wie folgt von einer Zelle in die andere zu verschieben:

... wobei der nextIndex ("Zeiger") eines Partikelknotens entweder als Index für das nächste Partikel in der Zelle oder für das nächste freie Partikel dient, das zurückgefordert werden soll, wenn das Partikel gestorben ist (im Grunde eine Implementierung eines freien Listenzuweisers unter Verwendung von Indizes):

Das Entfernen der linearen Zeit aus einer Zelle ist eigentlich kein Overhead, da wir die Partikellogik verarbeiten, indem wir durch die Partikel in einer Zelle iterieren. Eine doppelt verknüpfte Liste würde also nur Overhead hinzufügen, der nicht vorteilhaft ist Alles in meinem Fall, nur weil ein Schwanz mir überhaupt nicht nützen würde.

Ein Endzeiger würde die Speichernutzung des Rasters verdoppeln und die Anzahl der Cache-Fehler erhöhen. Außerdem muss ein Zweig eingefügt werden, um zu überprüfen, ob die Liste leer ist, anstatt verzweigungslos zu sein. Wenn Sie eine doppelt verknüpfte Liste erstellen, verdoppelt sich der Listenaufwand für jedes Partikel. 90% der Zeit, in der ich verknüpfte Listen verwende, ist dies für Fälle wie diese der Fall, und daher wäre die Speicherung eines Endzeigers relativ teuer.

4-8 Bytes sind also in den meisten Kontexten, in denen ich überhaupt verknüpfte Listen verwende, nicht trivial. Ich wollte nur dort einsteigen, denn wenn Sie eine Datenstruktur zum Speichern einer Schiffsladung von Elementen verwenden, sind 4-8 Bytes möglicherweise nicht immer so vernachlässigbar. Ich verwende tatsächlich verknüpfte Listen, um die Anzahl der Speicherzuordnungen und die erforderliche Speichermenge zu reduzieren , anstatt beispielsweise 160.000 dynamische Arrays zu speichern, die für das Raster wachsen und eine explosive Speichernutzung haben würden (normalerweise ein Zeiger plus zwei Ganzzahlen mindestens pro Rasterzelle zusammen mit Heap-Zuweisungen pro Gitterzelle im Gegensatz zu nur einer Ganzzahl und null Heap-Zuweisungen pro Zelle).

Ich finde oft viele Leute, die wegen ihrer zeitlich konstanten Komplexität, die mit dem Entfernen von Front / Mitte und dem Einfügen von Front / Mitte verbunden ist, nach verknüpften Listen greifen, wenn LLs in diesen Fällen aufgrund ihrer allgemeinen mangelnden Kontiguität oft eine schlechte Wahl sind. Wo LLs für mich vom Standpunkt der Leistung aus schön sind, ist die Möglichkeit, ein Element durch einfaches Bearbeiten einiger Zeiger von einer Liste in eine andere zu verschieben und eine Datenstruktur mit variabler Größe ohne Speicherzuordnung mit variabler Größe zu erzielen (seitdem Jeder Knoten hat eine einheitliche Größe, wir können freie Listen verwenden, zB). Wenn jeder Listenknoten einzeln einem Allzweckzuweiser zugewiesen wird, schneiden verknüpfte Listen im Vergleich zu den Alternativen normalerweise viel schlechter ab.

Ich würde stattdessen vorschlagen, dass in den meisten Fällen, in denen verknüpfte Listen als sehr effektive Optimierung gegenüber einfachen Alternativen dienen, die nützlichsten Formen im Allgemeinen einfach verknüpft sind, nur einen Kopfzeiger benötigen und keine allgemeine Speicherzuweisung pro erfordern Knoten und kann stattdessen oft nur den bereits pro Knoten zugewiesenen Speicher bündeln (von einem großen Array, das bereits im Voraus zugewiesen wurde, z. B.). Außerdem würde jede SLL in diesen Fällen im Allgemeinen eine sehr kleine Anzahl von Elementen speichern, wie z. B. Kanten, die mit einem Diagrammknoten verbunden sind (viele winzige verknüpfte Listen im Gegensatz zu einer massiven verknüpften Liste).

Es ist auch erwähnenswert, dass wir heutzutage eine Schiffsladung DRAM haben, aber das ist der zweitlangsamste verfügbare Speichertyp. Wir haben immer noch 64 KB pro Kern, wenn es um den L1-Cache mit 64-Byte-Cache-Zeilen geht. Infolgedessen können diese kleinen Byteeinsparungen in einem leistungskritischen Bereich wie der obigen Partikelsimulation wirklich von Bedeutung sein, wenn sie millionenfach multipliziert werden, wenn dies den Unterschied zwischen dem Speichern von doppelt so vielen Knoten in einer Cache-Zeile oder nicht bedeutet, z