Abgerollte Linked-List-Arrays vs. Knoten

Question

Ich lese über abgerollte verknüpfte Listen und habe zwei verschiedene Möglichkeiten gefunden, um eine zu erstellen. Das Buch, das ich habe implementiert eine so:

// Node 
typedef struct node { 
    int data; 
    struct node *next; 
} Node; 

// Block of nodes 
typedef struct linkedblock { 
    struct linkedblock *next; 
    Node *head; 
    int nodeCount; 
} LinkedBlock; 

jedoch Wikipedia zeigt, dass anstelle von LinkedBlock zu einem Node mit einem Zeiger, hat es ein Array. Ich denke, das könnte so sein, dass der Speicher zusammenhängend ist und etwas über Cache-Effizienz? Gibt es andere Vorteile, es auf diese Weise zu tun? Ist die Art, wie mein Buch es implementiert, weniger optimiert/schlechter? Gibt es einen gemeinsamen oder bevorzugten Weg?

Ich versuche, eine aufgerollte verkettete Liste zu implementieren, damit ich lernen kann, wie sie funktionieren, aber auch für den Fall, dass ich eine in der Zukunft verwenden muss (ich finde seltsamerweise keine C-Implementierungen auf GitHub oder anderswo). Grundsätzlich würde ich gerne wissen, welche der beiden Möglichkeiten in realen Anwendungen wahrscheinlicher ist. Ist das auch eine Datenstruktur, die ich nicht zu viel Zeit mit dem Lernen verschwenden sollte? Denn in meinem anderen Algorithmenbuch (CLRS) sehe ich es nicht einmal erwähnt.

Answer 1

Die Umsetzung des Buches scheint, wie es nicht sehr viel nützen würde, weil es tatsächlich verwendet mehr Speicher als ein Standard-verkettete Liste (zu speichern, diese LinkedBlock Strukturen). Einer der Hauptvorteile einer aufgerollten verknüpften Liste ist, dass Sie mehr Daten pro Knoten als eine normale verknüpfte Liste speichern können. Es ist ein Gleichgewicht zwischen Arrays, die nur eine ganze Zahl zusätzlichen Speicherplatzes zur Speicherung der Größe verwenden (platzsparend), und verknüpften Listen, die ein effizientes Einfügen und Löschen mit einem Zeiger auf einige Daten ermöglichen (zeiteffizient).

Für den Wert des Lernens über sie: Sie haben ähnliche algorithmische Eigenschaften wie normale verknüpfte Listen. Der größte Vorteil beim Erstellen einer aufgerollten verknüpften Liste besteht darin, dass Sie eine vorhandene Anwendung haben, die beschleunigt werden muss oder zu viel Arbeitsspeicher benötigt, da sie dieselbe Schnittstelle wie eine normale verknüpfte Liste haben würde. Wenn Sie etwas über asymptotische Analyse gelernt haben (was auch in CLRS diskutiert wird), dann können Sie vielleicht erkennen, dass die Speichernutzung und Zeiteffizienz von abgerollten verknüpften Listen nur um einen konstanten Faktor differiert, so dass sie asymptotisch gleich sind.

Meine Empfehlung wäre: Seien Sie sich bewusst, dass sie existieren und dass sie die Leistung in realen Anwendungen verbessern können, aber wenn Sie nicht eine bestimmte Anwendung beschleunigen möchten, machen Sie sich keine Sorgen .