Skiplisten:
Darstellung:
Menge von Knoten. Jeder Knoten n hat die Felder
  n.k - Schluessel
  n.v - Wert
  n.pred - Vorgaengerknoten (horizontal)
  n.next - Nachfolgerknoten (horizontal)
  n.down - korrespondierender Knoten in tieferer Liste (vertikal)

Jede Liste hat zwei Pseudoknoten, einen am Anfang und einen am Ende,
welche die Schluessel  -INFTY und +INFTY speichern.
Zu Beginn haben wir nur L0 mit den beiden Pseudoknoten.

// Liefere einen Stack Q, welcher die Vorgaengerknoten fuer k (bzw. die Knoten
// mit k) in allen Listen enthaelt (von unten nach oben) 
search(k):
  Q <- new Stack
  n <- -INFTY pseudonode of uppermost list 
  do
    while (n.next.k <= k)
      n <- n.next 
    Q.push(n)
    n <- n.down
  while (n != NULL)
  return Q 

put(k,v)
  Q <- search(k)
  n <- Q.pop()
  if (n.k == k)
    n.v <- v
    return
  insert a new node for (k,v) after n
  while (coinFlip == head)
    if (Q.isEmpty)
      create a new list with -INFTY, a node for k, +INFTY
      create vertical links 
    else
      n <- Q.pop()
      insert a new node for k after n, add a vertical link

remove(k)
  Q <- search(k)
  n <- Q.pop()
  if (n.k != k)
    throw NoSuchElementException
  while (n != NULL and n.k == k)
    remove n from the list
    if (!Q.isEmpty)
      n <- Q.pop()
    else
      n <-NULL
  remove pseudonodes for empty lists, if necessary

get(k)
pred(k)
succ(k)
min
max

Uebung