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

by

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:

More Related Contents:

  1. What is the difference between "collection" ,"Collection" and "Collections"? [duplicate]
  2. Difference between
  3. Properly removing an Integer from a List
  4. What is the best way to combine two lists into a map (Java)?
  5. Hibernate Validation of Collections of Primitives
  6. What is the best way get the symmetric difference between two sets in java?
  7. Performance ConcurrentHashmap vs HashMap
  8. What are Reified Generics? How do they solve Type Erasure problems and why can’t they be added without major changes?
  9. What is the difference between an ordered and a sorted collection?
  10. Java – How to create new Entry (key, value)
  11. Why does Collections.sort use Mergesort but Arrays.sort does not?
  12. How to modify a Collection while iterating using for-each loop without ConcurrentModificationException? [duplicate]
  13. Sort a List of objects by multiple fields [duplicate]
  14. Empty an ArrayList or just create a new one and let the old one be garbage collected? [duplicate]
  15. Removing items from a collection in java while iterating over it
  16. what’s a good persistent collections framework for use in java?
  17. Is there a way to get the value of a HashMap randomly in Java?
  18. Difference between a deprecated and a legacy API?
  19. Any implementation of Ordered Set in Java?
  20. JDK9 randomization on immutable sets and maps
  21. In what situations is the CopyOnWriteArrayList suitable? [duplicate]
  22. What Java 8 Stream.collect equivalents are available in the standard Kotlin library?
  23. Create a List of primitive int?
  24. Java collections covariance problem
  25. Java: Best way to iterate through a Collection (here ArrayList)
  26. How does ConcurrentHashMap work internally?
  27. How Best to Compare Two Collections in Java and Act on Them?
  28. Vector vs Collections.synchronizedList(ArrayList)
  29. What is the best way to get min and max value from a list of Comparables that main contain null values?
  30. Performance and Memory allocation comparison between List and Set

Leave a Comment