Java Collections

Implementation of List Interface

• ArrayList : Time complexity
  • add() – O(1) time when add new element in ArrayList; however, worst-case, when increase size internaly and a new array has to be created and all the elements copied to it, it's O(n)
  • add(index, element) –  O(n) time, on average runs, while add element at given index
  • get() – It is always a constant time O(1) operation
  • remove() – runs in linear O(n) time. We have to iterate the entire array to find the element qualifying for removal.
  • indexOf() – its checks each element one by one, So runs in linear time. It iterates through the internal array and  so the time complexity for this operation always requires O(n) time.
  • contains() – implementation is based on indexOf(), so it'll also run in O(n) time.
• LinkedList : Time complexity
  • Time complexity for add() – add an element to the end of the Linkedlist. It only updates a tail, and hence, it's O(1) constant-time complexity.
  • Time complexity add(index, element) – on average runs in O(n) time
  • Time complexity get() – search an element takes O(n) time.
  • Time complexity remove(element) – to remove an element from linkedlist, we first need to find it. This operation is O(n).
  • Time complexity remove(index) – to remove an element by index from linkedlist, we first need to travers the linklist from the beginning; hence, the overall complexity is O(n).
  • Time complexity contains() – also has O(n) time complexity
• AbstractList
• AbstractSequentialList
• AttributeList
• CopyOnWriteArrayList : Time complexity is O(n) for add(), remove(), contains() and O(1) constant time for get() operation
• RoleList
• RoleUnresolvedList
• Stack
• Vector

Implementation of Set Interface

• HashSet
• LinkedHashSet
• SortedSet : It is a sub-interface of set interface.
• TreeSet : TheeSet is an implementation class of SortedSet. TreeSet has O(log(n)) time complexity for the add(), remove() and contains() operations because of the TreeMap implementation internally.
• EnumSet
• CopyOnWriteArraySet : CopyOnWriteArraySet is a thread-safe variant of HashSet, its uses a CopyOnWriteArrayList internally for all of its operations. The add(), remove() and contains() methods have O(n) average time complexity.
• ConcurrentSkipListSet : ConcurrentSkipListSet have O(log(n)) time complexity for add(), remove() and contains(), as it's based in skip list data structure.

Time complexity :  For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time. These are uses HashMap internally.

Implementation of Map Interface

• HashMap
• LinkedHashMap
• SortedSet : It is a sub-interface of Map
• TreeMap : This is an implementation class of SortedMap interface.The time complexity of TreeMap is O(log(n)) For put(), get(), remove(), and containsKey() operations .
• Hashtable
• ConcurrentHashMap
• ConcurrentSkipListMap : The time complexity of  ConcurrentSkipListMap is O(log(n)) For put(), get(), remove(), and containsKey() operations.
• EnumMap
• IdentityHashMap
• WeakHashMap
• AbstractMap
• Attributes
• AuthProvider
• PrinterStateReasons
• Properties
• Provider
• RenderingHints
• SimpleBindings
• TabularDataSupport
• UIDefaults

Time Complexity of HashMap, LinkedHashMap, IdentityHashMap, WeakHashMap, EnumMap and ConcurrentHashMap is O(1) For  put(), get(), remove(), and containsKey() operations.

• HashMap: HashMap is a  part of java.util package in Java's collection. HashMap is used to store Key & Value pairs, it is denoted as HashMap<K, V>. Its does not guarantees to the order of the map elements i.e. unordered collection. It contains only unique elements i.e doesn’t allow duplicate keys. It is similar to the Hashtable class except that it is unsynchronized. it can have one null key but can have multiple null values. Click here to read in details.
• LinkedHashMap: It implements the Map interface and extends HashMap class. LinkedHashMap is just like HashMap with an additional feature of maintaining an insertion order of elements inserted into LinkedHashMap.It contains only unique elements. Click here to read in details.
• SortedMap: SortedMap is an interface in collection framework. Its extends Map interface.The main characteristic of a SortedMap is that, it orders the keys by their natural ordering, or by a specified comparator. Click here to read in details.
• TreeMap: TreeMap is the implementation of SortedMap interface. it orders the keys by their natural ordering, or by a specified comparator. Click here to read in details.

Q- What is the difference between collection and collections in java?

Collection is an interface,it is the root interface of collection hierarchy.

Collections is class present in java.util.package to define several method for collection object. Collections class has static methods that method returns the collection.

Q- What is the default size & load factor of Collection: ArrayList, Vector, HashSet, Hashtable, and HashMap.

Collection	Java 8		Before Java 8
	Initial capacity	Load factor	Initial capacity	Load factor
ArrayList	0 (lazily initialized to 10)		10
Vector	10		10
HashSet	16	0.75	16	0.75
HashMap	16	0.75	16	0.75
Hashtable	16	0.75	11	0.75

Related Tutorials

• Java Collections Interview
• List Interface In Java
• ArrayList
• LinkedList
• Custom Own ArrayList Implementation
• Custom LinkedList implementation in java
• Set Interface In Java
• Map Interface In Java
• HashMap
• TreeMap
• HashMap Vs ConcurrentHashMap
• HashMap Vs HashTable In Java
• HashMap Vs HashSet In Java
• HashMap Vs TreeMap In Java
• HashMap vs LinkedHashMap In Java
• TreeSet Vs TreeMap In Java
• SortedSet Vs TreeSet In Java
• SortedMap Vs TreeMap In Java
• Array Vs ArrayList In Java
• ArrayList Vs LinkedList In Java
• How HashSet Works Internally
• How TreeMap Works Internally
• How HashMap Works Internally
• How ConcurrentHashMap Works Internally
• How To Detect Loop In A LinkedList In Java
• Detect And Remove Loop In A LinkedList