Comparison of DataStructures

• Unsorted Array:
  • Add: add the records as the last entry  fast O(1)
  • Delete a target: slow finding the target, fast at filling the hole O(n)
  • Search: sequential search slow O(n)
• Sorted Array:
  • Add: insert the record in proper position. much record movement slow O(n)
  • Delete a target: how to handle the hole after deletion, much record movement slow O(n)
  • Search: binary search fast O(log n)
• Linked list:
  • Add: fast if one can insert node anywhere O(1)
  • Delete: fast at disposing the node, but slow at finding the target O(n)
  • Search: sequential search slow O(n)
    
• Hash table:
  • Add: fast O(1)
  • Delete: fast O(1)
  • Search: fast O(1)
• Hash Function:
  • Maps a key to an index within a range:
    • If key type is int, key % Tsize
    • If key type is string, convert the string to an integer and then %Tsize
  • Goal of hash function:
    • fast to compute
    • even distribution

Read Full Post »