The algorithm scalability choices also often manifest themselves in the choice of data structures. This table gives the time and space complexity of common data structures and their operations:
|
Data structure |
Time complexity |
Space complexity |
|||||
|
Average |
Worst |
Worst case |
|||||
|
Search |
Insert |
Delete |
Search |
Insert |
Delete |
||
|
Array |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
|
Linked list |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(1) |
O(n) |
|
Skip list |
O(logn) |
O(logn) |
O(logn) |
O(n) |
O(n) |
O(n) |
O(nlogn) |
|
Hash table |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
|
Binary search tree |
O(logn) |
O(logn) |
O(logn) |
O(n) |
O(n) |
O(n) |
O(n) |
|
Red black tree |
O(logn) |
O(logn) ... | |||||
