dcsimg
August 20, 2018
Hot Topics:

Java Ordered Collections: Trees and Skip Lists

  • January 9, 2009
  • By Mark Grand
  • Send Email »
  • More Articles »

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.

SortedMap

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

Summary

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



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

By submitting your information, you agree that developer.com may send you developer offers via email, phone and text message, as well as email offers about other products and services that developer believes may be of interest to you. developer will process your information in accordance with the Quinstreet Privacy Policy.

Sitemap

Thanks for your registration, follow us on our social networks to keep up-to-date