The following table shows the complexities of data structures:
| Data Structure | Average Cases | Worst Cases | ||||
| Insert | Delete | Search | Insert | Delete | Search | |
| Array/Stack/Queue | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Linked list | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Doubly linked list | O(1) | O(1) | O(n) | O(1) | O(1) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) |
| AVL tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| Red Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
| Binary heap | O(log(n)) | O(log(n)) | O(1): find max/min | O(log(n)) | O(log(n)) | O(1) |
