2013-09-09: SIQ: Detecting Cyclic Linked Lists

In this post we will look at cyclic lists in Racket: how to generate them and two ways to detect them.

-

First, we shall generate cyclic lists using N cons cells. The basic idea is to make all the possible conses, then pick a random place for the cycle to start and end. It is actually easier to think of it as picking a place where the cycle ends and then the place it points back to.

One cute thing we have to deal with is that in Racket conses are immutable, so it seems like we can’t actually ever create any cycles. Luckily, There is something called make-reader-graph that takes an immutable data-structure (like pairs) that contains special placeholder values that can be modified to create cycles and then translates the whole thing into a single immutable value with cycles. For instance,

This code creates a cyclic list of ones.

Our code has five steps: make all the conses, wire the list "forwards", pick the cycling nodes, rewire the cycle, and then make the reader graph.

This function is guaranteed to return a cycle, marked with the +inf.0 value, with an arbitrarily long prefix of non-cyclic list. Here are some example outputs, printed by Racket’s default (cycle detecting) printer:

Next, we’ll be writing functions that detect cycles, so we first need a testing system. We’ll just use variously sized cyclic and non-cyclic lists and make sure the right answer comes out. (build-list creates a non-cyclic list of length N.)

I think the most obvious way to detect a cycle is to "mark" the conses as you see them and return #t if you ever get a marked cons. It’s not obvious how to "mark" a cons in Racket though, because we don’t have any space to use. This sort of thing is one of the best uses for a hasheq-table. Since the table is indexed by eq?-ness, it is like adding another "field" to every object in the Racket program.

The code practically writes itself: if the list is empty, then return #f; if the cons is marked, return #t; otherwise, mark and move on.

Unfortunately, this version uses a lot of space by storing the mark table. There’s another algorithm we could use that doesn’t mark at all, by Robert W. Floyd called the tortoise and the hare algorithm.

It uses two pointers where one points at the ith element and the other points at the 2ith element. No matter when the cycle starts or how long it is, it must be the case that a duplicate will appear between these two elements for some i. The only downside is that the cycle may be traversed many times until a multiple of the cycle length is discovered.

The only tricky thing about implementing this is that it requires lots of empty? tests to make sure you don’t run off the end of the list. If you ever do, then you know it isn’t a cycle. In my version, I define a helper that guards calls to cdr and will return #f from the top-level if it ever sees one. It does this by using an escape continuation, which is like an exception handler: when you call it, it rolls back the stack and returns the value.

And that’s it!

1 Yo! It’s almost time to go!

But first let’s remember what we learned today!

You can create immutable cycles in Racket with make-reader-graph.

You should create a test suite before you write your program.

A hasheq provides a way to add an additional "field" on every object.

It is better to spent ten minutes reading Wikipedia than thirty minutes trying to make your own clever algorithm.

If you’d like to run this exact code at home, you should put it in this order: