The Junction Linked List (JLI): An Externally Indexed Sorted Linked List and an Empirical Comparison with the Skip List

An externally indexed sorted linked list, and an honest empirical comparison with the skip list The idea. A skip list stores its index inside every node and keeps it correct on every insert. JLI does the opposite. Nodes hold only a key, a payload pointer and a next pointer. Everything needed for fast search lives outside them, in junctions with shortcut arrays, blocks, and a skip list over the blocks. A mutation touches only the list and one junction, so the index may be slightly wrong. That is safe because a stale shortcut costs a slightly longer walk, never a wrong answer. Three escalating maintenance tiers keep the staleness bounded. What we found (vs. a textbook skip list, same C harness, 87 configurations, 10 to 1M keys): Memory: 75–80% of the skip list’s analytical memory in every configuration. Build: 2.1–2.2× faster than incremental insertion. Search: faster in 25 of 30 configurations, by small margins (ratios 0.81–1.23). The size dependence did not replicate on a second machine. Mutation: usually slower, but within 11% of the skip list in 21 of 25 insertion and 15 of 25 deletion configurations. Deferred maintenance has a break-even point. It costs up to 38% of JLI’s insertion latency on short runs, but on long runs it lowers it by up to 23%. With it off, JLI drifts to about 1.5× the skip list’s latency. A tail-sealing rule makes monotonic appends O(1) amortised, and tail appends beat the skip list by 14–35%. Its mirror, deletion from the tail, is JLI’s weakest case, reaching 2.05× at 1M keys.