Collection Implementation Classes

Set implementation classes.

• HashSet : Internally uses a hash table to store the elements. It does not make any guarantee of the ordering of the elements as traversal can give you a different order than the oreder of insertion but provides the best performance in all the implementations of set. So when the ordering of the elements does not matter, it is the best set implementation for use.
• TreeSet: Intyernally uses a red-black tree to store the elements. TreeSet orders its elements on the baisis of a natural sorting order or any sorting order passed to Comparable.
• LinkedHashSet: Internally uses a hash table with a linked list implementation. Maintains the order of the elements on the baisis of the insertion order. Lateral traversal will give you the order as the order of insertion. So if you need to maintain the order of insertion then it saves you from the unexpected ordering of the HashSet.

List implementation classes.

• ArrayList : ArrayList is a dynamic array which store the objects in a sequential manner and in the contiguous memory locations. Internally uses an array to store the elements. ArrayList is the Most commonly used List implementation class. It can grow dynamically and can have duplicate elements. Like Array, ArrayList is also a random access data structure which can access the elements using index in O(1). Insertion and deletion worst time complexity is also like Array – O(n) as elements needs to be shifted.
• LinkedList: Like ArrayList, LinkedList also stores elements sequentially but elements are stored in the nodes that are scattered in the memory and may not be contiguous but are linked through references. LinkedList is not a random access data structure. To find an element, whole LinkedList need to traversed that makes the time complexity as O(n). Insertion and deletion operations are easier to perform than ArrayList.

Map implementation classes.

Map has implementation classes - HashMap, TreeMap and LinkedHashMap. In HashMap oredering of the elements is not preserved, while in LinkedHashMap oredering of the elements is preserved on the basis of the inserson. In TreeMap, key-value pair is maintained in the ascending sorting order of the key. To add an object as a key to the TreeMap that class should implement Comparable interface which in turn forces to implement compareTo() method which in turn contains the sorting order definition.