Linked-list toolkit: dummies and test helpers

py/try_helpers.py

from lists import from_list, show, to_list

route = from_list([12, 7, 31])
print(show(route))
print(route.val, route.next.val, route.next.next.val, route.next.next.next)
print(to_list(route), to_list(from_list([])), show(None))

# A test is one line: build from a list, call the function, compare as a list.
assert to_list(from_list([5, 5, 2])) == [5, 5, 2]

# A rewiring bug can make the last node point back into the list. to_list stops and says so.
loop = from_list([3, 7, 1, 9])
loop.next.next.next.next = loop.next  # 9 now points back at 7
try:
    to_list(loop)
except ValueError as error:
    print("ValueError:", error)

12 -> 7 -> 31 -> None
12 7 31 None
[12, 7, 31] [] None
ValueError: cycle: after 4 nodes the list returns to position 1

py/lists.py

"""Test helpers for singly linked lists: build one from a Python list, read it back, and print it."""


class ListNode:
    """One node: a value and a reference to the next node (None after the last node)."""

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def from_list(values):
    """Build a linked list holding `values` in order and return its head (None for no values)."""
    dummy = ListNode(None)  # a node in front of the head, so the first append is like every other
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head):
    """Return the values from `head` to the end, in order.

    A list that loops back on itself has no end; instead of running forever, this raises ValueError and says where
    the loop closes.
    """
    values = []
    position = {}  # id of each node seen -> its position
    node = head
    while node is not None:
        if id(node) in position:
            raise ValueError(f"cycle: after {len(values)} nodes the list returns to position {position[id(node)]}")
        position[id(node)] = len(values)
        values.append(node.val)
        node = node.next
    return values


def show(head):
    """The list as one line of text, such as 3 -> 1 -> 4 -> None."""
    return " -> ".join([*map(str, to_list(head)), "None"])

py/stops.py

import random

from lists import ListNode, from_list, show, to_list


def remove_cancelled_no_dummy(head, cancelled):
    """Without a dummy: the head needs a loop of its own."""
    gone = set(cancelled)
    while head is not None and head.val in gone:  # cancelled stops at the front
        head = head.next
    node = head
    while node is not None and node.next is not None:
        if node.next.val in gone:
            node.next = node.next.next  # unlink, and look at the new next before moving on
        else:
            node = node.next
    return head


def remove_cancelled(head, cancelled):
    """With a dummy in front of the head: one loop for every stop, the first one included."""
    gone = set(cancelled)
    dummy = ListNode(None, head)
    prev = dummy  # the last stop kept so far
    while prev.next is not None:
        if prev.next.val in gone:
            prev.next = prev.next.next  # unlink; prev stays, its new next is not checked yet
        else:
            prev = prev.next
    return dummy.next


EXAMPLES = [
    ([4, 9, 4, 15, 2], [4, 2]),
    ([8, 8, 3], [8]),
    ([5, 6], [5, 6]),
    ([], [1]),
]
for route, cancelled in EXAMPLES:
    print(f"{route} without {cancelled}: {show(remove_cancelled(from_list(route), cancelled))}")

# The nodes that stay are the caller's own nodes: no copies.
head = from_list([4, 9, 4, 15, 2])
nine = head.next
print("the 9 node is the new head:", remove_cancelled(head, [4, 2]) is nine)

# Both versions against a plain list filter, on 2,000 random routes with repeated stop numbers.
rng = random.Random(7)
for _ in range(2000):
    route = [rng.randint(1, 6) for _ in range(rng.randint(0, 9))]
    cancelled = rng.sample(range(1, 7), rng.randint(0, 4))
    expected = [stop for stop in route if stop not in cancelled]
    assert to_list(remove_cancelled(from_list(route), cancelled)) == expected
    assert to_list(remove_cancelled_no_dummy(from_list(route), cancelled)) == expected
print("2000 random routes: both versions match the list filter")

[4, 9, 4, 15, 2] without [4, 2]: 9 -> 15 -> None
[8, 8, 3] without [8]: 3 -> None
[5, 6] without [5, 6]: None
[] without [1]: None
the 9 node is the new head: True
2000 random routes: both versions match the list filter

py/lists.py

"""Test helpers for singly linked lists: build one from a Python list, read it back, and print it."""


class ListNode:
    """One node: a value and a reference to the next node (None after the last node)."""

    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def from_list(values):
    """Build a linked list holding `values` in order and return its head (None for no values)."""
    dummy = ListNode(None)  # a node in front of the head, so the first append is like every other
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


def to_list(head):
    """Return the values from `head` to the end, in order.

    A list that loops back on itself has no end; instead of running forever, this raises ValueError and says where
    the loop closes.
    """
    values = []
    position = {}  # id of each node seen -> its position
    node = head
    while node is not None:
        if id(node) in position:
            raise ValueError(f"cycle: after {len(values)} nodes the list returns to position {position[id(node)]}")
        position[id(node)] = len(values)
        values.append(node.val)
        node = node.next
    return values


def show(head):
    """The list as one line of text, such as 3 -> 1 -> 4 -> None."""
    return " -> ".join([*map(str, to_list(head)), "None"])

js/stops.mjs

import { ListNode, fromList, show } from './lists.mjs';

/** Remove every stop whose number is in `cancelled`; return the new head. */
export function removeCancelled(head, cancelled) {
  const gone = new Set(cancelled);
  const dummy = new ListNode(null, head);
  let prev = dummy; // the last stop kept so far
  while (prev.next !== null) {
    if (gone.has(prev.next.val)) prev.next = prev.next.next;
    else prev = prev.next;
  }
  return dummy.next;
}

const examples = [
  [[4, 9, 4, 15, 2], [4, 2]],
  [[8, 8, 3], [8]],
  [[5, 6], [5, 6]],
  [[], [1]],
];
for (const [route, cancelled] of examples) {
  const result = show(removeCancelled(fromList(route), cancelled));
  console.log(`[${route.join(', ')}] without [${cancelled.join(', ')}]: ${result}`);
}

[4, 9, 4, 15, 2] without [4, 2]: 9 -> 15 -> null
[8, 8, 3] without [8]: 3 -> null
[5, 6] without [5, 6]: null
[] without [1]: null

js/lists.mjs

// Test helpers for singly linked lists: build one from an array, read it back, and print it.

export class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next; // null after the last node
  }
}

/** Build a linked list holding `values` in order and return its head (null for no values). */
export function fromList(values) {
  const dummy = new ListNode(null);
  let tail = dummy;
  for (const v of values) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

/** The values from `head` to the end. A list that loops back on itself throws instead of running forever. */
export function toList(head) {
  const values = [];
  const position = new Map(); // node -> its position
  for (let node = head; node !== null; node = node.next) {
    if (position.has(node)) {
      throw new Error(`cycle: after ${values.length} nodes the list returns to position ${position.get(node)}`);
    }
    position.set(node, values.length);
    values.push(node.val);
  }
  return values;
}

/** The list as one line of text, such as 3 -> 1 -> 4 -> null. */
export const show = (head) => [...toList(head), 'null'].join(' -> ');

Java · compiled/Stops.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Stops {
    static final class ListNode {
        int val;
        ListNode next; // null after the last node

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromList(int... values) {
        ListNode dummy = new ListNode(0, null); // its value is never read
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v, null);
            tail = tail.next;
        }
        return dummy.next;
    }

    /** The values from head to the end; a list that loops back on itself throws instead of running forever. */
    static List<Integer> toList(ListNode head) {
        List<Integer> values = new ArrayList<>();
        Map<ListNode, Integer> position = new IdentityHashMap<>();
        for (ListNode node = head; node != null; node = node.next) {
            Integer seen = position.putIfAbsent(node, values.size());
            if (seen != null) {
                throw new IllegalStateException("cycle: after " + values.size() + " nodes the list returns to position " + seen);
            }
            values.add(node.val);
        }
        return values;
    }

    static String show(ListNode head) {
        StringBuilder text = new StringBuilder();
        for (int v : toList(head)) text.append(v).append(" -> ");
        return text.append("null").toString();
    }

    static ListNode removeCancelled(ListNode head, int[] cancelled) {
        Set<Integer> gone = new HashSet<>();
        for (int stop : cancelled) gone.add(stop);
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy; // the last stop kept so far
        while (prev.next != null) {
            if (gone.contains(prev.next.val)) prev.next = prev.next.next;
            else prev = prev.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[][][] examples = {
            {{4, 9, 4, 15, 2}, {4, 2}},
            {{8, 8, 3}, {8}},
            {{5, 6}, {5, 6}},
            {{}, {1}},
        };
        for (int[][] e : examples) {
            String result = show(removeCancelled(fromList(e[0]), e[1]));
            System.out.println(Arrays.toString(e[0]) + " without " + Arrays.toString(e[1]) + ": " + result);
        }
    }
}

C++ · compiled/stops.cpp

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;  // nullptr after the last node
};

ListNode* from_list(const std::vector<int>& values) {
    ListNode dummy{0, nullptr};  // on the stack: it is never deleted
    ListNode* tail = &dummy;
    for (int v : values) {
        tail->next = new ListNode{v, nullptr};
        tail = tail->next;
    }
    return dummy.next;
}

// The values from head to the end; a list that loops back on itself throws instead of running forever.
std::vector<int> to_list(const ListNode* head) {
    std::vector<int> values;
    std::unordered_map<const ListNode*, std::size_t> position;
    for (const ListNode* node = head; node != nullptr; node = node->next) {
        auto [it, added] = position.try_emplace(node, values.size());
        if (!added) {
            throw std::runtime_error("cycle: after " + std::to_string(values.size()) +
                                     " nodes the list returns to position " + std::to_string(it->second));
        }
        values.push_back(node->val);
    }
    return values;
}

std::string show(const ListNode* head) {
    std::string text;
    for (int v : to_list(head)) text += std::to_string(v) + " -> ";
    return text + "nullptr";
}

void free_list(ListNode* head) {
    while (head != nullptr) {
        ListNode* next = head->next;  // save next before the node is deleted
        delete head;
        head = next;
    }
}

ListNode* remove_cancelled(ListNode* head, const std::vector<int>& cancelled) {
    std::unordered_set<int> gone(cancelled.begin(), cancelled.end());
    ListNode dummy{0, head};
    ListNode* prev = &dummy;  // the last stop kept so far
    while (prev->next != nullptr) {
        ListNode* cur = prev->next;
        if (gone.contains(cur->val)) {
            prev->next = cur->next;  // unlink first, then free: nothing points to cur any more
            delete cur;
        } else {
            prev = cur;
        }
    }
    return dummy.next;
}

std::string bracketed(const std::vector<int>& values) {
    std::string text = "[";
    for (std::size_t i = 0; i < values.size(); ++i) text += (i ? ", " : "") + std::to_string(values[i]);
    return text + "]";
}

int main() {
    const std::vector<std::pair<std::vector<int>, std::vector<int>>> examples = {
        {{4, 9, 4, 15, 2}, {4, 2}},
        {{8, 8, 3}, {8}},
        {{5, 6}, {5, 6}},
        {{}, {1}},
    };
    for (const auto& [route, cancelled] : examples) {
        ListNode* head = remove_cancelled(from_list(route), cancelled);
        std::cout << bracketed(route) << " without " << bracketed(cancelled) << ": " << show(head) << '\n';
        free_list(head);
    }
}

compiled/run_stops.py

"""Builds and runs Stops.java (compiled for Java 21 and later) and stops.cpp (C++23 with sanitizers)."""
from terminal import run

run("""
java --version | head -n 1 | cut -d ' ' -f 1,2
javac --release 21 -d classes Stops.java
java -cp classes Stops
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined stops.cpp -o stops
./stops
""")

$ java --version | head -n 1 | cut -d ' ' -f 1,2
openjdk 27
$ javac --release 21 -d classes Stops.java
$ java -cp classes Stops
[4, 9, 4, 15, 2] without [4, 2]: 9 -> 15 -> null
[8, 8, 3] without [8]: 3 -> null
[5, 6] without [5, 6]: null
[] without [1]: null
$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined stops.cpp -o stops
$ ./stops
[4, 9, 4, 15, 2] without [4, 2]: 9 -> 15 -> nullptr
[8, 8, 3] without [8]: 3 -> nullptr
[5, 6] without [5, 6]: nullptr
[] without [1]: nullptr

compiled/terminal.py

"""Runs commands as you would type them in a terminal and prints the session: each command after "$ ", then what it
printed (standard output and standard error together). A failing command adds its exit status, and the session stops.

Java is the OpenJDK that Homebrew installs (its folder goes first on PATH when it exists); C++ is built with the
system's clang++. An AddressSanitizer report is cut to the lines that say what went wrong and where: the error, the
access, and the stack frames in this folder's own files. Memory addresses and the process number change on every run,
so they are printed as 0x… and ==…==.
"""
import os
import re
import subprocess

JDK_BIN = "/opt/homebrew/opt/openjdk/bin"
ADDRESS = re.compile(r"0x[0-9a-fA-F]+")
FRAME = re.compile(r"^\s*#(\d+) 0x[0-9a-fA-F]+ in (.+?) (\S+?):(\d+)(?::\d+)?$")


def shorten(lines):
    """Keeps the lines of a sanitizer report that a reader needs; other lines pass through unchanged."""
    start = next((i for i, line in enumerate(lines) if "ERROR: AddressSanitizer" in line), None)
    if start is None:
        return lines
    own = {name for name in os.listdir(".") if name.endswith(".cpp")}
    kept, dropped = [line for line in lines[:start] if not line.startswith("=====")], 0
    for line in lines[start:]:
        frame = FRAME.match(line)
        if "ERROR: AddressSanitizer" in line:
            kept.append(ADDRESS.sub("0x…", re.sub(r"^==\d+==", "==…==", line).split(" at pc ")[0]))
        elif re.match(r"^(READ|WRITE) of size \d+", line):
            kept.append(ADDRESS.sub("0x…", line))
        elif re.match(r"^(freed|previously allocated) by thread", line):
            kept.append(line)
        elif frame and os.path.basename(frame.group(3)) in own:
            kept.append(f"    #{frame.group(1)} in {frame.group(2)} {os.path.basename(frame.group(3))}:{frame.group(4)}")
        else:
            dropped += 1
    kept.append(f"[{dropped} more lines of the report left out]")
    return kept


def run(script):
    env = dict(os.environ, ASAN_OPTIONS="color=never", UBSAN_OPTIONS="color=never")
    if os.path.isdir(JDK_BIN):
        env["PATH"] = os.pathsep.join([JDK_BIN, env.get("PATH", "")])
    for command in script.strip().splitlines():
        command = command.strip()
        print(f"$ {command}", flush=True)
        result = subprocess.run(command, shell=True, env=env, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)
        for line in shorten(result.stdout.splitlines()):
            print(line.rstrip())
        if result.returncode != 0:
            status = result.returncode if result.returncode > 0 else 128 - result.returncode
            print(f"[exit status {status}]")
            return