Doubly-linked_list implemented in Algol68

I was pleasantly surprised how easy Doubly-linked_lists are in Algol68.

Here are a few tricks:
 1. How to append to the end of the list:

TAIL example list +:= this

2. How to prefix to the start of a list:

this +=: HEAD example list

3. How to insert in the middle of the list:

next of next of HEAD example list +:= this

4. How to extract an item from the list and iterate forward or backward:

LINK next = example list -:= this;
LINK prev = (this -=: example list)

 I only know a handful of languages so I was curious as to how other programming languages have integrated link-list, so I asked at StackExchange: What language has integrated “list insertion” as part of code *syntax*?

Over all the most interesting thing I found out is that is using a sentinel node makes thing so much easier....  It seems that you should not need one at all, but somewhere you need to store the address of the link, this forces you to check for it every time you insert/remove links from a list, just in case you are inserting before the "address" of this list, or (indeed), removing the link that is the "address" of the list.

Notice the following code is devoid of any "if" conditional statements when inserting or deleting items from the list.

e.g. Compare the "if" count in this Algol68 code to the "if" count in insert and remove code examples cited in wikipedia: "A doubly linked list has O(1) insertion and deletion at both ends, so is a natural choice for queues".

When I dropped the sentinel node altogether I quickly discovered this leads to an ambiguity when you try to insert a new link at the start of the list vs adding a link to the end of the list.  Annoying....

Compare with other languages: ALGOL 68 @ Rosettacode


Still... the following Algol68 code is rather nice!

File: prelude/Doubly-linked_list_Link.a68

# -*- coding: utf-8 -*- #
COMMENT REQUIRES:
  mode VALUE = ~;
# For example: #
  mode VALUE = union(int, real, compl)
end COMMENT
 
mode LINKNEW = struct (
  LINK next, prev,
  VALUE value
);
 
mode LINK = ref LINKNEW;
 
skip

File: prelude/Doubly-linked_list_Operator.a68

# -*- coding: utf-8 -*- #
mode LISTNEW = LINKNEW;
mode LIST = ref LISTNEW;
 
op LISTINIT = (LIST self)LIST: (
  self := (self, self, ~);
  self
);
 
op ISEMPTY = (LIST self)bool:
  (LIST(prev of self) :=: LIST(self)) and (LIST(self) :=: LIST(next of self));
 
op HEAD = (LIST self)LINK: next of self;
 
op TAIL = (LIST self)LINK: prev of self;
 
# insert after #
op +:= = (LINK cursor, LINK link)LINK: (
  next of link := next of cursor;
  prev of link := cursor;
  next of cursor := link;
  prev of next of link := link;
  link
);
 
# insert before #
op +=: = (LINK link, LINK cursor)LINK: prev of cursor +:= link;
 
# delete current and step forward #
op -:= = (LIST ignore, LINK link)LINK: (
  next of prev of link := next of link;
  prev of next of link := prev of link;
  next of link := prev of link := nil; # garbage collection hint #
  link
);
 
# delete current and step backward #
prio -=: = 1;
op -=: = (LIST link, LIST ignore)LINK: (
  ignore -:= link; prev of link
);
 
prio ISIN = 1; # low priority #
 
op ISIN = (LINK link, LIST self)bool:
  link isnt LINK(self);
 
skip

File: test/Doubly-linked_list_Operator_Usage.a68

#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
mode VALUE = string; # user defined data type #
pr read "prelude/doubly-linked_list_link.a68" pr;
pr read "prelude/doubly-linked_list_operator.a68" pr;
 
main: (
 
    []VALUE sample = ("Was", "it", "a", "cat", "I", "saw");
    LIST example list := LISTINIT heap LISTNEW;
    LINK this;
 
# Add some data to a list #
    for i to upb sample do
        this := heap LINKNEW;
        value of this := sample[i];
        TAIL example list +:= this
    od;
 
# Iterate throught the list forward #
    this := HEAD example list;
    print("Iterate forward: ");
    while this ISIN example list do
        print((value of this, " "));
        this := next of this
    od;
    print(new line);
 
# Iterate throught the list backward #
    this := TAIL example list;
    print("Iterate backward: ");
    while this ISIN example list do
        print((value of this, " "));
        this := prev of this
    od;
    print(new line);
 
# Finally empty the list #
    print("Empty from tail: ");
    while not ISEMPTY example list do
          this := (example list -:= TAIL example list);
          print((value of this, " "))
    od;
    print(new line)
)

Output:

Iterate forward: Was it a cat I saw 
Iterate backward: saw I cat a it Was
Empty from tail: saw I cat a it Was