java_datastructure_time_complexity/JavaDataStructureTimeComplexity.java at master · SubhashPavuskar/java_datastructure_time_complexity · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
BelowaretheBigOperformanceofcommonfunctionsofdifferentJavaCollections.


List | Add | Remove | Get | Contains | Next | DataStructure
---------------------|------|--------|------|----------|------|---------------
ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array
LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | LinkedList
CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array


Set | Add | Remove | Contains | Next | Size | DataStructure
----------------------|----------|----------|----------|----------|------|-------------------------
HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | HashTable
LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | HashTable + LinkedList
EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | BitVector
TreeSet | O(logn) | O(logn) | O(logn) | O(logn) | O(1) | Red-blacktree
CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array
ConcurrentSkipListSet | O(logn) | O(logn) | O(logn) | O(1) | O(n) | SkipList


Queue | Offer | Peak | Poll | Remove | Size | DataStructure
------------------------|----------|------|----------|--------|------|---------------
PriorityQueue | O(logn) | O(1) | O(logn) | O(n) | O(1) | PriorityHeap
LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array
ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | LinkedList
ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | LinkedList
ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array
PriorirityBlockingQueue | O(logn) | O(1) | O(logn) | O(n) | O(1) | PriorityHeap
SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None!
DelayQueue | O(logn) | O(1) | O(logn) | O(n) | O(1) | PriorityHeap
LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | LinkedList


Map | Get | ContainsKey | Next | DataStructure
----------------------|----------|-------------|----------|-------------------------
HashMap | O(1) | O(1) | O(h / n) | HashTable
LinkedHashMap | O(1) | O(1) | O(1) | HashTable + LinkedList
IdentityHashMap | O(1) | O(1) | O(h / n) | Array
WeakHashMap | O(1) | O(1) | O(h / n) | HashTable
EnumMap | O(1) | O(1) | O(1) | Array
TreeMap | O(logn) | O(logn) | O(logn) | Red-blacktree
ConcurrentHashMap | O(1) | O(1) | O(h / n) | HashTables
ConcurrentSkipListMap | O(logn) | O(logn) | O(1) | SkipList