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