Lista de saltos
Estructura de datos probabilística — una lista enlazada ordenada con "expresos" en niveles superiores que permiten saltar elementos. Tiempo esperado O(log n).
William Pugh (1989) la propuso como alternativa más sencilla a los árboles balanceados. Cada nodo tiene un número aleatorio de "punteros hacia arriba" (clásicamente p=0,5 por nivel). Búsqueda: empezar arriba del todo, saltar a la derecha lo más lejos posible, bajar un nivel, repetir.
Impulsa los sorted sets de Redis (ZSET), la memtable de LevelDB/RocksDB y las posting lists de Lucene. Ventaja frente a los árboles balanceados: implementación lock-free más sencilla, mejor localidad de caché. Lo que pierde: el peor caso garantizado (puede ser O(n) con mala suerte).