add-memberalign-toparrow-leftarrow-rightbellblockcalendarcamerachatchevron-leftchevron-rightchevron-small-downchevron-upcircle-with-crosscomposecrossfacebookflagfolderglobegoogleimagesinstagramkeylocation-pinmedalmoremuplabelShape 3 + Rectangle 1pagepersonpluspollsImported LayersImported LayersImported LayersshieldstartwitterwinbackClosewinbackCompletewinbackDiscountyahoo

50 Algos in 50 Weeks: Implementing Skip list

skip list is a data structure for storing a sorted list of items using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n).

Skip list.svg

Each link of the sparser lists skips over many items of the full list in one step, hence the structure's name. These forward links may be added in arandomized way with a geometricnegative binomial distribution.[3] Insert, search and delete operations are performed in logarithmic expected time. The links may also be added in a non-probabilistic way so as to guarantee amortized (rather than merely expected) logarithmic cost.


Join or login to comment.

  • A former member
    A former member

    Very entertaining--I love the respectful but passionate discussion about implementation details. Members were super engaged--can't wait for the next meetup!

    July 6, 2012

  • A former member
    A former member

    Awesome meetup--excited to see what's in store for next week! Bummed about leaving early though...

    July 6, 2012

50 went

Our Sponsors

  • Pivotal Labs

    Pivotal Labs

  • Vendavo

    Vendavo is the leader in front-line profit optimization

  • Wolfram Research

    Mathematica is the world's ultimate application for computations.

  • Yodle

    Local online advertising for small businesses.

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy