creating a doubly linked list between the elements, allowing them to be accessed in the order in which they were inserted into the map. TreeMap, in contrast to HashMap and LinkedHashMap, uses a red–black tree. The keys are used as the values for the nodes in the tree, and the nodes point to the elements in the map. The java.util.Map interface is extended by its subinterface, java.util.SortedMap. This interface defines a map that's sorted by the keys provided. Using, once again, the compareTo() method or a method provided in the constructor to the sorted map, the key-element pairs are sorted by the keys. The first and last keys in the map can be called. Additionally, submaps can be created from minimum and maximum keys. SortedMap is implemented by java.util.TreeMap. The java.util.NavigableMap interface extends java.util.SortedMap in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented by java.util.TreeMap. Extensions to the Java collections framework Java collections framework is extended by the Apache Commons Collections library, which adds collection types such as a bag and bidirectional map, as well as utilities for creating unions and intersections. Google has released its own collections libraries as part of the guava libraries. See also Collection Container Standard Template Library Java concurrency Java ConcurrentMap References Java (programming language) Data structures libraries and frameworks