Java Ordered Collections: Trees and Skip Lists
Figure 6 shows, in red, the links in the skip list that were traversed in the search for 5.
Figure 6: Skip List Search for 5
When a node is added to a skip list, a random number generator is used to determine what levels of linked list the node will be included in. There is a ½ chance that a new node will be included in the level 2 linked list. There is a ¼ chance that the new node will be included in the level 3 linked list. For each higher level of linked list, the chance of a new node being included in the linked list is ½ of the chance of its being included in the next lower level linked list.
For a more detailed explanation of skip lists, see A Skip List Cookbook by William Pugh.
The SortedMap interface is similar to the SortedSet interface in that it also involves a set of objects that are sorted by their value. Like SortedSet, Java 1.6 includes two implementations of the SortedMap interface. These are TreeMap and ConcurrentSkipListMap. The preceding discussion of TreeSet and ConcurrentSkipListSet also applies to TreeMap and ConcurrentSkipListMap
This article has explained when it is best to use a TreeSet or ConcurrentSkipListSet to manage an ordered set of objects within the SortedSet interface. It has also explained the data structures that these classes use to organize their contents.
About the Author
|Mark Grand is a consultant and book author with over 30 years of experience who specializes in Distributed Systems, Object Oriented Design and Java. He was the architect of the first commercial business-to-business e-commerce product to use the Internet.
Mark Grand is most widely known for his best-selling design pattern books. Mark has taught for U.C. Berkeley, Sun, and other organizations.
Mark is based in the Atlanta area. He has been involved with object-oriented programming and design since 1982.
Page 4 of 4