-2

Which data structures should I use to implement a trie in Java?

Do I use a linked list, array, map?

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
deepeshdm
  • 43
  • 4
  • 1
    "*Which data structure is used to implement a Trie ?*" - What is a "*Trie"*? – Turing85 Sep 28 '20 at 14:44
  • 4
    @Turing85 https://en.wikipedia.org/wiki/Trie – Konrad Rudolph Sep 28 '20 at 14:45
  • 1
    For example like this: https://stackoverflow.com/questions/2225540/trie-implementation (not suggesting that this is a very good reference implementation, it has some obvious problems that the author is asking about, but still...) – Hulk Sep 28 '20 at 14:48
  • 5
    The data structures you mention aren’t on the same level of abstraction, so they aren’t mutually exclusive (for instance, a map can be (and very often is) implemented in terms of an array). In fact, the requirements for the data structure underlying a trie posits some kind of lookup. But how that’s implemented isn’t fixed, and different possibilities have different pros and cons. – Konrad Rudolph Sep 28 '20 at 14:48
  • There seem to be numerous examples out in the wild. I'd suggest Googling "java trie implementation". There is no one right answer as to how to implement such a structure. – CryptoFool Sep 28 '20 at 14:52
  • A trie *is* a data structure. Java does not have a built-in implementation. – chrylis -cautiouslyoptimistic- Sep 28 '20 at 15:59

1 Answers1

3

The way I implemented a Trie was to use a custom class for the node and store outgoing links as either a HashMap or ArrayList (depending on the number of child nodes).

The reason to split the two cases was that many of the nodes would have just a few child nodes and using a Map would actually slow things down. If I recall correctly I put the limit at about 4 child nodes.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176