Floyds Algorithmus ist auch mehr Algorithmus als Datenstruktur. Er dient dazu, den Anfang eines Zykels in einer verketteten Liste zu finden. Der Zykel kann dabei an einem beliebigen Punkt starten.

Kennengelernt habe ich ihn über diesen Sketch. Dort wird der Algorithmus etwas anders vorgestellt: Zum Finden eines doppelten Eintrags in einem Array. Im Vergleich zu einem Hash-Set bzw. ähnlichen Varianten hat Floyds algorithmus lineare Zeit und konstanten Speicher, also schon echt gut.

In diesem Video wird der Algorithmus noch mal genauer erklärt. Um zu verstehen, was das macht, hab ich das auch mal in Python implementiert und gegen zwei naive Implementierungen getestet.
Ergebnis: Das mit dem Speicherverbrauch merkt man sofort – die lineare Laufzeit kickt nicht so. Vielleicht waren die Daten zu wenig oder ich habe falsch gemessen.