Time complexity for all collection object of java
Here’s a comprehensive list of time complexities for commonly used operations in Java Collection Framework objects:
In short, O(1) stands for constant time complexity. This means that the operation’s execution time does not depend on the size of the input data. Regardless of how large the dataset is, the operation takes a fixed amount of time.
1. List Implementations
| Operation | ArrayList | LinkedList | CopyOnWriteArrayList |
|---|---|---|---|
| Access (by index) | O(1)O(1)O(1) | O(n)O(n)O(n) | O(1)O(1)O(1) |
| Search (by value) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
| Insertion (at end) | O(1)∗O(1)*O(1)∗ | O(1)O(1)O(1) | O(n)O(n)O(n) |
| Insertion (at index) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
| Deletion (by index) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
| Iteration | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
*For ArrayList, O(1)O(1)O(1) for appending at the end, assuming no resizing.
2. Set Implementations
| Operation | HashSet | LinkedHashSet | TreeSet | CopyOnWriteArraySet |
|---|---|---|---|---|
| Access | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(n)O(n)O(n) |
| Search | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(n)O(n)O(n) |
| Insertion | O(1)∗O(1)*O(1)∗ | O(1)∗O(1)*O(1)∗ | O(logn)O(\log n)O(logn) | O(n)O(n)O(n) |
| Deletion | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(n)O(n)O(n) |
| Iteration | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
*For HashSet and LinkedHashSet O(1)O(1)O(1) assumes a good hash function and no collisions.
3. Queue Implementations
| Operation | PriorityQueue | ArrayDeque | LinkedList |
|---|---|---|---|
| Enqueue (add) | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) | O(1)O(1)O(1) |
| Dequeue (poll) | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) | 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) |
| Search | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
4. Deque Implementations
| Operation | ArrayDeque | LinkedList |
|---|---|---|
| Add First/Last | O(1)O(1)O(1) | O(1)O(1)O(1) |
| Remove First/Last | O(1)O(1)O(1) | O(1)O(1)O(1) |
| Peek First/Last | O(1)O(1)O(1) | O(1)O(1)O(1) |
5. Map Implementations
| Operation | HashMap | LinkedHashMap | TreeMap | ConcurrentHashMap |
|---|---|---|---|---|
| Access (get) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) |
| Search (containsKey) | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) |
| Insertion | O(1)∗O(1)*O(1)∗ | O(1)∗O(1)*O(1)∗ | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) |
| Deletion | O(1)O(1)O(1) | O(1)O(1)O(1) | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) |
| Iteration (keys/values) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) | O(n)O(n)O(n) |
*For HashMap and LinkedHashMap, O(1)O(1)O(1) assumes a good hash function and minimal collisions.
TreeMap
TreeMap is implemented using a Red-Black Tree, which ensures that the elements are always stored in sorted order. This affects the time complexities of various operations:
| Operation | Time Complexity |
|---|---|
| Insertion | O(logn)O(\log n)O(logn) |
| Deletion | O(logn)O(\log n)O(logn) |
| Search (get/containsKey) | O(logn)O(\log n)O(logn) |
| Iteration (keySet/values) | O(n)O(n)O(n) |
Key Points:
- Elements are stored in natural order or according to a custom comparator provided.
- Useful when you need operations like range queries or iteration in sorted order.
HashMap
HashMap is implemented using a combination of an array and a linked list (or a red-black tree for buckets with many collisions, starting from Java 8).
| Operation | Time Complexity |
|---|---|
| Insertion | O(1)∗O(1)*O(1)∗ |
| Deletion | O(1)∗O(1)*O(1)∗ |
| Search (get/containsKey) | O(1)∗O(1)*O(1)∗ |
| Iteration (keySet/values) | O(n)O(n)O(n) |
Key Points:
- Elements are not stored in order; they rely on the hash of the keys.
- The O(1)O(1)O(1) time complexity for insertion, deletion, and search assumes a good hash function and minimal collisions.
- In case of many collisions, performance can degrade to O(n)O(n)O(n), but Java 8+ uses a red-black tree for such scenarios, improving it to O(logn)O(\log n)O(logn).
When to Use?
- TreeMap:
Use when you need the keys to be sorted or when you need range queries (e.g., finding all keys between two values). - HashMap:
Use when you need fast access (on average O(1)O(1)O(1)) and ordering of keys is not important.
Summary Table:
| Feature | TreeMap | HashMap |
|---|---|---|
| Ordering | Sorted | Unordered |
| Insertion | O(logn)O(\log n)O(logn) | O(1)∗O(1)*O(1)∗ |
| Search | O(logn)O(\log n)O(logn) | O(1)∗O(1)*O(1)∗ |
| Deletion | O(logn)O(\log n)O(logn) | O(1)∗O(1)*O(1)∗ |
| Iteration | O(n)O(n)O(n) | O(n)O(n)O(n) |
| Null Keys Allowed | No | Yes |
Notes:
- Resize Overhead: For dynamic data structures like ArrayList and HashMap, resizing incurs additional O(n)O(n)O(n) cost occasionally.
- Collision Handling: In hash-based collections, performance can degrade to O(n)O(n)O(n) in the case of poor hash functions or excessive collisions.
- Thread Safety: Concurrent collections (like ConcurrentHashMap and
Recent Comments