Design Phone Book Data structure

Designa a phone book - basically contact book on phone.
Give data structures and give time complexity to search a phone number.
Ex: search - freeninza and if found in your phone book return the mobile number of user.

Strategy:

Using a Trie can help you on that and the time will be O(L) where L is the string length.

1. input name and find phone number
   -- Trie structure for name (string), phone number as assocaited value.
   -- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2. input phone number and find name
   -- hash table
   (phone number is unique, so use as hash key)
   The great thing about a trie is that it would provide functionality to easily facilitate partial searches, you type in the start of the persons name or phone number and you could return all leaf nodes that match that that prefix. Insertion and search will take O(length of phone number). To display the numbers starting with one or more digits, then the complexity will be the O(prefix length)+O(number of children for the immediate prefix node * length of the remaining number from child nodes).