Detecting Circular Lists

Andrew P. Black black at cse.ogi.edu
Wed Oct 4 00:23:48 UTC 2000


A friend recently sent me the following email:

>Andrew,
>
>I remember a really cute algorithm that detect when a linked list
>traversal has gone circular (due to a bad entry on the list). It involved
>using a trailing pointer and allowing the trailing pointer to fall further
>behind as the list was traversed.
>
>Do you happen to have a reference to that algorithm?

Well, I had never heard of this algorithm, but given the general 
idea, it took me only a couple of minutes to reconstruct it on the 
whiteboard.  My variant moves the tailing pointer forward one link 
every time the traversal pointer moves forward two links.

Tim Sheard, a colleague here at OGI, told me that he thought that the 
algorithm was originally due to Dijkstra, but that he thought that he 
had seen it in CommonLisp, in the form of a predicate cyclic, defined 
something like

	overlaps a b =
		if (eq a b) then true else overlaps (next a) (next (next b))
	cyclic a =
		overlaps a (next a)

Needless to say, there is no such function in the CommonLisp manual.

Just for grins, I implemented this test in Squeak as part of a 
LinkedList method #do:ifCyclic: (ChangeSet attached).   Not that 
Squeak makes much use of linked lists ... but if I need this someday, 
I want it written down!

I would still be interested in an original reference.

	Andrew

-------------- next part --------------
A non-text attachment was scrubbed...
Name: LinkedListCircularities.2.cs
Type: application/octet-stream
Size: 1780 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20001003/0dd070e5/LinkedListCircularities.2.obj


More information about the Squeak-dev mailing list