Saltar lista
En informática , una lista de saltos es una estructura de datos probabilísticos que permite la complejidad de búsqueda, así como la complejidad de inserción dentro de una secuencia ordenada de elementos. Por lo tanto, puede obtener las mejores características de una matriz ordenada (para buscar) mientras mantiene una lista vinculada-estructura similar que permite la inserción, lo que no es posible con una matriz estática. La búsqueda rápida es posible manteniendo una jerarquía vinculada de subsecuencias, con cada subsecuencia sucesiva saltando menos elementos que la anterior (ver la imagen a continuación a la derecha). La búsqueda comienza en la subsecuencia más escasa hasta que se encuentran dos elementos consecutivos, uno más pequeño y otro más grande o igual que el elemento buscado. A través de la jerarquía vinculada, estos dos elementos se vinculan con elementos de la siguiente subsecuencia más escasa, donde la búsqueda continúa hasta que finalmente estamos buscando en la secuencia completa. Los elementos que se saltan pueden elegirse de manera probabilística [2] o determinista, [3] siendo más común la primera.
Una lista de saltos se construye en capas. La capa inferior es una lista enlazada ordenada ordinaria . Cada capa superior actúa como un "carril rápido" para las listas a continuación, donde un elemento en la capa aparece en la capa con alguna probabilidad fija (dos valores comúnmente usados para son o ). En promedio, cada elemento aparece en las listas, y el elemento más alto (generalmente un elemento de cabeza especial al frente de la lista de saltos) aparece en todas las listas. La lista de omisión contiene (es decir, base de logaritmo de ) listas.
