algorithm - 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