14

For a homework assignment, I need to understand how a skip list works.

I've been programming for a little over 2 years now (I know that's not that long in reality), and I have never even heard of a skip list.

I've looked over all of the guides that I can find, and I still only barely understand how they work. I even searched Code Review for an example implementation, and found only one review; and it's not even a complete implementation. I looked over the sample implementation supplied by the course, and it's absolutely atrocious. Between the lack of proper methods, and single-letter variable names, I have no clue how it works.

How does a skip list work? Is knowledge of a skip list required to understand more advanced data structures?

  • 1
  • 1
    Education advice is explicitly off-topic. Given this is about data structures and not education, I edited your question to remove those portions. I also recommend reading the Wikipedia link I edited in and update your question with more specific details about what you still do not understand. – user22815 Jun 18 '15 at 23:41
  • @Snowman Thanks. I only added that to prevent comments like "ask your teacher". I'll keep that in mind for next time. And you added an edit that changes the question. At the end, I'm not asking people to explain how they work since I'm assuming that's offtopic (although I wouldn't be against a good explanation). I just want to know how important they are to learn. – Carcigenicate Jun 18 '15 at 23:46
  • 1
    @Carcigenicate explaining how they work is actually more on topic than asking if you will see them in the real world. We can only guess at what you will be doing and the various realms. Asking if we see them in the real world is polling us for "yep, I see them and use them" or "nope, never heard of it" - which don't make for good or useful answers for other people to read. – user40980 Jun 18 '15 at 23:57
29

In days of old, in data structures class we learned how AVL trees worked. I would have had that in one of my classes, but the instructor said "you'll never actually use this" and instead had us learn 2-3 trees and b* trees instead. Those were days when memory was tight and processes were singally threaded. You didn't use a deque when a singly linked list would work just as well.

The skip list is much more common today with more available memory and concurrency being an issue (you don't need to lock much at all when acting as a writer in a skip list - compared to everything with an AVL tree).

Frankly, it's my favorite data structure now in that its something I can easily reason about how it works underneath and where it will be advantageous or disadvantageous to use.

You aren't going to need to write one from scratch (unless you get it as an interview question - but then you're just as likely to get implement an AVL tree).

You are going to need to understand why you want to select a ConcurrentSkipListMap in Java rather than a HashMap or TreeMap or any of the other map implementations.


To understand how it works, you need to understand how a binary tree works. Wait, let me amend that. You need to understand how a balanced binary tree works. Without balancing a binary tree, you don't get any real advantage with its lookup.

Lets say we've got this tree:

A binary tree

And we insert an '8' into it. Now we've got:

An unbalanced binary tree

And that's not balanced. So, we go and do the magic of balancing it via some implementation...

balanced tree

And you've got a balanced tree again. But that was a lot of magic I waved my hand over.

Lets take a skip list.

ideal skip list

This one happens to be an idealized one. Few are, but it shows the balanced binary tree nature that the skiplist ideal approximates.

Now, we want to insert a 6 into there. This is inserting it much like a linked list. However, we start at the top and go down. The top points to 5. Is 6 > 5? Yes. Ok, the top points off to the end now, so we go down the stack (we're on the 5). The next is 7. Is 6 > 7? Nope. So we go down a level and we're at the base level so we insert 6 to the right of the 5.

We flip a coin - heads we build, tails we stay. Tails. Nothing more needs to be done.

skip list after an insert

Lets insert that 8 now. 8 > 5? yep. 8 > 7? Yep. And now we are at the bottom level again after following arrows and the stack around and we test 8 > 11? Nope. So we insert the 8 to the right of the 7.

We flip a coin - heads we build, tails we stay. Tails. Nothing more needs to be done.

skip list after another insert

In the balanced tree, we'd be getting all worked up about the tree not being balanced now. But this isn't a tree - its a skip list. We approximate a balanced tree.

Now lets insert a 10. I'll avoid all the comparisons.

We flip a coin - heads we build, tails we stay. Heads! And flip it again, Heads again! Flip it again, ok, there's a tails. Two levels above the base linked list.

skip list after yet another insert

The advantage here is that now if we're going to insert a 12, we can skip from 5 to 10 without doing all those other comparisons. We can skip over them with the skip list. And we don't have to worry about the balanced tree - the probabilistic nature of the stacking does that for us.

Why is this so useful? Because when inserting the 10 I can do that by locking the write on the 5 and 7 and 8 pointers rather than the entire structure. And while I am doing that, the readers can still be going through the skip list without having an inconsistent state. For concurrent usage, its faster not having to lock. For iterating over the bottom layer, its faster than a tree (the joys of the BFS and DFS algorithms for tree navigation - you don't have to worry about them).

Will you encounter it? You'll probably see it in use in places. And then you'll know why the author chose that implementation rather than a TreeMap or HashMap for the structure.

Much of this has been borrowed from my blog post: The Skip List

  • Thank you. It's not even the general implementation that I don't understand; I get their resemblance to BSTs. I tried thinking out how I'd implement it, and the thought of managing all the pointers/references constantly confused me. Maybe I let myself get too frustrated. Thanks. I'll try picking it up tomorrow using your answer as a starting point. – Carcigenicate Jun 19 '15 at 0:04
  • 2
    @Carcigenicate you may also find the original paper introducing them useful - Skip Lists: A Probabilistic Alternative to Balanced Trees. It's a rather understandable paper compared to most academic papers that can go way over peoples heads. Table 2 is why you'll see them in use. That time factor for insertion or deletion is added complexity of other solutions. – user40980 Jun 19 '15 at 0:07
  • 2
    A linked list is "just a degenerate very unbalanced tree". A skip list is kind of partially adding back some sort of tree structure on top of a list. Personally, I am a big fan of persistent data structures, and trees seem to be easier to reason about in that particular context. I don't think it's a coincidence that Clojure, Scala, et al. seem to be converging on some kind of Bagwell-style Hash tries as their basic data structure. (Phil Bagwell was even involved in the redesign of Scala's collections framework for Scala 2.8.) Skip lists are still nice, though. – Jörg W Mittag Jun 19 '15 at 10:33
  • That's the best explanation of how a skip list works that I have ever read. – gaborous Nov 10 '15 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.