Introducción
Las listas enlazadas tienen un gran problema en términos de eficiencia: la búsqueda de elementos es demasiado lenta. Su complejidad de búsqueda secuencial es O(n), lo que significa que el número de elementos en la lista determinará directamente la cantidad de operaciones necesarias para encontrar un valor. Por ejemplo, si una lista contiene un millón de elementos, el algoritmo deberá realizar un millón de comprobaciones para encontrar el dato deseado.
¿Qué es una lista por saltos (skip list)?
Las listas por saltos solucionan este problema mejorando la eficiencia de las búsquedas, pero requieren que la lista esté previamente ordenada. El principio detrás de las listas por saltos es duplicar la lista original, pero eliminando ciertos elementos en cada nueva copia, generando varios niveles de índices. Cada nivel contiene menos elementos que el anterior, creando una estructura escalonada que acelera la búsqueda.
- Lista normal:
- Lista por saltos
Cómo funcionan las listas por saltos
Generación de niveles
- La lista original contiene todos los elementos.
- El segundo nivel es una copia reducida del primero, y así sucesivamente.
- La altura de cada elemento en la lista (es decir, el número de niveles en el que aparece) se determina de forma probabilística.
Probabilidad de altura
- Imagina que lanzas una moneda: por cada “cara” obtenida, aumentas la altura de un elemento.
- Es posible que un elemento alcance grandes alturas si “cara” se obtiene repetidamente, aunque la probabilidad disminuye con cada lanzamiento adicional.
Esto se implementa en programación utilizando generadores de números aleatorios para simular el lanzamiento de una moneda.
Ejemplo de búsqueda con una lista por saltos
Supongamos que buscamos el valor 31 en una lista con esta estructura:
- Nivel 3: 17
- Nivel 2: 17 → 25 → 55
- Nivel 1: 3 → 17 → 25 → 31 → 55
El proceso es el siguiente:
- Inicia en el nivel más alto. Compara el valor objetivo (31) con los elementos de este nivel.
- Si el valor objetivo es mayor al elemento actual (por ejemplo, 17), descarta todos los elementos menores y baja al siguiente nivel.
- Repite este proceso hasta encontrar el valor o agotar los niveles.
Complejidad del algoritmo
La gran ventaja de las listas por saltos es que su complejidad de búsqueda es O(log(n)), lo que las hace mucho más eficientes que la búsqueda secuencial. A medida que aumenta la cantidad de datos, las operaciones necesarias para localizar un elemento crecen de manera logarítmica, en lugar de lineal.
¿Dónde se usan las listas por saltos?
Las listas por saltos son una estructura de datos ampliamente utilizada en bases de datos, sistemas de archivos y otros contextos donde se necesita realizar búsquedas rápidas en conjuntos de datos grandes.
