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.
  • HashMapHashMap 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.
  • SortedMapSortedMap 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
0 (lazily initialized to 10)

Related Tutorials

No comments:

Post a Comment