...
...
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);
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