RE: Detecting Infinite Looping

Subject: RE: Detecting Infinite Looping
From: Gavin Nicol <gtn@xxxxxxxxxxxx>
Date: Thu, 29 Jan 1998 10:37:12 GMT
The standard algorithm for detecting loops in linked lists is the
"tortoise and hare" algorithm, where you have 2 pointers moving
along the list, one at twice the pace of the other. If the faster
pointer ever passes the slower pointer, there is a loop.

Also, some LISP systems had a way of persisting circular lists,
so there must be code out there for this (been a long time since
I used a symbolics...)


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist


Current Thread
  • Detecting Infinite Looping
    • W. Eliot Kimber - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id XAA26840Wed, 28 Jan 1998 23:49:20 -0500 (EST)
      • Richard Light - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id EAA04376Thu, 29 Jan 1998 04:14:50 -0500 (EST)
      • Henry Thompson - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id EAA04681Thu, 29 Jan 1998 04:40:15 -0500 (EST)
      • <Possible follow-ups>
      • Pawson, David - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id DAA29108Thu, 29 Jan 1998 03:02:52 -0500 (EST)
      • Gavin Nicol - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id FAA05174Thu, 29 Jan 1998 05:37:26 -0500 (EST) <=
      • W. Eliot Kimber - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id KAA06902Thu, 29 Jan 1998 10:35:42 -0500 (EST)
        • hanche+dsssl-l - from mail1.ability.netby web4.ability.net (8.8.5/8.6.12) with ESMTP id NAA07915Thu, 29 Jan 1998 13:13:21 -0500 (EST)