Big-O summary for Java Collections Framework implementations

Question

I may be teaching a  Java crash-course  soon   While it is probably safe to assume that the audience members will know Big-O notation  it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is   I could take time to generate a summary matrix myself  but if it s already out there in the public domain somewhere  I d sure like to reuse it  with proper credit  of course    Anyone have any pointers

User · Answer

The guy above gave comparison for HashMap / HashSet vs. TreeMap / TreeSet.

I will talk about ArrayList vs. LinkedList:

ArrayList:

O(1) get()
amortized O(1) add()
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(n) to shift all the following elements

LinkedList:

O(n) get()
O(1) add()
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1)

User · Answer

The Javadocs from Sun for each collection class will generally tell you exactly what you want  HashMap  for example      This implementation provides constant-time performance for the basic operations  get and put   assuming the hash function disperses the elements properly among the buckets  Iteration over collection views requires time proportional to the  capacity  of the HashMap instance  the number of buckets  plus its size  the number of key-value mappings      TreeMap      This implementation provides guaranteed log n  time cost for the containsKey  get  put and remove  operations    TreeSet      This implementation provides guaranteed log n  time cost for the basic operations  add  remove and contains       emphasis mine

User · Answer

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 capacity  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 capacity  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

User · Answer

This website is pretty good but not specific to Java  http   bigocheatsheet com

[java] Big-O summary for Java Collections Framework implementations?

Examples related to java

Examples related to collections

Examples related to big-o