Skip list

La capa del fondo (la más baja) es una sencilla lista enlazada.

Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p.

A diferencia de los árboles de búsqueda balanceados, el peor caso para las operaciones de listas por saltos no está garantizado como logarítmico, dado que es posible aunque poco probable, que se produzca una estructura no balanceada.

Las listas por saltos son útiles también para cómputo paralelo, dado que se pueden realizar inserciones en paralelo sobre segmentos diferentes sin tener luego que balancear la estructura.

Las listas por saltos fueron creadas por William Pugh y publicadas en su artículo Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676.