Algol 68 linked lists
last modified November 13, 2026
A row keeps its elements next to each other in memory, which makes a subscript cheap and a fixed size unavoidable. A linked list takes the opposite approach: every value sits in a node of its own, allocated on the heap, and the nodes are joined by references. The list grows and shrinks one node at a time, and a subscript becomes a walk from the first node.
This article builds a list from a structure and a reference, adds and removes nodes, reverses the list in place, and shows what happens when two lists share part of their nodes.
Nodes and lists
MODE NODE declares a structure with a reference to another node and
an integer, and MODE LIST abbreviates a reference to a node. The
empty list is a nil reference. cons allocates a node on the heap
whose next field is the given tail, which is why a list is built
backwards by repeated calls.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE LIST = REF NODE;
LIST empty = NIL;
PROC cons = (LIST tail, INT value) LIST:
HEAP NODE := (tail, value);
PROC print list = (LIST l) VOID:
(
REF NODE p := l;
WHILE p ISNT empty DO
print((whole(value OF p, 0), " "));
p := next OF p
OD;
print(newline)
);
PROC length = (LIST l) INT:
(
INT n := 0;
REF NODE p := l;
WHILE p ISNT empty DO
n +:= 1;
p := next OF p
OD;
n
);
BEGIN
LIST l := empty;
l := cons(l, 3);
l := cons(l, 7);
l := cons(l, 12);
print list(l);
print(("length ", whole(length(l), 0), newline))
END
The program places 3, then 7, then 12 in front of the list, so the last value
becomes the head. Walking uses a local reference that starts at the head and
follows next until it reaches the empty list; length
does the same and counts the steps.
In this implementation p IS NIL is false for a reference variable
declared with :=, even when the variable holds NIL,
so the programs declare LIST empty = NIL once and compare against
that typed empty value. The declaration is called an identity declaration, and
its name compares correctly with any reference of the same mode.
$ a68g basic.a68 12 7 3 length 3
Adding at both ends
A list is held by the variable that refers to its first node, so a procedure
that changes that node needs a reference to the variable:
REF LIST. push puts a new node in front in constant
time. append walks to the last node and links a new one after it,
which costs one step per existing node.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE LIST = REF NODE;
LIST empty = NIL;
PROC cons = (LIST tail, INT value) LIST:
HEAP NODE := (tail, value);
PROC push = (REF LIST l, INT value) VOID:
l := cons(l, value);
PROC append = (REF LIST l, INT value) VOID:
IF l IS empty THEN
l := cons(empty, value)
ELSE
REF NODE p := l;
WHILE next OF p ISNT empty DO
p := next OF p
OD;
next OF p := cons(empty, value)
FI;
PROC print list = (LIST l) VOID:
(
REF NODE p := l;
WHILE p ISNT empty DO
print((whole(value OF p, 0), " "));
p := next OF p
OD;
print(newline)
);
BEGIN
LIST l := empty;
push(l, 5);
push(l, 4);
append(l, 6);
append(l, 7);
print list(l)
END
push is a single assignment to the parameter, and the assignment
reaches the caller's variable because the parameter is a name.
append has to treat the empty list separately: there is no last
node to link after, so the new node becomes the head.
The two pushes put 4 and 5 at the front, and the two appends add 6 and 7 at the end, so the list reads 4 5 6 7. A list built only with appends keeps its values in the order they were added, at the price of a walk per insertion.
$ a68g insert.a68 4 5 6 7
Removing a node
Removing a node means changing the reference that points at it. When the value is in the first node, the head variable itself changes. Otherwise a walk stops at the node before the one to remove, and that node is linked around, so its predecessor now points at its successor.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE LIST = REF NODE;
LIST empty = NIL;
PROC cons = (LIST tail, INT value) LIST:
HEAP NODE := (tail, value);
PROC print list = (LIST l) VOID:
(
REF NODE p := l;
WHILE p ISNT empty DO
print((whole(value OF p, 0), " "));
p := next OF p
OD;
print(newline)
);
PROC remove first = (REF LIST l, INT value) BOOL:
(
BOOL removed := FALSE;
IF l ISNT empty THEN
IF value OF l = value THEN
l := next OF l;
removed := TRUE
ELSE
REF NODE p := l;
WHILE NOT removed AND (next OF p ISNT empty) DO
IF value OF (next OF p) = value THEN
next OF p := next OF (next OF p);
removed := TRUE
ELSE
p := next OF p
FI
OD
FI
FI;
removed
);
BEGIN
LIST l := empty;
l := cons(l, 30);
l := cons(l, 20);
l := cons(l, 30);
l := cons(l, 10);
print list(l);
print(((remove first(l, 30)), newline));
print list(l);
print(((remove first(l, 10)), newline));
print list(l);
print(((remove first(l, 99)), newline));
print list(l)
END
The procedure answers whether it removed anything, which lets the caller tell a
missing value from a successful removal. The loop keeps p at the
node before the candidate, so next OF p is the node to unlink. The
parentheses around the second test are needed because OF binds
more loosely than AND: without them the parser reads
NOT removed AND next first.
The list starts as 10 30 20 30. The first call removes the 30 at the front and
answers T, the second removes the 10 that is now first, and the
third finds no 99 and leaves the list alone. A removed node is not freed
explicitly; the garbage collector reclaims it when no reference is left.
$ a68g delete.a68 10 30 20 30 T 10 20 30 T 20 30 F 20 30
Reversing in place
A list reverses by turning every next reference around. Three
references are enough: one to the part already reversed, one to the node being
processed, and one to the rest of the list, saved before the link is
overwritten.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE LIST = REF NODE;
LIST empty = NIL;
PROC cons = (LIST tail, INT value) LIST:
HEAP NODE := (tail, value);
PROC print list = (LIST l) VOID:
(
REF NODE p := l;
WHILE p ISNT empty DO
print((whole(value OF p, 0), " "));
p := next OF p
OD;
print(newline)
);
PROC reverse = (REF LIST l) VOID:
(
LIST prev := empty;
LIST cur := l;
WHILE cur ISNT empty DO
LIST following := next OF cur;
next OF cur := prev;
prev := cur;
cur := following
OD;
l := prev
);
BEGIN
LIST l := empty;
l := cons(l, 1);
l := cons(l, 2);
l := cons(l, 3);
l := cons(l, 4);
print list(l);
reverse(l);
print list(l)
END
The loop moves forward through the original list while building the reversed one behind it. No node is allocated and no value is copied, so the cost is one step per node and no extra memory.
The output shows the same four nodes before and after the call. Because the nodes themselves are unchanged and only the references between them were rewritten, any other list that shared those nodes would see the reversal too.
$ a68g reverse.a68 4 3 2 1 1 2 3 4
Sharing nodes
Because a list is made of references, two lists can share a tail. The program builds one tail and puts a different node in front of it twice, which gives two lists of three values each that use four nodes between them.
MODE NODE = STRUCT (REF NODE next, INT value);
MODE LIST = REF NODE;
LIST empty = NIL;
PROC cons = (LIST tail, INT value) LIST:
HEAP NODE := (tail, value);
PROC print list = (LIST l) VOID:
(
REF NODE p := l;
WHILE p ISNT empty DO
print((whole(value OF p, 0), " "));
p := next OF p
OD;
print(newline)
);
BEGIN
LIST tail := cons(cons(empty, 2), 3);
LIST a := cons(tail, 1);
LIST b := cons(tail, 9);
print list(a);
print list(b);
value OF tail := 20;
print list(a);
print list(b)
END
Assigning to value OF tail changes the shared node, and both lists
show the new value. Sharing is what makes insertion at the front cheap, since
the new node simply points at the old list, and it is also a source of
surprises when a program assumes that two lists are independent.
The first two lines show the two lists before the change, and the last two show them after the node that both of them contain was updated. A procedure that modifies a list is therefore said to modify every list that shares its nodes.
$ a68g sharing.a68 1 3 2 9 3 2 1 20 2 9 20 2
Lists and rows
A linked list trades random access for flexibility. Reaching the n-th element costs n steps, while a row reaches it in one, and a list spends memory on a reference in every node. In exchange, inserting or removing at a known place costs constant time and never moves another element, and the list grows until the heap is exhausted.
The nodes live on the heap, so they outlive the clause that created them and are reclaimed by the garbage collector when nothing refers to them. The references and the heap article describes that storage, and stacks, queues and trees builds other structures from the same pieces.
Next steps
The references and the heap article explains the
HEAP generator and the garbage collector that the lists depend on,
and structures covers the mode declarations
of the nodes. Stacks, queues and
trees continues with structures built from references, and
rows is the contiguous alternative.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have built a linked list from a structure and a reference, added nodes at the front and at the end, removed a value, reversed the list in place, and seen two lists share their tail.
Author
List all Algol 68 tutorials.