‹ Back
Data Structures
Time Complexity (Average)
| Data Structure |
Access |
Search |
Insert |
Delete |
| Dynamic Array |
O(1) |
O(n) |
O(n) |
O(n) |
| Stack |
O(n) |
O(n) |
O(1) |
O(1) |
| Queue |
O(n) |
O(n) |
O(1) |
O(1) |
| Singly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
| Doubly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
| Hash Table |
O(1) |
O(1) |
O(1) |
O(1) |
| Binary Search Tree |
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) |
Time Complexity (Worst)
| Data Structure |
Access |
Search |
Insert |
Delete |
| Dynamic Array |
O(1) |
O(n) |
O(n) |
O(n) |
| Stack |
O(n) |
O(n) |
O(1) |
O(1) |
| Queue |
O(n) |
O(n) |
O(1) |
O(1) |
| Singly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
| Doubly-Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
| Hash Table |
O(1) |
O(n) |
O(n) |
O(n) |
| Binary Search Tree |
O(n) |
O(n) |
O(n) |
O(n) |
| Red-Black Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
Space Complexity
| Data Structure |
Space Complexity |
| Dynamic Array |
O(n) |
| Stack |
O(n) |
| Queue |
O(n) |
| Singly-Linked List |
O(n) |
| Doubly-Linked List |
O(n) |
| Hash Table |
O(n) |
| Binary Search Tree |
O(n) |
| Red-Black Tree |
O(n) |