int grad = grad_max;
nod temp[grad_max];
    while (gradul >= 0) {

        while ((x->link[grad] != NULL)
                &&(x->link[grad]->key < cheie_cautata)) {

        while (x->link[grad] != NULL && x->link[grad]->key < cheie_cautata)

            x=x->link[grad];

            temp[grad]=x;
        }

        temp[grad]=x;

        grad--;
    }
==

Memorie este oarecum evident {$O(N)$}. Daca skiplist-ul ar fi complet echilibrat atunci vor exista $N$ link-uri de nivel {$0$}, {$N/2$} de nivel {$1$}, {$N/4$} de nivel {$2$}, etc. Cu putina matematica {$N + N/2 + N/4 + N/8.. = 2 * N$}, adica {$O(n)$}. Pentru cei care programeaza in pascal si nu vor sa se complice cu alocare de array-uri dinamice, memoria va fi evident $O(N log N)$

h2. Skip Lists vs. AVL - Timpi de executie
 
Am testat pe laptopul meu implementearea AVL (vezi articolul http://infoarena.ro/Multe-smenuri-de-programare-in-CC-si-nu-numai) vs. Skiplists (vezi implementarea de mai jos). Laptopul este destul de performant, dar important este raportul dintre timpii de executie la AVL, respectiv Skiplists.
 
|_. Numar de inserari |_. Numar de stergeri |_. Numar de Cautari |_. Timp Skiplists(1) |_. Timp AVL(2) |_. Raportul timpilor (2) / (1)|
|1.000.000	|0	|0	|1.265	|2.656	|2.099604743|
|1.000.000	|0	|1.000.000	|1.479	|2.672	|1.806626099|
|1.000.000	|1.000.000	|0	|1.969	|4.797	|2.436262062|
|1.000.000	|1.000.000	|1.000.000	|2.437	|4.85	|1.990151826|
 
 
 

h2. Extinderi
Pe langa algoritmii de baza skip list permite imbogatiri care va permit multe alte lucruri cu timp minim de implementare si complexitate {$O(log N)$}. Cam toate imbogatirile structurii se bazeaza pe memorarea in paralel a unor informatii ajutatoare pt fiecare link (ATENTIE in pascal)