Saturday, July 9, 2011

The Comparison between BST, Hashtable, Array and Linked List

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