Skip list

Keywords: Skip list, Cota superior asintótica, Estructura de datos, Lista (estructura de datos), Programación paralela, Árbol binario

Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones).

Una lista por saltos se construye por capas. La capa del fondo es una sencilla lista enlazada. Cada capa subsiguiente es como una "vía rápida" para la lista de la capa anterior. Un elemento de la capa i aparece en la capa i+1 con una probabilidad fija p. En promedio, cada elemento aparece en 1/(1-p) listas, el elemento más alto (generalmente un elemento inicial colocado al principio de la lista por saltos) aparece en O(log(1/p) n) listas.

1
 1-----4---6
 1---3-4---6-----9
 1-2-3-4-5-6-7-8-9-10

Para buscar un elemento, se inicia con el elemento inicial de la lista de la capa más alta hasta alcanzar el máximo elemento que es menor o igual al buscado, se pasa a la capa anterior y se continua la búsqueda. Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p. De manera que el costo total de búsqueda es O(log(1/p) n / p), que es lo mismo que O(log n) cuando p es una constante. Dependiendo del valor de escogido para p, se puede favorecer el costo de búsqueda contra el costo de almacenamiento.

Las operaciones de inserción y borrado se implantan como las de sus correspondientes listas enlazadas, salvo que los elementos de las capas superiores deben ser insertados o borrados de más de una lista enlazada.

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. Sin embargo, las listas por saltos trabajan bien en la práctica y el esquema de balanceo es más sencillo de implementar que el de los aboles binarios balanceados. Las listas por saltos son útiles también para cómputo paralelo, dado que se pueden realizar inserciones en paralelo en sobre segmentos diferentes sin tener luego que balancear la estructura.

Origen

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. Ver también en .

El creador de la estructura de datos las describe así:

Las listas por saltos son una estructura probabilística que podría remplazar los árboles balanceados como método de implementación preferido en muchas aplicaciones. Las operaciones de listas por saltos tienen el mismo comportamiento asintótico esperado que las de los árboles balanceados, son más rápidas y utilizan menos espacio.