Binary Trees vs. Linked Lists vs. Hash Tables

algorithm hashtable linked-list binary-tree symbol-tables
benmcredmond picture benmcredmond · Dec 16, 2008 · Viewed 85.5k times · Source

I'm building a symbol table for a project I'm working on. I was wondering what peoples opinions are on the advantages and disadvantages of the various methods available for storing and creating a symbol table.

I've done a fair bit of searching and the most commonly recommended are binary trees or linked lists or hash tables. What are the advantages and or disadvantages of all of the above? (working in c++)

Answer

Darron picture Darron · Dec 16, 2008

The standard trade offs between these data structures apply.

  • Binary Trees
    • medium complexity to implement (assuming you can't get them from a library)
    • inserts are O(logN)
    • lookups are O(logN)
  • Linked lists (unsorted)
    • low complexity to implement
    • inserts are O(1)
    • lookups are O(N)
  • Hash tables
    • high complexity to implement
    • inserts are O(1) on average
    • lookups are O(1) on average

Related questions

hash function for string

I'm working on hash table in C language and I'm testing hash function for string. The first function I've tried is to add ascii code and use modulo (%100) but i've got poor results with the first test of data: 40 collisions …

Read More
Hash table runtime complexity (insert, search and delete)

Why do I keep seeing different runtime complexities for these functions on a hash table? On wiki, search and delete are O(n) (I thought the point of hash tables was to have constant lookup so what's the point if …

Read More
How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

So if I have to choose between a hash table or a prefix tree what are the discriminating factors that would lead me to choose one over the other. From my own naive point of view it seems as though …

Read More