<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P073-linked-list/ | updated: 2026-10-14 -->

# P073 Linked list playground

A singly linked list kept as values and next-slot links, drawn with the slots it lives in: insert, delete (the slot is freed and reused), reverse by the three-pointer walk, the middle by a slow and a fast walker, and a loop closed and found again by Floyd's two walkers.

EML-P project `projects/linked-list` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/linked-list` runs it and `eml project verify projects/linked-list` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: linked-list-operations (https://efficientnewlanguage.org/cases/101-linked-list-operations/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
3
abc
1000
5
9

4
42
7
7

2
10
2
11
2
12
2
13
2
14
2
15
2
16
2
6
9
```

Screen:

```text
== Linked list playground ==
A singly linked list: each node holds a value and the slot of the next node.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 0
Pick a number from 1 to 9.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> x
Pick a number from 1 to 9.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 3
value (0 to 999)> abc
Type a whole number from 0 to 999.
value (0 to 999)> 1000
Type a whole number from 0 to 999.
value (0 to 999)> 5
position (0 to 5)> 9
Type a whole number from 0 to 5.
position (0 to 5)> 
Cancelled.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 4
value (0 to 999)> 42
No node holds 42.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 7
point the last node back to position (0 to 4)> 7
Type a whole number from 0 to 4.
point the last node back to position (0 to 4)> 
Cancelled.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 10
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 11
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 12
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> [12] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11     7
     7     12   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 13
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> [12] -> [13] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11     7
     7     12     8
     8     13   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 14
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> [12] -> [13] -> [14] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11     7
     7     12     8
     8     13     9
     9     14   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 15
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> [12] -> [13] -> [14] -> [15] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11     7
     7     12     8
     8     13     9
     9     14    10
    10     15   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 16
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> [10] -> [11] -> [12] -> [13] -> [14] -> [15] -> [16] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1     5
     5     10     6
     6     11     7
     7     12     8
     8     13     9
     9     14    10
    10     15    11
    11     16   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
The list is full: 12 nodes.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 6
12 nodes: when the fast walker ran out, the slow one had taken 6 steps, to [11] at position 6.
With an even number of nodes there are two middles; this way finds the second.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 9
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
3
5
2
4
3
2
8
5
6
7
2
1
8
2
7
8
9
```

Screen:

```text
== Linked list playground ==
A singly linked list: each node holds a value and the slot of the next node.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 1
  head -> [7] -> [3] -> [9] -> [4] -> [1] -> end
  slot  value  next
     0      7     1
     1      3     2
     2      9     3
     3      4     4
     4      1   end
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 3
value (0 to 999)> 5
position (0 to 5)> 2
  head -> [7] -> [3] -> [5] -> [9] -> [4] -> [1] -> end
  slot  value  next
     0      7     1
     1      3     5
     2      9     3
     3      4     4
     4      1   end
     5      5     2
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 4
value (0 to 999)> 3
Deleted 3 from position 1; its slot is free for the next node.
  head -> [7] -> [5] -> [9] -> [4] -> [1] -> end
  slot  value  next
     0      7     5
     1  (free)
     2      9     3
     3      4     4
     4      1   end
     5      5     2
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
value (0 to 999)> 8
  head -> [7] -> [5] -> [9] -> [4] -> [1] -> [8] -> end
  slot  value  next
     0      7     5
     1      8   end
     2      9     3
     3      4     4
     4      1     1
     5      5     2
  head is slot 0.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 5
  head -> [8] -> [1] -> [4] -> [9] -> [5] -> [7] -> end
  slot  value  next
     0      7   end
     1      8     4
     2      9     5
     3      4     2
     4      1     3
     5      5     0
  head is slot 1.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 6
6 nodes: when the fast walker ran out, the slow one had taken 3 steps, to [9] at position 3.
With an even number of nodes there are two middles; this way finds the second.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 7
point the last node back to position (0 to 5)> 2
  head -> [8] -> [1] -> [4] -> [9] -> [5] -> [7] -> back to [4]
  slot  value  next
     0      7     3
     1      8     4
     2      9     5
     3      4     2
     4      1     3
     5      5     0
  head is slot 1.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 1
  head -> [8] -> [1] -> [4] -> [9] -> [5] -> [7] -> back to [4]
  slot  value  next
     0      7     3
     1      8     4
     2      9     5
     3      4     2
     4      1     3
     5      5     0
  head is slot 1.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 8
A loop: the two walkers met after 4 steps. It starts at [4], position 2, and goes round 4 nodes.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 2
The list has a loop, so it has no end: break the loop first (7).

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 7
Loop broken: [7] points to the end again.
  head -> [8] -> [1] -> [4] -> [9] -> [5] -> [7] -> end
  slot  value  next
     0      7   end
     1      8     4
     2      9     5
     3      4     2
     4      1     3
     5      5     0
  head is slot 1.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 8
No loop: the fast walker reached the end after 3 steps.

1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit
choice> 9
Bye.
```

## Modules

### main.eml

```eml
# P073 linked list playground: a singly linked list drawn as its nodes and
# links, with the slots they live in. Insert, delete, reverse, find the
# middle, close a loop and find it again with Floyd's two walkers.
import links

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def number(s):
    # A whole number of up to 3 digits, or -1.
    if len(s) == 0 or len(s) > 3:
        return -1
    0 => n
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n * 10 + int(c) => n
    return n

def lpad(s, n):
    while len(s) < n:
        " " + s => s
    return s

def draw(lst):
    links.walk(lst) => w
    lst[0] => values
    "head" => line
    for i in w[0]:
        line + " -> [" + str(values[i]) + "]" => line
    if w[1] == -1:
        line + " -> end" => line
    else:
        line + " -> back to [" + str(values[w[1]]) + "]" => line
    ("  " + line) ^0
    "  slot  value  next" ^0
    lst[1] => nexts
    for i in [0:len(nexts) - 1]:
        if nexts[i] == -2:
            ("  " + lpad(str(i), 4) + "  (free)") ^0
        else:
            "end" => nx
            if nexts[i] >= 0:
                str(nexts[i]) => nx
            ("  " + lpad(str(i), 4) + lpad(str(values[i]), 7) + lpad(nx, 6)) ^0
    ("  head is slot " + str(lst[2]) + ".") ^0

def looped(lst):
    return links.walk(lst)[1] != -1

def ask(prompt, low, high):
    while True:
        trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => a
        if a == "":
            return -1
        number(a) => n
        if n >= low and n <= high:
            return n
        ("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0

def add_end(lst):
    if links.length(lst) == 12:
        "The list is full: 12 nodes." ^0
        return lst
    ask("value", 0, 999) => v
    if v == -1:
        "Cancelled." ^0
        return lst
    links.insert_at(lst, links.length(lst), v) => lst
    draw(lst)
    return lst

def insert(lst):
    if links.length(lst) == 12:
        "The list is full: 12 nodes." ^0
        return lst
    ask("value", 0, 999) => v
    if v == -1:
        "Cancelled." ^0
        return lst
    ask("position", 0, links.length(lst)) => p
    if p == -1:
        "Cancelled." ^0
        return lst
    links.insert_at(lst, p, v) => lst
    draw(lst)
    return lst

def delete(lst):
    if links.length(lst) == 0:
        "The list is empty." ^0
        return lst
    ask("value", 0, 999) => v
    if v == -1:
        "Cancelled." ^0
        return lst
    links.delete_value(lst, v) => r
    if r[1] == -1:
        ("No node holds " + str(v) + ".") ^0
        return lst
    ("Deleted " + str(v) + " from position " + str(r[1]) + "; its slot is free for the next node.") ^0
    draw(r[0])
    return r[0]

def middle(lst):
    links.length(lst) => n
    if n == 0:
        "The list is empty." ^0
        return
    links.middle(lst) => m
    lst[0][m[0]] => v
    (str(n) + " nodes: when the fast walker ran out, the slow one had taken " + str(m[1]) + " steps, to [" + str(v) + "] at position " + str(m[1]) + ".") ^0
    if n % 2 == 0:
        "With an even number of nodes there are two middles; this way finds the second." ^0

def loop(lst):
    if looped(lst):
        links.walk(lst) => w
        lst[0][w[0][len(w[0]) - 1]] => last
        links.break_loop(lst) => lst
        ("Loop broken: [" + str(last) + "] points to the end again.") ^0
        draw(lst)
        return lst
    links.length(lst) => n
    if n == 0:
        "The list is empty." ^0
        return lst
    ask("point the last node back to position", 0, n - 1) => p
    if p == -1:
        "Cancelled." ^0
        return lst
    links.close_loop(lst, p) => lst
    draw(lst)
    return lst

def find_loop(lst):
    links.floyd(lst) => f
    if not f[0]:
        ("No loop: the fast walker reached the end after " + str(f[1]) + " steps.") ^0
        return
    links.walk(lst)[0] => order
    0 => pos
    for k in [0:len(order) - 1]:
        if order[k] == f[2]:
            k => pos
    ("A loop: the two walkers met after " + str(f[1]) + " steps. It starts at [" + str(lst[0][f[2]]) + "], position " + str(pos) + ", and goes round " + str(f[3]) + " nodes.") ^0

links.new_list() => lst
for v in [7, 3, 9, 4, 1]:
    links.insert_at(lst, links.length(lst), v) => lst

"== Linked list playground ==" ^0
"A singly linked list: each node holds a value and the slot of the next node." ^0
True => running
while running:
    "" ^0
    "1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        draw(lst)
    elif choice == "7":
        loop(lst) => lst
    elif choice == "8":
        find_loop(lst)
    elif choice == "9":
        False => running
    elif (choice == "2" or choice == "3" or choice == "4" or choice == "5" or choice == "6") and looped(lst):
        "The list has a loop, so it has no end: break the loop first (7)." ^0
    elif choice == "2":
        add_end(lst) => lst
    elif choice == "3":
        insert(lst) => lst
    elif choice == "4":
        delete(lst) => lst
    elif choice == "5":
        links.reverse(lst) => lst
        draw(lst)
    elif choice == "6":
        middle(lst)
    else:
        "Pick a number from 1 to 9." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import links

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def number(s):
    if len(s) == 0 or len(s) > 3:
        return -1
    n = 0
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n = n * 10 + int(c)
    return n

def lpad(s, n):
    while len(s) < n:
        s = " " + s
    return s

def draw(lst):
    w = links.walk(lst)
    values = lst[0]
    line = "head"
    for i in w[0]:
        line = line + " -> [" + str(values[i]) + "]"
    if w[1] == -1:
        line = line + " -> end"
    else:
        line = line + " -> back to [" + str(values[w[1]]) + "]"
    print("  " + line)
    print("  slot  value  next")
    nexts = lst[1]
    for i in range(0, len(nexts)):
        if nexts[i] == -2:
            print("  " + lpad(str(i), 4) + "  (free)")
        else:
            nx = "end"
            if nexts[i] >= 0:
                nx = str(nexts[i])
            print("  " + lpad(str(i), 4) + lpad(str(values[i]), 7) + lpad(nx, 6))
    print("  head is slot " + str(lst[2]) + ".")

def looped(lst):
    return links.walk(lst)[1] != -1

def ask(prompt, low, high):
    while True:
        a = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
        if a == "":
            return -1
        n = number(a)
        if n >= low and n <= high:
            return n
        print("Type a whole number from " + str(low) + " to " + str(high) + ".")

def add_end(lst):
    if links.length(lst) == 12:
        print("The list is full: 12 nodes.")
        return lst
    v = ask("value", 0, 999)
    if v == -1:
        print("Cancelled.")
        return lst
    lst = links.insert_at(lst, links.length(lst), v)
    draw(lst)
    return lst

def insert(lst):
    if links.length(lst) == 12:
        print("The list is full: 12 nodes.")
        return lst
    v = ask("value", 0, 999)
    if v == -1:
        print("Cancelled.")
        return lst
    p = ask("position", 0, links.length(lst))
    if p == -1:
        print("Cancelled.")
        return lst
    lst = links.insert_at(lst, p, v)
    draw(lst)
    return lst

def delete(lst):
    if links.length(lst) == 0:
        print("The list is empty.")
        return lst
    v = ask("value", 0, 999)
    if v == -1:
        print("Cancelled.")
        return lst
    r = links.delete_value(lst, v)
    if r[1] == -1:
        print("No node holds " + str(v) + ".")
        return lst
    print("Deleted " + str(v) + " from position " + str(r[1]) + "; its slot is free for the next node.")
    draw(r[0])
    return r[0]

def middle(lst):
    n = links.length(lst)
    if n == 0:
        print("The list is empty.")
        return
    m = links.middle(lst)
    v = lst[0][m[0]]
    print(str(n) + " nodes: when the fast walker ran out, the slow one had taken " + str(m[1]) + " steps, to [" + str(v) + "] at position " + str(m[1]) + ".")
    if n % 2 == 0:
        print("With an even number of nodes there are two middles; this way finds the second.")

def loop(lst):
    if looped(lst):
        w = links.walk(lst)
        last = lst[0][w[0][len(w[0]) - 1]]
        lst = links.break_loop(lst)
        print("Loop broken: [" + str(last) + "] points to the end again.")
        draw(lst)
        return lst
    n = links.length(lst)
    if n == 0:
        print("The list is empty.")
        return lst
    p = ask("point the last node back to position", 0, n - 1)
    if p == -1:
        print("Cancelled.")
        return lst
    lst = links.close_loop(lst, p)
    draw(lst)
    return lst

def find_loop(lst):
    f = links.floyd(lst)
    if not f[0]:
        print("No loop: the fast walker reached the end after " + str(f[1]) + " steps.")
        return
    order = links.walk(lst)[0]
    pos = 0
    for k in range(0, len(order)):
        if order[k] == f[2]:
            pos = k
    print("A loop: the two walkers met after " + str(f[1]) + " steps. It starts at [" + str(lst[0][f[2]]) + "], position " + str(pos) + ", and goes round " + str(f[3]) + " nodes.")

lst = links.new_list()
for v in [7, 3, 9, 4, 1]:
    lst = links.insert_at(lst, links.length(lst), v)
print("== Linked list playground ==")
print("A singly linked list: each node holds a value and the slot of the next node.")
running = True
while running:
    print("")
    print("1) draw  2) add at the end  3) insert  4) delete  5) reverse  6) middle  7) close or break a loop  8) look for a loop  9) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        draw(lst)
    elif choice == "7":
        lst = loop(lst)
    elif choice == "8":
        find_loop(lst)
    elif choice == "9":
        running = False
    elif (choice == "2" or choice == "3" or choice == "4" or choice == "5" or choice == "6") and looped(lst):
        print("The list has a loop, so it has no end: break the loop first (7).")
    elif choice == "2":
        lst = add_end(lst)
    elif choice == "3":
        lst = insert(lst)
    elif choice == "4":
        lst = delete(lst)
    elif choice == "5":
        lst = links.reverse(lst)
        draw(lst)
    elif choice == "6":
        middle(lst)
    else:
        print("Pick a number from 1 to 9.")
print("Bye.")
```

### links.eml

```eml
# P073 linked list playground - a singly linked list kept as two parallel
# lists, as in the corpus case linked-list-operations: values[i] is node
# i's payload and nexts[i] the index of the node after it, -1 for the end.
# A deleted node is marked free (next = -2) and its slot is reused by the
# next node made, the way an allocator reuses memory.
#
# A list is [values, nexts, head].

def new_list():
    return [[], [], -1]

def make_node(lst, value):
    # A slot for a new node: the lowest free one, or a new one at the end.
    # Returns [list, index].
    lst[0] => values
    lst[1] => nexts
    -1 => slot
    for i in [0:len(nexts) - 1]:
        if slot == -1 and nexts[i] == -2:
            i => slot
    if slot == -1:
        values + [value] => values
        nexts + [-1] => nexts
        len(values) - 1 => slot
    else:
        value => values[slot]
        -1 => nexts[slot]
    return [[values, nexts, lst[2]], slot]

def walk(lst):
    # The node indices from the head, stopping at the end or at the first
    # node seen twice (a loop): [indices, index the loop goes back to or -1].
    lst[1] => nexts
    [] => out
    [0] * len(nexts) => seen
    lst[2] => cur
    while cur != -1:
        if seen[cur] == 1:
            return [out, cur]
        1 => seen[cur]
        out + [cur] => out
        nexts[cur] => cur
    return [out, -1]

def length(lst):
    return len(walk(lst)[0])

def node_at(lst, pos):
    # The index of the node at position pos (0 = head).
    walk(lst)[0] => order
    return order[pos]

def insert_at(lst, pos, value):
    # Insert value so it becomes position pos (0 = new head, length = at
    # the end): two links change, nothing moves.
    make_node(lst, value) => made
    made[0] => lst
    made[1] => k
    lst[1] => nexts
    if pos == 0:
        lst[2] => nexts[k]
        return [lst[0], nexts, k]
    node_at(lst, pos - 1) => before
    nexts[before] => nexts[k]
    k => nexts[before]
    return [lst[0], nexts, lst[2]]

def delete_value(lst, value):
    # Unlink the first node holding value and free its slot: the node
    # before it skips over it. Returns [list, position deleted or -1].
    lst[0] => values
    lst[1] => nexts
    lst[2] => head
    -1 => prev
    head => cur
    0 => pos
    while cur != -1:
        if values[cur] == value:
            if prev == -1:
                nexts[cur] => head
            else:
                nexts[cur] => nexts[prev]
            -2 => nexts[cur]
            return [[values, nexts, head], pos]
        cur => prev
        nexts[cur] => cur
        pos + 1 => pos
    return [lst, -1]

def reverse(lst):
    # The corpus case's three-pointer walk: turn every link around in one
    # pass, keeping the node that comes next before the link is changed.
    lst[1] => nexts
    -1 => prev
    lst[2] => cur
    while cur != -1:
        nexts[cur] => following
        prev => nexts[cur]
        cur => prev
        following => cur
    return [lst[0], nexts, prev]

def middle(lst):
    # Two walkers from the head, one taking two steps for each one of the
    # other. When the fast one reaches the end, the slow one is in the
    # middle - the second of the two middles when the length is even.
    # Returns [index, steps the slow walker took].
    lst[1] => nexts
    lst[2] => slow
    lst[2] => fast
    0 => steps
    while fast != -1 and nexts[fast] != -1:
        nexts[slow] => slow
        nexts[nexts[fast]] => fast
        steps + 1 => steps
    return [slow, steps]

def close_loop(lst, pos):
    # Point the last node back at the node at position pos.
    walk(lst)[0] => order
    lst[1] => nexts
    order[pos] => nexts[order[len(order) - 1]]
    return [lst[0], nexts, lst[2]]

def break_loop(lst):
    # The last node before the walk comes round again points to the end.
    walk(lst) => w
    lst[1] => nexts
    if w[1] != -1:
        -1 => nexts[w[0][len(w[0]) - 1]]
    return [lst[0], nexts, lst[2]]

def floyd(lst):
    # Floyd's cycle finding with two walkers, using no memory of where
    # either has been: [False, steps] if the fast one reaches the end; otherwise
    # [True, steps to meet, index where the loop starts, loop length].
    # After they meet, a walker from the head and one from the meeting
    # point, one step at a time each, meet exactly where the loop starts.
    lst[1] => nexts
    lst[2] => slow
    lst[2] => fast
    0 => steps
    while fast != -1 and nexts[fast] != -1:
        nexts[slow] => slow
        nexts[nexts[fast]] => fast
        steps + 1 => steps
        if slow == fast:
            lst[2] => a
            slow => b
            while a != b:
                nexts[a] => a
                nexts[b] => b
            1 => n
            nexts[a] => c
            while c != a:
                nexts[c] => c
                n + 1 => n
            return [True, steps, a, n]
    return [False, steps]
```

Python projection of links.eml:

```python
def new_list():
    return [[], [], -1]

def make_node(lst, value):
    values = lst[0]
    nexts = lst[1]
    slot = -1
    for i in range(0, len(nexts)):
        if slot == -1 and nexts[i] == -2:
            slot = i
    if slot == -1:
        values = values + [value]
        nexts = nexts + [-1]
        slot = len(values) - 1
    else:
        values[slot] = value
        nexts[slot] = -1
    return [[values, nexts, lst[2]], slot]

def walk(lst):
    nexts = lst[1]
    out = []
    seen = [0] * len(nexts)
    cur = lst[2]
    while cur != -1:
        if seen[cur] == 1:
            return [out, cur]
        seen[cur] = 1
        out = out + [cur]
        cur = nexts[cur]
    return [out, -1]

def length(lst):
    return len(walk(lst)[0])

def node_at(lst, pos):
    order = walk(lst)[0]
    return order[pos]

def insert_at(lst, pos, value):
    made = make_node(lst, value)
    lst = made[0]
    k = made[1]
    nexts = lst[1]
    if pos == 0:
        nexts[k] = lst[2]
        return [lst[0], nexts, k]
    before = node_at(lst, pos - 1)
    nexts[k] = nexts[before]
    nexts[before] = k
    return [lst[0], nexts, lst[2]]

def delete_value(lst, value):
    values = lst[0]
    nexts = lst[1]
    head = lst[2]
    prev = -1
    cur = head
    pos = 0
    while cur != -1:
        if values[cur] == value:
            if prev == -1:
                head = nexts[cur]
            else:
                nexts[prev] = nexts[cur]
            nexts[cur] = -2
            return [[values, nexts, head], pos]
        prev = cur
        cur = nexts[cur]
        pos = pos + 1
    return [lst, -1]

def reverse(lst):
    nexts = lst[1]
    prev = -1
    cur = lst[2]
    while cur != -1:
        following = nexts[cur]
        nexts[cur] = prev
        prev = cur
        cur = following
    return [lst[0], nexts, prev]

def middle(lst):
    nexts = lst[1]
    slow = lst[2]
    fast = lst[2]
    steps = 0
    while fast != -1 and nexts[fast] != -1:
        slow = nexts[slow]
        fast = nexts[nexts[fast]]
        steps = steps + 1
    return [slow, steps]

def close_loop(lst, pos):
    order = walk(lst)[0]
    nexts = lst[1]
    nexts[order[len(order) - 1]] = order[pos]
    return [lst[0], nexts, lst[2]]

def break_loop(lst):
    w = walk(lst)
    nexts = lst[1]
    if w[1] != -1:
        nexts[w[0][len(w[0]) - 1]] = -1
    return [lst[0], nexts, lst[2]]

def floyd(lst):
    nexts = lst[1]
    slow = lst[2]
    fast = lst[2]
    steps = 0
    while fast != -1 and nexts[fast] != -1:
        slow = nexts[slow]
        fast = nexts[nexts[fast]]
        steps = steps + 1
        if slow == fast:
            a = lst[2]
            b = slow
            while a != b:
                a = nexts[a]
                b = nexts[b]
            n = 1
            c = nexts[a]
            while c != a:
                c = nexts[c]
                n = n + 1
            return [True, steps, a, n]
    return [False, steps]
```

## README

# P073 - Linked list playground

A singly linked list drawn two ways: as the chain from the head, and as
the slots its nodes live in, each with its value and the slot of the
next node. Insert, delete, reverse, find the middle, and close a loop to
watch Floyd's two walkers find it. It starts with 7, 3, 9, 4, 1.

- `main.eml` - the menu, drawing, and the questions
- `links.eml` - the list as values and links: making nodes in free slots,
  walking, insert, delete, reverse, the middle, loops and Floyd's method

How each part works:

- As in the corpus case `linked-list-operations`, a list is two parallel
  lists - values[i] is node i's value and nexts[i] the slot of the node
  after it, -1 for the end - and the slot of the head. Pointers are slot
  numbers.
- Insert changes two links and moves nothing. A deleted node is unlinked
  - the node before it skips over it - and its slot is marked free; the
  next new node takes the lowest free slot, as an allocator reuses memory.
- Reverse is the corpus case's three-pointer walk: keep the next node,
  point the current one back at the previous, step on. One pass, nothing
  new made.
- Middle: two walkers from the head, the fast one taking two steps for
  each one of the slow. When the fast one runs out, the slow one is at
  position n // 2 - with an even number of nodes, the second of the two
  middles.
- Loop: the last node is pointed back at a chosen node. The drawing
  stops where the walk comes round again. Floyd's method finds the loop
  with no memory of where the walkers have been: if there is a loop, the
  fast walker catches the slow one inside it. Then one walker from the
  head and one from the meeting point, a step at a time each, meet
  exactly where the loop starts. A loop has no end, so insert, delete,
  reverse and middle wait until it is broken again.

What is checked: menu choices 1 to 9; values from 0 to 999; positions
inside the list; at most 12 nodes. An empty answer cancels.

Sessions: `sessions/basic.in` gives:
- the list, 5 inserted at position 2, 3 deleted (slot 1 freed), and 8
  added at the end in that freed slot;
- the reverse, with the head now slot 1, and the middle of 6 nodes;
- a loop back to position 2, found: it starts at [4] and goes round 4
  nodes;
- the loop refusing an insert, then broken, and no loop found.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- the values abc and 1000, position 9 of 0 to 5, then a cancel;
- deleting 42, which no node holds; loop position 7 of 0 to 4, then a
  cancel;
- seven nodes added to fill all 12, a thirteenth refused, and the middle
  of 12.

Built on the verified corpus case `linked-list-operations` (values and
next-indices in parallel lists, and the three-pointer reverse).