Skip list to wielopoziomowa lista, gdzie część węzłów jest losowo „promowana” do wyższych poziomów. Daje oczekiwane O(log n) dla search/insert/delete (jak zbalansowane drzewa), jest prostsza w implementacji, ale ma probabilistyczną wydajność.