Hare-hedgehog algorithm

The Hase-Hedgehog algorithm is a method with which loops with a time complexity and a space complexity of can be found in a singly linked list . From a mathematical point of view, the algorithm is used to find cycles in sequences . It is also known under the name of Floyd's algorithm for finding loops (English Floyd's cycle-finding algorithm ) and must not be confused with Floyd's algorithm from graph theory . ${\ displaystyle O (n)}$ ${\ displaystyle O (1)}$

Importance in mathematics

In addition to the trivially obvious use for finding loops in lists used to store data, the Hase-Igel algorithm is the basis of the Pollard-Rho method for determining the period length of a number sequence including the prime factorization that can be traced back to it .

The algorithm is also used in the field of pseudo-random sequences .

principle

The algorithm consists of running through the list simultaneously with different increments. Two pointers to list elements are used, one of which ( hedgehog ) is shifted to the next element in each iteration , while the other ( rabbit ) is shifted to the next but one element in the same iteration. If the two pointers meet, i.e. reference the same element, the list has a loop. When either pointers reach the end of the list, it has no loop.

Reason

Hare-hedgehog algorithm

The procedure can best be visualized by following the path of the two pointers in a drawn diagram. It is easy to see that in a loop with an odd number of elements as well as in a loop with an even number the hare will encounter the hedgehog in at most one pass.

Because the hare gets one step closer to the hedgehog with every step taken by the hedgehog, the algorithm terminates in a finite time.

Performance consideration

In the best case ( best case performance ) a cyclic list with elements with as the length of the cycle and as the number of elements requires steps before the start of the cycle , since the hedgehog must at least reach the beginning of the cycle before the rabbit takes it on a second round can catch up. ${\ displaystyle m + n}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle m}$

In the worst case performance , steps are necessary, that is, the rabbit only reaches the hedgehog on the last element of the list. At this point, the hedgehog has gone through the loop exactly once, but the rabbit twice. ${\ displaystyle m + n}$

Implementations

C.

# include <stdio.h>
# include <stdlib.h>

int main() {
        struct liste { struct liste *next; } *root, *el, *hase, *igel;
        int i;

        /* Liste erzeugen. */
        root = el = malloc(sizeof(struct liste));
        for(i=0; i<5; ++i) {
                struct liste *eneu = malloc(sizeof(struct liste));
                el->next = eneu;
                el = eneu;
        }
        /* Zyklischen Verweis vom letzten auf das zweite Element anlegen. */
        el->next = root->next;

        /* Hase-Igel-Algorithmus. */
        igel = root;
        hase = root->next;
        while(hase && hase != igel) {
                printf("%p %p\n", hase, igel);
                igel = igel->next;
                hase = hase->next;
                if(hase) hase = hase->next;
        }
        if(hase) puts("Zyklus gefunden!");
        else puts("Liste ist nicht zyklisch!");
        return 0;
}

Ada

with Ada.Text_IO; use Ada.Text_IO;
procedure Hase_Igel is

   package Int_IO is new Integer_IO(Integer); use Int_IO;

   type Liste;
   type Liste_P is access Liste;
   type Liste is record
      Name : Integer;
      Next : Liste_P;
   end record;

   Root, Last, Hase, Igel : Liste_P;

begin
   -- Liste erzeugen
   Root := new Liste'(Name => 0, Next => null);
   Last := Root;
   for I in 1..12 loop
      Last.Next := new Liste'(Name => I, Next => null);
      Last := Last.Next;
   end loop;
   -- zyklischen Verweis erzeugen
   Last.Next := Root.Next.Next;

   -- Hase-Igel-Algorithmus
   Igel := Root;
   Hase := Igel.Next;
   while Hase /= null and Hase /= Igel loop
      Put(Hase.Name, 4); Put(Igel.Name, 4); New_Line;
      Igel := Igel.Next;
      Hase := Hase.Next;
      exit when Hase = null;
      Hase := Hase.Next;
   end loop;
   if Hase = null then
      Put_Line("Liste ist nicht zyklisch");
   else
      Put_Line("Zyklus gefunden");
   end if;
end Hase_Igel;

Scheme

(define (is-mlist? lst)
  (define (iter hase igel counter) ; hase und igel sind meine zeiger,
    (cond ((null? hase) #t) ;ist a null >#t
          ((eq? (mcar hase) (mcar igel)) #f)
          (else (if (= counter 1) ;setze counter auf startwert 1
                    (iter (mcdr hase) (mcdr igel) 0)
                    (iter (mcdr hase) igel 1))))) ;igel startet bei plus 1
  (iter (mcdr lst) lst 0))

;(define a (mlist 2 3 5 7)) ;prüfbeispiel
;(is-mlist? a)

Compare with other approaches to loop detection

Note every knot

approach

Each node traversed is stored in a suitable structure.

Problems

The method requires a great deal of storage space and computing power and is therefore unsuitable for large lists.

Use double chaining

approach

In a doubly linked list , each element has a pointer to both the next and the previous element. When running through such a list, each element must reference the previously visited element as the previous element. If this is not the case, the list must have a loop, since - assuming the concatenation is correct - there are two pointers for this visited element.

Problems

The procedure only works if the double concatenation is not faulty.
A loop over the entire list must be checked separately at the pointer to the preceding element of the start element.

Mark each node

approach

The list is run through; each node is marked. When a marked node is hit the list will loop.

Problems

The procedure does not work because the list must first be run through before searching through it in order to initially set all markings to "not visited". However, this is not reliably possible in the case of a loop.
The marking requires additional memory.

Comparison with starting element

approach

The pointer to the next element of each list element is compared with the start element. When an item points to the start item, the list is looped.

Problems

The procedure only works for lists that are a single loop. Lists that have a loop at any position after the start element are not recognized.

Web links

Finding a Loop in a Singly Linked List . (English)