What are the Big-O Time Complexities of Different Java Collections Framework Operations?

Big-O Notation for Java Collections Framework Implementations

In anticipation of an upcoming Java crash-course, it is essential to provide a concise summary of the time complexity of various operations on different collection implementations.

List Implementations

Implementation	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

Implementation	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

Implementation	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

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

Additional Resources

For further exploration, consider these valuable resources:

• Collections Overview: Offers a helpful summary table
• Annotated Outline: Contains a comprehensive list of implementations on a single page

The above is the detailed content of What are the Big-O Time Complexities of Different Java Collections Framework Operations?. For more information, please follow other related articles on the PHP Chinese website!