| ADT | Processing | Applications | Functions | Performance | |
| Average-Case | Worst-Case | ||||
| array | unordered key | simple/static | insert_at_p | O(n) | O(n) |
| in contiguous storage | find | O(n) | O(n) | ||
| findmin | O(n) | O(n) | |||
| findnext | O(n) | O(n) | |||
| delete_at_p | O(n) | O(n) | |||
| list | unordered key | complex/dynamic | insert_at_p | O(1) | O(1) |
| in non-contiguous storage | find | O(n) | O(n) | ||
| findmin | O(n) | O(n) | |||
| findnext | O(n) | O(n) | |||
| delete_at_p | O(1) | O(1) | |||
| stack | LIFO time-ordered key | compilers | push | O(1) | O(1) |
| automata | find | O(n) | O(n) | ||
| balancing | findmin | O(n) | O(n) | ||
| infix-to-postfix | findnext | O(n) | O(n) | ||
| calculator | pop | O(1) | O(1) | ||
| queue | FIFO time-ordered key | operating systems | enqueue | O(1) | O(1) |
| breadth-first | find | O(n) | O(n) | ||
| findmin | O(n) | O(n) | |||
| findnext | O(n) | O(n) | |||
| dequeue | O(1) | O(1) | |||
| binary search tree | partially-ordered | lookup | insert | O(log n) | O(n) |
| hierarchical key | dictionary | find | O(log n) | O(n) | |
| findmin | O(log n) | O(n) | |||
| findnext | O(log n) | O(n) | |||
| delete | O(log n) | O(n) | |||
| B+tree | ordered | databases | insert | O(log n) | O(log n) |
| hierarchical key | find | O(log n) | O(log n) | ||
| findmin | O(log n) | O(log n) | |||
| findnext | O(1) | O(1) | |||
| delete | O(log n) | O(log n) | |||
| priority queue | partially-ordered | operating systems | insert | O(log n) | O(log n) |
| (heap) | hierarchical key | simulation | find | O(n) | O(n) |
| sorting | deletemin | O(log n) | O(log n) | ||
| findnext | O(n) | O(n) | |||
| delete_at_i | O(log n) | O(log n) | |||
| hash table | unordered/direct key | databases | insert | O(1) | O(n) |
| compilers | find | O(1) | O(n) | ||
| dictionary | findmin | O(n) | O(n) | ||
| findnext | O(n) | O(n) | |||
| delete | O(1) | O(n) | |||
| binary search | ordered key | lookup | insert | O(n) | O(n) |
| find | O(log n) | O(log n) | |||
| findmin | O(1) | O(1) | |||
| findnext | O(1) | O(1) | |||
| delete | O(n) | O(n) | |||
| sorting | ordered key | printouts | |||
| bubble | binary search | sort | O(n^2) | O(n^2) | |
| insertion | sort | O(n^2) | O(n^2) | ||
| selection | sort | O(n^2) | O(n^2) | ||
| mergesort | sort | O(nlog n) | O(nlog n) | ||
| heapsort | sort | O(nlog n) | O(nlog n) | ||
| quicksort | sort | O(nlog n) | O(n^2) | ||