¿Qué es una lista de omisión?

Una lista de omisión es una estructura de datos probabilística. La lista de omisión se utiliza para almacenar una lista ordenada de elementos o datos con una lista vinculada. Permite visualizar el proceso de los elementos o datos de manera eficiente. En un solo paso, se salta varios elementos de la lista completa, por eso se la conoce como lista de omisión.

La lista de omisión es una versión extendida de la lista vinculada. Permite al usuario buscar, eliminar e insertar el elemento muy rápidamente. Consiste en una lista base que incluye un conjunto de elementos que mantiene la jerarquía de enlaces de los elementos posteriores.

Saltar estructura de lista

Está construido en dos capas: la capa más baja y la capa superior.

La capa más baja de la lista de omisión es una lista enlazada ordenada común, y las capas superiores de la lista de omisión son como una 'línea rápida' donde se omiten los elementos.

Tabla de complejidad de la lista de omisión

Funcionamiento de la lista de omisión

Tomemos un ejemplo para comprender el funcionamiento de la lista de omisión. En este ejemplo, tenemos 14 nodos, de modo que estos nodos se dividen en dos capas, como se muestra en el diagrama.

La capa inferior es una línea común que une todos los nodos, y la capa superior es una línea rápida que une sólo los nodos principales, como puedes ver en el diagrama.

Suponga que desea encontrar 47 en este ejemplo. Comenzará la búsqueda desde el primer nodo de la línea rápida y continuará corriendo en la línea rápida hasta encontrar un nodo que sea igual a 47 o mayor que 47.

Puedes ver en el ejemplo que 47 no existe en la línea express, entonces buscas un nodo menor que 47, que es 40. Ahora, vas a la línea normal con ayuda de 40, y buscas el 47, como se muestra en el diagrama.

Nota: Una vez que encuentre un nodo como este en la 'línea rápida', vaya de este nodo a un 'carril normal' usando un puntero, y cuando busque el nodo en la línea normal.

Saltar lista de operaciones básicas

Existen los siguientes tipos de operaciones en la lista de omisión.

Operación de inserción:Se utiliza para agregar un nuevo nodo a una ubicación particular en una situación específica.Operación de eliminación:Se utiliza para eliminar un nodo en una situación específica.Operación de búsqueda:La operación de búsqueda se utiliza para buscar un nodo particular en una lista de omisión.

Algoritmo de la operación de inserción.

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Algoritmo de operación de eliminación.

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Algoritmo de operación de búsqueda.

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

Ejemplo 1: Cree una lista de omisión, queremos insertar las siguientes claves en la lista de omisión vacía.

1. 6 con nivel 1.
2. 29 con nivel 1.
3. 22 con nivel 4.
4. 9 con nivel 3.
5. 17 con nivel 1.
6. 4 con nivel 2.

Años:

Paso 1: Insertar 6 con nivel 1

Paso 2: Insertar 29 con nivel 1

Paso 3: Insertar 22 con nivel 4

Etapa 4: Insertar 9 con nivel 3

Paso 5: Insertar 17 con nivel 1

Paso 6: Insertar 4 con nivel 2

Ejemplo 2: Considere este ejemplo en el que queremos buscar la clave 17.

Años:

Ventajas de la lista de omisión

1. Si desea insertar un nuevo nodo en la lista de omisión, insertará el nodo muy rápido porque no hay rotaciones en la lista de omisión.
2. La lista de omisión es sencilla de implementar en comparación con la tabla hash y el árbol de búsqueda binario.
3. Es muy sencillo encontrar un nodo en la lista porque almacena los nodos ordenados.
4. El algoritmo de la lista de omisión se puede modificar muy fácilmente en una estructura más específica, como listas de omisión indexables, árboles o colas de prioridad.
5. La lista de omisiones es una lista sólida y confiable.

Desventajas de la lista de omisión

1. Requiere más memoria que el árbol equilibrado.
2. No se permite la búsqueda inversa.
3. La lista de omisión busca el nodo mucho más lentamente que la lista vinculada.

Aplicaciones de la lista Skip

1. Se utiliza en aplicaciones distribuidas y representa los punteros y el sistema en las aplicaciones distribuidas.
2. Se utiliza para implementar una cola concurrente elástica dinámica con baja contención de bloqueo.
3. También se utiliza con la clase de plantilla QMap.
4. La indexación de la lista de omisión se utiliza para ejecutar problemas de mediana.
5. La lista de omisión se utiliza para la publicación de codificación delta en la búsqueda de Lucene.