Skip to content

Instantly share code, notes, and snippets.

@FedericoPonzi

FedericoPonzi/big-o-java-collections.md

Last active December 30, 2023 18:05
Show Gist options
  • Star 87 You must be signed in to star a gist
  • Fork 34 You must be signed in to fork a gist
  • Save FedericoPonzi/8d5094dbae33cbb94536a73f62d1c1a0 to your computer and use it in GitHub Desktop.
Save FedericoPonzi/8d5094dbae33cbb94536a73f62d1c1a0 to your computer and use it in GitHub Desktop.
Download ZIP
Big O notation for java's collections
Raw
big-o-java-collections.md

The book Java Generics and Collections has this information (pages: 188, 211, 222, 240).

List implementations:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Set implementations:

                    add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Map implementations:

                    get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Queue implementations:

                    offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

The bottom of the javadoc for the java.util package contains some good links: Collections Overview has a nice summary table. Annotated Outline lists all of the implementations on one page.

Copy link

ghost commented Jul 11, 2019

Thanks!

@Xtizainy
Copy link

I have a question regarding ArrayList's add() method:
why it's complexity is O(1) while in the worst case you have to adjust the whole array meaning O(n) complexity?

@FedericoPonzi
Copy link
Author

I have a question regarding ArrayList's add() method:
why it's complexity is O(1) while in the worst case you have to adjust the whole array meaning O(n) complexity?

Good catch! The answer can be found here.
TLDR: it's the amortized time complexity.

@Xtizainy
Copy link

Then it is probably worth to note that here we see amortized complexities

@nkarthikpsg
Copy link

Hi, can you add the complexities for put in Maps section ?

@Joseph919
Copy link

May I ask what's the time complexity of TreeMap.keySet() ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment