# Time Complexity of Collections

* https://www.baeldung.com/java-collections-complexity
* https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures

| List                 | 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                   | 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                   | Offer    | Peak | 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          |
| ArrayDequeue            | 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          |
| PriorirityBlockingQueue | 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                   | 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                |
