Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 questionslinks.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (30 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (18 lines)
1
3
5
2
4
3
2
8
5
6
7
2
1
8
2
7
8
9
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (links.py)
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]