Binary Trees vs. Linked Lists vs. Hash Tables

Question

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 1

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

Answer 2

Your use case is presumably going to be "insert the data once (e.g., application startup) and then perform lots of reads but few if any extra insertions".

Therefore you need to use an algorithm that is fast for looking up the information that you need.

I'd therefore think the HashTable was the most suitable algorithm to use, as it is simply generating a hash of your key object and using that to access the target data - it is O(1). The others are O(N) (Linked Lists of size N - you have to iterate through the list one at a time, an average of N/2 times) and O(log N) (Binary Tree - you halve the search space with each iteration - only if the tree is balanced, so this depends on your implementation, an unbalanced tree can have significantly worse performance).

Just make sure that there are enough spaces (buckets) in the HashTable for your data (R.e., Soraz's comment on this post). Most framework implementations (Java, .NET, etc) will be of a quality that you won't need to worry about the implementations.

Did you do a course on data structures and algorithms at university?