Secret.Codes's blog

Trie Implementation. Help please
By Secret.Codes, history, 7 years ago, In English

There are two famous way for implementing trie.

One is by linked list and other is by 2D array.

Now I want to know which will be better.

I think 2D array is better for time but it needs too much space than linked list.

Please someone explain time and space complexity of those 2 approach.

If there are any better approach then tell.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Time complexity is same for both. Space required for 2D array approach will be higher because you're fixing a particular amount of memory statically at the beginning.

The reason people (and I) prefer to use 2D array method is that we do not normally have to worry about the space (the memory we are provided is more than enough to declare a large static array).

Also, I think most programmers dislike using pointers and dynamic memory allocation and hence avoid the linked list approach (you can implement linked list using static arrays too but I assume you mean the textbook pointer approach).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you sir for your reply. In contest programming I think 2D array is better from your comment because from a problem statement we can know how much memory is needed in worst case .

    → Reply