BST:
- locating/deleting/inserting an element is not slow -- O(logn)
- maintain the order between elements
- support range query
- if not balanced, the worst case is like a linked list
Hashtable:
- look up operation is fast: O(1) if the hash function is well chosen.
- have space overhead
- don't support range query
Array:
- allow random access
- can explore cache locality
- updating is costly
Linked List:
- allow easy insertion/deletion
- do not support random access
- may not have cache locality
No comments:
Post a Comment