Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Runtime Complexity of Java Collections
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
@shrishar

This comment has been minimized.

Copy link

commented Aug 30, 2017

Amazing thank you so much ~!

@bitnahian

This comment has been minimized.

Copy link

commented Sep 21, 2017

Thank you for this great chart!

@rafareyes7

This comment has been minimized.

Copy link

commented Sep 27, 2017

Thanks! source?

@SurendraVidiyala

This comment has been minimized.

Copy link

commented Oct 5, 2017

Thank you

@firstpixel

This comment has been minimized.

Copy link

commented Nov 24, 2017

Awesome! Great reference, but its missing Stack.

@pendawleabhay

This comment has been minimized.

Copy link

commented Nov 29, 2017

So LinkedList under List Interface uses Linked List data structure. But LinkedList under Queue interface uses Array? How??

@ayush--s

This comment has been minimized.

Copy link

commented Dec 31, 2017

@vlytsus

This comment has been minimized.

Copy link

commented Jan 30, 2018

ArrayDequeue spelled wrong. Should be ArrayDeque. And Data Structure for ArrayDeque is array.

@ArseniyChern

This comment has been minimized.

Copy link

commented Feb 3, 2018

HashMap should be log(n) if worst case

@baruchiro

This comment has been minimized.

Copy link

commented Mar 27, 2018

Thanks!
What about constructors?
They are not always as added.

@pszeliga

This comment has been minimized.

Copy link

commented May 16, 2018

I think you switched data structures for LinkedList and ArrayDeque

@matthewmarkose

This comment has been minimized.

Copy link

commented May 29, 2018

This is beautiful. Good job and thank you.

@abcoep

This comment has been minimized.

Copy link

commented Jun 3, 2018

I think you switched data structures for LinkedList and ArrayDeque

@pszeliga I second you

@slavadolg

This comment has been minimized.

Copy link

commented Jun 25, 2018

In Queue section LinkedList isnt an Array and ArrayDequeue based on cycled array

@prajeethrudra

This comment has been minimized.

Copy link

commented Aug 1, 2018

Thank You

@Bhagyasree1234

This comment has been minimized.

Copy link

commented Aug 19, 2018

In case of O(h / n) may i know the 'h' value and what does it stands for.

@lare96

This comment has been minimized.

Copy link

commented Oct 16, 2018

LinkedList remove is only O(1) if you use its iterator. standard remove(Object) is O(n)

@digi9ten

This comment has been minimized.

Copy link

commented Oct 25, 2018

In case of O(h / n) may i know the 'h' value and what does it stands for.

h stands for the current capacity of the hash collection.

@dmitry-izmerov

This comment has been minimized.

Copy link

commented Dec 3, 2018

@psayre23 could you explain or anybody why there is no put/add operation for map in table above?

@enkeebbx

This comment has been minimized.

Copy link

commented Mar 11, 2019

Simply amazing. Thank you.

@ZhijianD

This comment has been minimized.

Copy link

commented Apr 5, 2019

It really helps me to prepare for my CS exam! Thank you!!

@chinmay2312

This comment has been minimized.

Copy link

commented Apr 7, 2019

For Queue, the 2nd column head would be "peek" instead of "peak"

@dongw00

This comment has been minimized.

Copy link

commented Apr 14, 2019

Thank you bro

@mindskai27

This comment has been minimized.

Copy link

commented Jun 18, 2019

Very useful! Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.