Saturday, July 9, 2011

The Comparison between BST, Hashtable, Array and Linked List

  • 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

  • look up operation is fast: O(1) if the hash function is well chosen.
  • have space overhead
  • don't support range query

  • 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