Algorithme - Listes circulaires et doublement chaînées

Was ist eine kreisförmige Liste?

Im letzten Knoten in der Liste enthält das Linkfeld null, einen Wert, der das Ende angibt. Eine kreisförmige Liste besteht darin, auf den ersten Knoten in der Liste zu verweisen. Es wird gesagt, dass es offen oder linear ist succ(tail)=head.

Definition der Kreisliste durch einen Zeiger

zeigergesteuerte kreisförmige Liste

1) Durchsuchen Sie die Liste

Prozedurpfad(L: ptr , p : ptr)
var pp:ptr
start
    pp := p
    repeat
         process (*pp.val)
         pp := *pp.link
    to (pp=p)
end

2) Einfügen

Einsatz am Kopf

In den Lead einfügen

Integration außerhalb des Leads

Andere als den oberen einfügen

Siehe:
Einfügen eines Elements in eine verknüpfte Liste.

3) Löschung

Siehe: Löschen eines Elements aus einer verknüpften Liste.

Vor-und Nachteile

• Der Kurs hat keinen Sonderfall.
• Drei Fälle zum Einsetzen:
• Oben (leere Liste).
•  Oben (nicht leere Liste).
• Anderswo als an der Spitze.
• Drei Fälle für die Löschung;
•  Oben (Ein-Elemente-Liste).
• Oben (Liste mit mehr als einem Element).
• Anderswo als in der Führung

Definition der Kreisliste durch einen Link

• Die Route wird aus dem aktuellen Link erstellt, der sie bewacht.
• Integration hat keinen Sonderfall.
• Wir müssen sicherstellen, dass der zu eliminierende Link nicht der Wächter ist.