Totul porneste de la o lista simplu inlantuita in care fiecare element are un link (pointer sau orice altceva care poate indica alt element) catre urmatorul element din lista. Presupunem ca aceasta lista o tinem sortata. Ce ar fi daca de la elementul $x$ nu am sari la elementul {$x+1$}? Ce ar fi daca am sari la {$x+2$}? Acesta este principiul din spatele Skiplist-urilor.

Intr-un Skiplist fiecare element are un grad, numarul de link-uri la alte elemente. Un link de nivelul $x$ va indica un element care are cel putin $x$ nivele, astfel este posibil ca sa parcurgem toata lista cu link-uri de un anumit nivel. Cheia este ca, cu cat nivelul este mai mare, elemente de nivelul respectiv sunt mai rare, link-urile sunt din ce in ce mai putine si astfel pointeaza mai departe. La nivelul minim, {$0$}, exista un link catre elementul exact urmator, iar cu cat crestem nivelul, cu atat link-urile sunt mai rare si "sar" peste mai multe elemente, de unde vine si denumirea de Skiplist-uri, liste cu salt.

Intr-un Skiplist fiecare element are un grad, numarul de link-uri la alte elemente. Un link de nivelul $x$ va indica un element care are cel putin $x$ nivele, astfel este posibil ca sa parcurgem toata lista cu link-uri de un anumit nivel. Cheia este ca, cu cat nivelul este mai mare, elemente de nivelul respectiv sunt mai rare, link-urile sunt din ce in ce mai putine si astfel pointeaza mai departe. La nivelul minim,{$0$}, exista un link catre elementul exact urmator, iar cu cat crestem nivelul, cu atat link-urile sunt mai rare si "sar" peste mai multe elemente, de unde vine si denumirea de Skiplist-uri, liste cu salt.

h2. Implementare

    }
==

Acest algoritm ne da nodul din fata elementului cautat, daca acesta exista, sau cel care are cel mai mare key mai mic decat cel cautat. De aici e simplu sa vedem daca elementul cautat exista in Skiplist, ar trebui sa fie {$x->link {~0~}$ (urmatorul element, pe nivelul $0$ structura este o lista simplu inlantuita). De asemenea ne mai ramane si {$temp$}, $temp$ contine acum toate nodurile din fata elementului curent care indica catre elemente de la $x$ in sus. Acest vector $temp$ este o modalitate de a evita listele dublu-inlantuite, si a injumatati consumul de memorie.

Acest algoritm ne da nodul din fata elementului cautat, daca acesta exista, sau cel care are cel mai mare key mai mic decat cel cautat. De aici e simplu sa vedem daca elementul cautat exista in Skiplist, ar trebui sa fie $x->link{~0~}$ (urmatorul element, pe nivelul $0$ structura este o lista simplu inlantuita). De asemenea ne mai ramane si {$temp$}, $temp$ contine acum toate nodurile din fata elementului curent care indica catre elemente de la $x$ in sus. Acest vector $temp$ este o modalitate de a evita listele dublu-inlantuite, si a injumatati consumul de memorie.

OK, dar cum se fac celelalte operatii? Sa le luam pe rand...

}
==

Predecesorul si succesorul fiecarui nod se iau pur si simplu din node->prev, respectiv node->link{~0~}.

Predecesorul si succesorul fiecarui nod se iau pur si simplu din node->prev, respectiv $node->link{~0~}$