It is tempting to return true the moment x.next[level].key == key part way down. For a pure search that is correct and saves a few drops, but for insert and delete it is a real bug: those need update[level], the last node before the key, at every level, and you only have the full path once the descent reaches the bottom. Size update[] for maxLevel and start it at head, not at the list's current level, since a new node can be taller than anything present and the head is its predecessor on those lanes.