

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

I'm trying to go deep into Dictionary ADT and Skip List for Java. My textbook doesn't cover a lot about this and whatever it has covered is very complicated. Which is the best online site to get more information on Dictionary ADT and Skip List for Java. I'm looking for the one which talks visually and gives a lot of examples.

share|improve this question
up vote 3 down vote accepted

Since it sounds like you're in an algorithms class, I would separate the implementation of a dictionary and a skip list from what is provided by the Java API. At this point, it's more important that you understand the concept of what these abstract data types are, because they can be implemented in any language (C#, PHP, Scheme, Brainfuck, etc.)

Your instructor will probably want you to: first, define the interface or contract for a dictionary (or a skip list), and then figure out its implementation. If you're programming in Java, use JUnit to verify the correctness of your algorithms. If you're programming in some other language, look for any xUnit API.

Look in NIST's Dictionary of Algorithms and Data Structures as a secondary resource to your textbook to understand what these things mean. Probably the best algorithm book in Java is Sedgewick's, and its main distinctive is its pedagogical use of applets. Since the sample code is not written in idiomatic Java, I wouldn't look there for industrial-strength implementations of the algorithms. After all, you're supposed to do the work yourself, not use someone else's collections API.

Oh, btw, Java 6 has two implementations of skip lists: ConcurrentSkipListSet and ConcurrentSkipListMap. And the interface of a dictionary data structure in Java is Map.

share|improve this answer

You can download the PDF of William Pugh's original paper describing skip lists and the theory behind it here.

Also, this is a good applet to visualize the operations of a skip list. It helped me alot when skip lists came up in my data structures class.

Also, the Wikipedia entry has a few good links at the bottom for other implementations and the Java source code.

share|improve this answer

Your Answer


