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.

Answered by: Wilson420 | Posted: 22-02-2022

Answer 2

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.

Answered by: Aida119 | Posted: 22-02-2022

Similar questions

Convert python dictionary into Java hashmap where value types are a mixture of data structures and lambda functions

I am trying to convert the python code provided by our instructor into the equivalent Java code. This portion of code is supposed to read from a txt file, parse the data with regex, and store them as an array of words. A restriction for this exercise is that the "data_storage_obj" is used to imitate JavaScript Object, and we have to keep them in that key-value format. The instruction indicates that a data structure...

---

java - Examples for creating stub data structures with dynamic JVM Languages?

Over the years, I think I have seen and tried every conceivable way of generating stub data structures (fake data) for complex object graphs. It always gets hairy in java. * * * * A---B----C----D----E (Pardon cheap UML) The key issue is that there are certain relationships between the values, so a certain instance of C may imply given values for E. Any attempt...

---

java - Data structures in JDK, under what scenario which one to use?

Closed. This question does not meet Stack Overflow guid...

---

data structures - Efficient persistent storage for simple id to table of values map for java

I need to store some data that follows the simple pattern of mapping an "id" to a full table (with multiple rows) of several columns (i.e. some integer values [u, v, w]). The size of one of these tables would be a couple of KB. Basically what I need is to store a persistent cache of some intermediary results. This could quite easily be implemented as simple sql, but there's a couple of problems, namely I need to co...

---

sql - Querying Java Data Structures

Is there any way to perform SQL Like Queries or Filtering on Java Data Structures? I want to filter objects in an ArrayList and a HashMap by fields of the objects contained within.

---

Fastest way to compare two data structures in java

I would like to know what is the fastest way in java 1.5 to compare two data structures. My data structure represents a tree that can be pretty big. I can traverse the whole data structure and compare the 2 node by node (which I guess will be slow). Or I can compute a hash of the data structure to do it faster, right ? What is the best (efficient and not too long) way to compute this hash ? I would...

---

java - JAXB: How should I marshal complex nested data structures?

I have several complex data structures like Map< A, Set< B > > Set< Map< A, B > > Set< Map< A, Set< B > > > Map< A, Map< B, Set< C > > > and so on (more complex data structures) Note: In my case it doesn't really matter if I use Set or List. Now I know that JAXB let me define XmlAdapter's, that's ...

---

java - Regex for tree structures?

Are there regular expression equivalents for searching and modifying tree structures? Concise mini-languages (like perl regex) are what I am looking for. Here is an example that might clarify what I am looking for. <root> <node name="1"> subtrees .... </node> <node name="2"> <node name="2.1"> data </node> other subtrees... </node&gt...

---

java - array of structures, or structure of arrays?

Hmmm. I have a table which is an array of structures I need to store in Java. The naive don't-worry-about-memory approach says do this: public class Record { final private int field1; final private int field2; final private long field3; /* constructor & accessors here */ } List<Record> records = new ArrayList<Record>(); If I end up using a large number (> 106

---

java - How do I print the class structures in a jar file using the javap tool?

I want to list the methods of the class files in the jar using the javap tool. How do I do it so that it lists the methods and members of all the class files in the jar. Right now I am able to do it for just one class at a time. I am expecting something like if I say javap java.lang.* it should enlist the methods and members of all the classes in java.lang package. If javap is not ...

---

Java Data Structures Reference

Can anyone give me references of a web site containing a summary of the main Java data structures, and their respective complexity in time (for some given operations like add, find, remove), e.g. Hashtables are O(1) for finding, while LinkedLists are O(n). Some details like memory usage would be nice too. This would be really helpful for thinking in data structures for algorithms.

---

Still can't find your answer? Check out these amazing Java communities for help...

Java Reddit Community | Java Help Reddit Community | Dev.to Java Community | Java Discord | Java Programmers (Facebook) | Java developers (Facebook)