zu www.bildungsgueter.de zur Inhaltsübersicht des Kapitels

Doppelt verkettete, sortierte Listen


...

eine leere, doppelt verkettete Liste

eine doppelt verkettete Liste mit einem Elementknoten

eine doppelt verkettete Liste mit zwei Elementknoten

eine doppelt verkettete Liste mit drei Elementknoten

Erforderliche Typvereinbarungen

...

   MODE ELEMENTTYPE = INT;

   MODE NODE = STRUCT( ELEMENTTYPE item,
                       REF NODE previous,
                       REF NODE next);
   MODE DLLIST =
         STRUCT(REF NODE first,
                REF NODE last,
                INT size);

Einfügeoperationen

Das Einfügen am Beginn der Liste ...

   PROC (REF ELEMENTTYPE, REF DLLIST) VOID add first =
        (REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     REF NODE new node = HEAP NODE := (elem, NIL, first OF list);
     IF REF NODE(first OF list) ISNT NIL THEN
        previous OF first OF list := new node
     FI;
     first OF list := new node;
     IF REF NODE(last OF list) IS NIL THEN
        last OF list := new node
     FI;
     size OF list +:= 1
   END;

Einfügen am Ende der Liste

   PROC (REF ELEMENTTYPE, REF DLLIST) VOID add last =
        (REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     REF NODE new node = HEAP NODE := (elem, last OF list, NIL);
     IF REF NODE(last OF list) ISNT NIL THEN
        next OF last OF list := new node
     FI;
     last OF list := new node;
     IF REF NODE(first OF list) IS NIL THEN
        first OF list := new node
     FI;
     size OF list +:= 1
   END;

Einfügen zwischen zwei Listenelementen

   PROC (INT, REF ELEMENTTYPE, REF DLLIST) VOID add =
        (INT idx, REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     IF idx = 0 THEN
        add first(elem, list)
     ELIF idx >= size OF list THEN
        add last(elem, list)
     ELSE
        COMMENT
            Es ist möglich, den Wert des Index mit der Länge der
            Liste zu vergleichen, um zu entscheiden, ob die
            Einfügestelle vom Listenanfang oder vom Listenende
            her aufgesucht werden sollte.
        COMMENT
        REF NODE insert point := first OF list;
        FOR i FROM 1 BY 1 WHILE i < idx DO
          insert point := next OF insert point
        OD;
        REF NODE new node = HEAP NODE
                  := (elem, insert point, next OF insert point);
        previous OF next OF insert point := new node;
        next OF insert point := new node;
        size OF list +:= 1
     FI
   END;

...

Die Entfernung des mittleren Knotens aus der Liste geschieht nun mit diesen beiden Zuweisungen:

next OF previous OF node to remove := next OF node to remove;
previous OF next OF node to remove := previous OF node to remove
BEGIN

   MODE ELEMENTTYPE = INT;

   MODE NODE = STRUCT( ELEMENTTYPE item,
                       REF NODE previous,
                       REF NODE next);
   MODE DLLIST =
         STRUCT(REF NODE first,
                REF NODE last,
                INT size);

   PROC (REF ELEMENTTYPE, REF DLLIST) VOID add first =
        (REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     REF NODE new node = HEAP NODE := (elem, NIL, first OF list);
     IF REF NODE(first OF list) ISNT NIL THEN
        previous OF first OF list := new node
     FI;
     first OF list := new node;
     IF REF NODE(last OF list) IS NIL THEN
        last OF list := new node
     FI;
     size OF list +:= 1
   END;

   PROC (REF ELEMENTTYPE, REF DLLIST) VOID add last =
        (REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     REF NODE new node = HEAP NODE := (elem, last OF list, NIL);
     IF REF NODE(last OF list) ISNT NIL THEN
        next OF last OF list := new node
     FI;
     last OF list := new node;
     IF REF NODE(first OF list) IS NIL THEN
        first OF list := new node
     FI;
     size OF list +:= 1
   END;

   PROC (INT, REF ELEMENTTYPE, REF DLLIST) VOID add =
        (INT idx, REF ELEMENTTYPE elem, REF DLLIST list) VOID :
   BEGIN
     IF idx = 0 THEN
        add first(elem, list)
     ELIF idx >= size OF list THEN
        add last(elem, list)
     ELSE
        COMMENT
            Es ist möglich, den Wert des Index mit der Länge der
            Liste zu vergleichen, um zu entscheiden, ob die
            Einfügestelle vom Listenanfang oder vom Listenende
            her aufgesucht werden sollte.
        COMMENT
        REF NODE insert point := first OF list;
        FOR i FROM 1 BY 1 WHILE i < idx DO
          insert point := next OF insert point
        OD;
        REF NODE new node = HEAP NODE
                  := (elem, insert point, next OF insert point);
        previous OF next OF insert point := new node;
        next OF insert point := new node;
        size OF list +:= 1
     FI
   END;

   PROC (REF DLLIST, PROC VOID) ELEMENTTYPE remove first =
        (REF DLLIST list, PROC VOID error) ELEMENTTYPE :
   BEGIN
     REF ELEMENTTYPE result = LOC ELEMENTTYPE;
     IF size OF list = 0 THEN
        error
     ELSE
        result := item OF first OF list;
        IF size OF list = 1 THEN
           first OF list := last OF list := NIL
        ELSE
           previous OF next OF first OF list := NIL;
           first OF list := next OF first OF list
        FI
     FI;
     size OF list -:= 1;
     result
   END;

   PROC (REF DLLIST, PROC VOID) ELEMENTTYPE remove last =
        (REF DLLIST list, PROC VOID error) ELEMENTTYPE :
   BEGIN
     REF ELEMENTTYPE result = LOC ELEMENTTYPE;
     IF size OF list = 0 THEN
        error
     ELSE
        result := item OF last OF list;
        IF size OF list = 1 THEN
           first OF list := last OF list := NIL
        ELSE
           next OF previous OF last OF list :=NIL;
           last OF list := previous OF last OF list
        FI
     FI;
     size OF list -:= 1;
     result
   END;

   PROC (INT, REF DLLIST, PROC VOID) ELEMENTTYPE remove =
        (INT idx, REF DLLIST list, PROC VOID error) ELEMENTTYPE :
   BEGIN
     IF idx < 1 OR idx > size OF list
        THEN
          error;
          SKIP
     ELIF idx = 1 THEN
        remove first(list, error)
     ELIF idx = size OF list THEN
        remove last(list, error)
     ELSE
        COMMENT
            Es ist möglich, den Wert des Index mit der Länge der
            Liste zu vergleichen, um zu entscheiden, ob der zu
            entfernende Knoten vom Listenanfang oder vom Listenende
            her aufgesucht werden sollte.
        COMMENT
        REF ELEMENTTYPE result = LOC ELEMENTTYPE;
        REF NODE node to remove := first OF list;
        FOR i FROM 1 BY 1 WHILE i < idx DO
          node to remove := next OF node to remove
        OD;
        result := item OF node to remove;
        next OF previous OF node to remove := nextOF node to remove;
        previous OF next OF node to remove := previous OF node to remove;
        size OF list -:= 1;
        result
     FI
   END;

   PROC (INT, REF DLLIST, PROC VOID) ELEMENTTYPE remove2 =
        (INT idx, REF DLLIST list, PROC VOID error) ELEMENTTYPE :
   BEGIN
     IF idx < 1 OR idx > size OF list
        THEN
          error;
          SKIP
     ELIF idx = 1 THEN
        remove first(list, error)
     ELIF idx = size OF list THEN
        remove last(list, error)
     ELSE
        REF ELEMENTTYPE result = LOC ELEMENTTYPE;
        REF NODE node to remove;
        IF 2*idx < size OF list THEN
          node to remove:= first OF list;
          FOR i FROM 1 BY 1 WHILE i < idx DO
            node to remove := next OF node to remove
          OD
        ELSE
          node to remove:= last OF list;
          FOR i FROM size OF list BY -1 WHILE i > idx DO
            node to remove := previous OF node to remove
          OD
        FI;
        result := item OF node to remove;
        next OF previous OF node to remove := next OF node to remove;
        previous OF next OF node to remove := previous OF node to remove;
        size OF list -:= 1;
        result
     FI
   END;

   PROC (REF DLLIST) VOID print list =
        (REF DLLIST list) VOID :
   BEGIN
     REF INT cnt = LOC INT := 1;
     print(("("));
     REF NODE ptr := first OF list;
     WHILE REF NODE(ptr) ISNT NIL
     DO
       print((item OF ptr));
       IF REF NODE(next OF ptr) ISNT NIL THEN
           print((", "))
       FI;
       ptr := next OF ptr;
       cnt +:= 1;
       IF cnt = 10 THEN
         print((newline));
         cnt := 1
       FI
     OD;
     print((")", newline))
   END;

   COMMENT
      Test:
   COMMENT
   REF DLLIST liste = LOC DLLIST := (NIL, NIL, 0);
   print(("Test 1: Anfügen"));
   print list(liste);
   add first(LOC INT := 2, liste);
   add last(LOC INT := 4, liste);
   add last(LOC INT := 6, liste);
   add last(LOC INT := 8, liste);
   add last(LOC INT := 10, liste);
   add(2, LOC INT := 5, liste);
   remove first (liste, VOID : BEGIN GOTO error END);
   add first(LOC INT := 1, liste);
   print list(liste);


   print(("Test 2: Einfaches Löschen"));
   liste := (NIL, NIL, 0);
   print list(liste);
   FOR i FROM 1 TO 15 DO
     add last(LOC INT := i, liste)
   OD;
   print list(liste);
   remove (10, liste, VOID : BEGIN GOTO error END);
   print list(liste);

   print(("Test 3: Optimiertes Löschen"));
   liste := (NIL, NIL, 0);
   print list(liste);
   FOR i FROM 1 TO 15 DO
     add last(LOC INT := i, liste)
   OD;
   print list(liste);
   remove2 (10, liste, VOID : BEGIN GOTO error END);
   print list(liste);

   GOTO end of program;
  error:
   print(("Ein Fehler ist aufgetreten"));
  end of program:
   SKIP

END

zur Inhaltsübersicht des Kapitels