Below are the Big O performance of common functions of different Java Collections. | |
List | Add | Remove | Get | Contains | Next | Data Structure | |
---------------------|------|--------|------|----------|------|--------------- | |
ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array | |
LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List | |
CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array | |
Set | Add | Remove | Contains | Next | Size | Data Structure | |
----------------------|----------|----------|----------|----------|------|------------------------- | |
HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table | |
LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List | |
EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector | |
TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree | |
CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array | |
ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List | |
Queue | Offer | Peak | Poll | Remove | Size | Data Structure | |
------------------------|----------|------|----------|--------|------|--------------- | |
PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | |
LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array | |
ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List | |
ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List | |
ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array | |
PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | |
SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! | |
DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | |
LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List | |
Map | Get | ContainsKey | 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 |
This comment has been minimized.
This comment has been minimized.
Thank you for this great chart! |
This comment has been minimized.
This comment has been minimized.
Thanks! source? |
This comment has been minimized.
This comment has been minimized.
Thank you |
This comment has been minimized.
This comment has been minimized.
Awesome! Great reference, but its missing Stack. |
This comment has been minimized.
This comment has been minimized.
So LinkedList under List Interface uses Linked List data structure. But LinkedList under Queue interface uses Array? How?? |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
ArrayDequeue spelled wrong. Should be ArrayDeque. And Data Structure for ArrayDeque is array. |
This comment has been minimized.
This comment has been minimized.
HashMap should be log(n) if worst case |
This comment has been minimized.
This comment has been minimized.
Thanks! |
This comment has been minimized.
This comment has been minimized.
I think you switched data structures for LinkedList and ArrayDeque |
This comment has been minimized.
This comment has been minimized.
This is beautiful. Good job and thank you. |
This comment has been minimized.
This comment has been minimized.
@pszeliga I second you |
This comment has been minimized.
This comment has been minimized.
In Queue section LinkedList isnt an Array and ArrayDequeue based on cycled array |
This comment has been minimized.
This comment has been minimized.
Thank You |
This comment has been minimized.
This comment has been minimized.
In case of O(h / n) may i know the 'h' value and what does it stands for. |
This comment has been minimized.
This comment has been minimized.
LinkedList remove is only O(1) if you use its iterator. standard |
This comment has been minimized.
This comment has been minimized.
h stands for the current capacity of the hash collection. |
This comment has been minimized.
This comment has been minimized.
@psayre23 could you explain or anybody why there is no put/add operation for map in table above? |
This comment has been minimized.
This comment has been minimized.
Simply amazing. Thank you. |
This comment has been minimized.
This comment has been minimized.
It really helps me to prepare for my CS exam! Thank you!! |
This comment has been minimized.
This comment has been minimized.
For Queue, the 2nd column head would be "peek" instead of "peak" |
This comment has been minimized.
This comment has been minimized.
Thank you bro |
This comment has been minimized.
This comment has been minimized.
Very useful! Thanks! |
This comment has been minimized.
This comment has been minimized.
Thankyou! Only a small mistake that I think is LinkedList remove is O(N) not O(1) because it first needs to find the node before deleting it. |
This comment has been minimized.
This comment has been minimized.
thanks !!! |
This comment has been minimized.
This comment has been minimized.
Very useful. Thank you! |
This comment has been minimized.
This comment has been minimized.
Great!!! Thanks! |
This comment has been minimized.
This comment has been minimized.
Thanks a lot! Very helpful! |
This comment has been minimized.
This comment has been minimized.
This is great! Thanks |
This comment has been minimized.
This comment has been minimized.
Very helpful indeed. |
This comment has been minimized.
This comment has been minimized.
Thank you for this! |
This comment has been minimized.
This comment has been minimized.
Wow! Thank you! That's very helpful! |
This comment has been minimized.
This comment has been minimized.
How O(1) for adding in arraylist? |
This comment has been minimized.
This comment has been minimized.
Thanks, Great Resource! I have to build my Programs in a way that saves time! |
This comment has been minimized.
This comment has been minimized.
Correct |
This comment has been minimized.
This comment has been minimized.
To the point. Thanks man! |
This comment has been minimized.
This comment has been minimized.
just curious how about the complexity of ArrayList.addAll(Collection)? is it Constant time? |
This comment has been minimized.
This comment has been minimized.
@Barry36 nope, it's O(M+N) where M = array size (the FYI, the source code of
|
This comment has been minimized.
Amazing thank you so much ~!