Quick complexity reference for most common data structures, considering efficient implementations usually available in frameworks class libraries.
Array
Time Complexity:
| Average | Worst | |
|---|---|---|
| Indexing | O(1) | O(1) |
| Search | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Delete | O(n) | O(n) |
Space Complexity: O(n)
Linked List
Time Complexity:
| Average | Worst | |
|---|---|---|
| Indexing | O(n) | O(n) |
| Search | O(n) | O(n) |
| Insert | O(1) | O(1) |
| Delete | O(1) | O(1) |
Space Complexity: O(n)
For both single-linked and doubly-linked lists
Stack
Time Complexity:
| Average | Worst | |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
Space Complexity: O(n)
Queue
Time Complexity:
| Average | Worst | |
|---|---|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
Space Complexity: O(n)
Hash Table
Time Complexity:
| Average | Worst | |
|---|---|---|
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
Space Complexity: O(n)
Heap
Time Complexity:
| Average | Worst | |
|---|---|---|
| Heapify | O(n) | O(n) |
| Find Max | O(1) | O(1) |
| Insert | O(log(n)) | O(log(n)) |
| Delete | O(log(n)) | O(log(n)) |
Space Complexity: O(n)
Binary Search Tree
Time Complexity:
| Average | Worst | |
|---|---|---|
| Indexing | O(log(n)) | O(n) |
| Search | O(log(n)) | O(n) |
| Insert | O(log(n)) | O(n) |
| Delete | O(log(n)) | O(n) |
Space Complexity: O(n)
Self-balancing Binary Search Tree
Time Complexity:
| Average | Worst | |
|---|---|---|
| Indexing | O(log(n)) | O(log(n)) |
| Search | O(log(n)) | O(log(n)) |
| Insert | O(log(n)) | O(log(n)) |
| Delete | O(log(n)) | O(log(n)) |
Space Complexity: O(n)
Ex: AVL Tree, Red-Black Tree
Trie
Time Complexity:
| Average | Worst | |
|---|---|---|
| Search | O(m) | O(m) |
| Insert | O(m) | O(m) |
| Delete | O(m) | O(m) |
Space Complexity: O(m * l)
Where:
mis the length of the search stringlis the length of the character alphabet