Atlamalı liste (skip list)

Kısaca: Atlamalı liste, öğelerin ortalama O(log n)‘de bulunabilmesi için ek “ekspres şeritleri” olan sıralı bağlı bir listedir.

Biraz daha ayrıntılı: En alt düzey tüm öğeleri içerir. Her üst düzey, rastgele seçilmiş olarak, alttaki düzeyin öğelerinin yaklaşık yarısını içerir. Arama en üstten başlar, uzağa sıçrar ve aşacağı zaman aşağı iner.