December 2018
Intermediate to advanced
500 pages
12h 19m
English
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) ... | |||||