The title of the article should be: What are the Big-O Time Complexities of Java Collection Implementations?

Java Collections Framework Implementations: A Big-O Summary

When teaching a "Java crash-course," it's crucial to be aware of the Big-O time complexity associated with various collection implementations. While audience members may be familiar with Big-O notation, it's unlikely they'll know the specific complexities for different operations on specific collections.

Fortunately, the book "Java Generics and Collections" provides valuable insights into these complexities. This article summarizes the information from the book, providing a detailed table for each type of collection: lists, sets, maps, and queues.

List Implementations:

Operation	ArrayList	LinkedList	CopyOnWriteArrayList
get	O(1)	O(n)	O(1)
add	O(1)	O(1)	O(n)
contains	O(n)	O(n)	O(n)
next	O(1)	O(1)	O(1)
remove(0)	O(n)	O(1)	O(n)
iterator.remove	O(n)	O(1)	O(n)

Set Implementations:

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

Map Implementations:

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

Queue Implementations:

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

The above is the detailed content of The title of the article should be: What are the Big-O Time Complexities of Java Collection Implementations?. For more information, please follow other related articles on the PHP Chinese website!