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

shrishar commented Aug 30, 2017

Amazing thank you so much ~!

@bitnahian

This comment has been minimized.

Copy link

bitnahian commented Sep 21, 2017

Thank you for this great chart!

@rafareyes7

This comment has been minimized.

Copy link

rafareyes7 commented Sep 27, 2017

Thanks! source?

@SurendraVidiyala

This comment has been minimized.

Copy link

SurendraVidiyala commented Oct 5, 2017

Thank you

@firstpixel

This comment has been minimized.

Copy link

firstpixel commented Nov 24, 2017

Awesome! Great reference, but its missing Stack.

@pendawleabhay

This comment has been minimized.

Copy link

pendawleabhay 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

ayush--s commented Dec 31, 2017

@vlytsus

This comment has been minimized.

Copy link

vlytsus 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

ArseniyChern commented Feb 3, 2018

HashMap should be log(n) if worst case

@baruchiro

This comment has been minimized.

Copy link

baruchiro commented Mar 27, 2018

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

@pszeliga

This comment has been minimized.

Copy link

pszeliga commented May 16, 2018

I think you switched data structures for LinkedList and ArrayDeque

@matthewmarkose

This comment has been minimized.

Copy link

matthewmarkose commented May 29, 2018

This is beautiful. Good job and thank you.

@abcoep

This comment has been minimized.

Copy link

abcoep 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

slavadolg 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

prajeethrudra commented Aug 1, 2018

Thank You

@Bhagyasree1234

This comment has been minimized.

Copy link

Bhagyasree1234 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

lare96 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

digi9ten 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

dmitry-izmerov 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

enkeebbx commented Mar 11, 2019

Simply amazing. Thank you.

@ZhijianD

This comment has been minimized.

Copy link

ZhijianD commented Apr 5, 2019

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

@chinmay2312

This comment has been minimized.

Copy link

chinmay2312 commented Apr 7, 2019

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

@dongw00

This comment has been minimized.

Copy link

dongw00 commented Apr 14, 2019

Thank you bro

@mindskai27

This comment has been minimized.

Copy link

mindskai27 commented Jun 18, 2019

Very useful! Thanks!

@agrawalankit006

This comment has been minimized.

Copy link

agrawalankit006 commented Jul 11, 2019

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.

@HUAZHEYINy

This comment has been minimized.

Copy link

HUAZHEYINy commented Aug 5, 2019

thanks !!!

@LisaFan18

This comment has been minimized.

Copy link

LisaFan18 commented Sep 14, 2019

Very useful. Thank you!

@VasilSokolov

This comment has been minimized.

Copy link

VasilSokolov commented Nov 1, 2019

Great!!! Thanks!

@MariaForester

This comment has been minimized.

Copy link

MariaForester commented Nov 17, 2019

Thanks a lot! Very helpful!

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.