whcih data structure you use for mobile contact list

which data structure will be used for storing mobile contact list and If enter "ma" it should show all contacts in sorted list starting with ma letters.


Many people give answers we can use Hashtable or Array list but those are suitable but that is wrong answers , try with Binary search tree.

A hash table can insert and retrieve elements in O(1) .
A BST can insert and retrieve elements in O(log(n)), which is quite a bit slower than the hash table which can do it in O(1).


Try using Hash table :

When designing a cell phone, we need to think much about memory. A hash table is an unordered data structure –  which means that it does not keep its elements in any particular order. So, if you use a hash table for a cell phone address book, then you would need additional memory to sort the values when user enters input  So, by using a hash table you have to set aside memory to sort elements . i.e it requires more memory.

Try with BST(Binary Search tree)

Because a binary search tree is already sorted, there will be no need to waste memory or processing time sorting records in a cell phone. As  mentioned earlier, making a lookup or an insert on a binary tree is slower than doing it with a hash table, but a cell phone address book will almost never have more than 5,000 entries. With such a small number of entries, a binary search tree’s O(log(n)) will definitely be fast enough. So, given all that information, a binary search tree is the data structure that you should use in this scenario, since it is a better choice than a hash table or Array list