Coding and AI classes in Pontypridd

The data is every CF37 postcode in Ordnance Survey's Code-Point Open, 885 of them, sorted from CF37 1AA upwards. The question is simple: how many times must the program compare two postcodes before it finds the one it wants? The slowest answer is to start at the top and read down, which takes 443 comparisons on average. The usual fast answer is binary search, the method behind Python's bisect module: look at the middle, discard the half that cannot hold the target, repeat. That takes 10.85 comparisons on average, close to the 9.79 you get from log base 2 of 885.

Binary search needs the whole list stored in one block so it can jump straight to the middle. A linked list, where each postcode only knows the next one, cannot jump. The skip list fixes that by adding lanes. Every postcode sits on level 1. A coin toss decides whether it also sits on level 2; if that toss succeeds, another toss decides level 3, and so on. A search starts on the highest lane, runs forward until the next stop would overshoot, drops down a lane, and repeats until it reaches level 1.

The skip list figures are averages over 20 separate random builds, and the builds really do differ: with fair coins, the average search ranged from 16.89 to 20.64 comparisons depending on how the tosses fell, the tallest tower reached between 8 and 13 levels, and the single worst search in all 20 builds took 37 comparisons. In one build, seeded 20261001, the levels split 464, 199, 105, 57, 30, 13, 8, 4 and 5 from the bottom up, close to halving at each step as a fair coin should give; in that build, finding CF37 1DL took 15 comparisons, against 11 for binary search. Biased coins that rarely promote save memory, about a third of a link per postcode instead of one, at the price of a worse unlucky case: 49 comparisons for the slowest search.

So binary search wins on reading. Why would anyone choose a skip list? Because the CF37 list changes as new streets are built. Inserting one postcode into a Python list means shifting everything after it along by one, about half the list on average. Inserting into a skip list means tossing coins for the new entry and rewiring around two links on average. That trade, slightly slower searching for much cheaper updating, is why skip lists still sit inside working systems: the Redis database uses one for its sorted sets.

For a Pontypridd teenager, measuring before trusting is what keeps them in charge of AI tools rather than led by them, and that habit comes from writing the code. The longer argument is in why it still pays to learn coding in 2026.