The basic insertion and deletion routines for linked lists are more elegantly written using recursion.
PROCEDURE Insert(VAR list: T; value:INTEGER) =
(* inserts new element in list and maintains order *)
VAR new: T; (*new node*)
BEGIN
IF list = NIL THEN
list:= NEW(T, key := value) (*list is empty*)
ELSIF value < list.key THEN (*proper place found: insert*)
new := NEW(T, key := value);
new.next := list;
list := new;
ELSE (*seek position for insertion*)
Insert(list.next, value);
END; (*IF list = NIL*)
END Insert;
PROCEDURE Remove(VAR list:T; value:INTEGER; VAR found:BOOLEAN) =
(* deletes (first) element with value from sorted list,
or returns false in found if the element was not found *)
BEGIN
IF list = NIL THEN (*empty list*)
found := FALSE
ELSIF value = list.key THEN (*elemnt found*)
found := TRUE;
list := list.next
ELSE (*seek for the element to delete*)
Remove(list.next, value, found);
END;
END Remove;
Doubly Linked Lists
Often it is necessary to move both forward and backwards along a linked list. Thus we need another pointer from each node, to make it doubly linked.
List types are analogous to dance structures:
Conga line - singly linked list.
Chorus line - doubly linked list.
Hora circle - double linked circular list.
Extra pointers allow the flexibility to have both forward and backwards linked lists:
type
pointer = REF node;
node = record
info : item;
front : pointer;
back : pointer;
end;
Insertion
How do we insert p between nodes q and r in a doubly linked list?