Data Structures
    Overview
    Number
    String
    Array
    Linked List
    Stack
    Hash
    Tree
    Trie
    Advanced Data Structure
    Probabilistic Data Structures
    Big O

Big-O Complexity

Updated: 2021-12-15

h is the hash table capacity

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
HashSet               O(1)     O(1)     O(h/n)
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
HashMap               O(1)     O(1)        O(h/n)
LinkedHashMap         O(1)     O(1)        O(1)
IdentityHashMap       O(1)     O(1)        O(h/n)
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)
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)