Where to get more information on Dictionary ADT and Skip List for Java?

Question

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.

Answer 1

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.