April 03, 2020

#Collections: Part 8(Time Complexity And Performance of Java Collections)

ArrayList
The ArrayList in Java is backed by an array.
  • add() takes O(1) time
  • add(index, element) in average runs in O(n) time
  • get() 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() also runs in linear time. It iterates through the internal array and checking each element one by one. So the time complexity for this operation always requires O(n) time
  • contains() implementation is based on indexOf(). So it will also run in O(n) time
CopyOnWriteArrayList 
This implementation of the List interface is very useful when working with multi-threaded applications.
  • add() depends on the position we add value, so the complexity is O(n)
  • get() is O(1) constant time operation
  • remove() takes O(n) time
  • contains() likewise, the complexity is O(n)
LinkedList
LinkedList is a linear data structure which consists of nodes holding a data field and a reference to another node
  • add() supports O(1) constant-time insertion at any position
  • get() searching for an element takes O(n) time
  • remove() removing an element also takes O(1) operation, as we provide the position of the element
  • contains() also has O(n) time complexity.
LIST
Add at last index
Add at specific index
Remove by value/ index
Get
Contains
Data  Structure
ArrayList
 O(1)
O(n)
O(n)
O(1)
O(n)
Array
LinkedList
 O(1)
O(n)
O(n)
O(n)
O(n)
Linked List
CopyonWriteArrayList
 O(n)

O(n)
O(1)
O(n)
Array

SET
Add/Remove
Contains
Next
Data Structure
HashSet
O(1)
O(1)
O(h/n)
Hash Table
LinkedHashSet
O(1)
O(1)
O(1)
Hash Table + Linked List
EnumSet
O(1)
O(1)
O(1)
Bit Vector
TreeSet
O(log n)
O(log n)
O(log n)
Red-black tree
CopyonWriteArraySet
O(n)
O(n)
O(1)
Array
ConcurrentSkipList
O(log n)
O(log n)
O(1)
Skip List

QUEUE
Offer
Peak
Poll
Size
Data Structure
PriorityQueue
O(log n )
O(1)
O(log n)
O(1)
Priority Heap
ArrayDequeue
 O(1)
O(1)
O(1)
O(1)
Linked List
ConcurrentLinkedQueue
 O(1)
O(1)
O(1)
O(n)
Linked List
ArrayBlockingQueue
 O(1)
O(1)
O(1)
O(1)
Array
PriorirityBlockingQueue
O(log n)
O(1)
O(log n)
O(1)
Priority Heap
SynchronousQueue
O(1)
O(1)
O(1)
O(1)
None!
DelayQueue
O(log n)
O(1)
O(log n)
O(1)
Priority Heap
LinkedBlockingQueue
O(1)
O(1)
O(1)
O(1)
Linked List

MAP
Get
Contains
Next
Data Structure
HashMap
O(1)
O(1)
O(h / n)
Hash Table
LinkedHashMap
O(1)
O(1)
O(1)
Hash Table + Linked List
IdentityHashMap
O(1)
O(1)
O(h / n)
Array
WeakHashMap
O(1)
O(1)
O(h / n)
Hash Table
EnumMap
O(1)
O(1)
O(1)
Array
TreeMap
O(log n)
O(log n)
O(log n)
Red-black tree
ConcurrentHashMap
O(1)
O(1)
O(h / n)
Hash Tables
ConcurrentSkipListMap
O(log n)
O(log n)
O(1)
Skip List


-K Himaanshu Shuklaa..

No comments:

Post a Comment