Java Collections Big O Performance Summary Below are the time complexity details for common functions of major Java Collection classes.
List Type Add Remove Get Contains Next Data Structure ArrayList O(1) O(n) O(1) O(n) O(1) Array LinkedList O(1) O(1) O(n) O(n) O(1) Linked List CopyOnWriteArrayList O(n) O(n) O(1) O(n) O(1) Array
Set Type Add Remove Contains Next Size Data Structure HashSet O(1) O(1) O(1) O(h/n) O(1) Hash Table LinkedHashSet O(1) O(1) O(1) O(1) O(1) Hash Table + Linked List EnumSet O(1) O(1) O(1) O(1) O(1) Bit Vector TreeSet O(log n) O(log n) O(log n) O(log n) O(1) Red-black tree CopyOnWriteArraySet O(n) O(n) O(n) O(1) O(1) Array ConcurrentSkipListSet O(log n) O(log n) O(log n) O(1) O(n) Skip List
Queue Type Offer Peek Poll Remove Size Data Structure PriorityQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap LinkedList O(1) O(1) O(1) O(1) O(1) Array ArrayDeque O(1) O(1) O(1) O(n) O(1) Linked List ConcurrentLinkedQueue O(1) O(1) O(1) O(n) O(n) Linked List ArrayBlockingQueue O(1) O(1) O(1) O(n) O(1) Array PriorityBlockingQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap SynchronousQueue O(1) O(1) O(1) O(n) O(1) None DelayQueue O(log n) O(1) O(log n) O(n) O(1) Priority Heap LinkedBlockingQueue O(1) O(1) O(1) O(n) O(1) Linked List
Map Type Get ContainsKey Next Data Structure HashMap O(1) O(1) O(h / n) Hash Table LinkedHashMap O(1) O(1) O(1) Hash Table + Linked List IdentityHashMap O(1) O(1) O(h / n) Array WeakHashMap O(1) O(1) O(h / n) Hash Table EnumMap O(1) O(1) O(1) Array TreeMap O(log n) O(log n) O(log n) Red-black tree ConcurrentHashMap O(1) O(1) O(h / n) Hash Tables ConcurrentSkipListMap O(log n) O(log n) O(1) Skip List
Note: O(h/n) where h is the table capacity; for non-hash tables, ignore this detail.