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