Question

It is required to implement a map data structure with the following characteristics:

It stores (key, value) pairs, and both the key and value are of type String
Inserting a new (key, value) pair in the map must have a performance time of O(log n) in the worst case
Looking up a key in the map must have a performance time of O(log n) in the worst case
It is expected to be a main-memory data structure
Which of the following data structures is most appropriate for this requirement

Answer 1

Implement a map data structure

Explanation:

Dictionary is the perfect data structure for this scenario where it have to store key and value pairs that too of type strings each

If we use List or Array we can not assign a key velue of string we can assign a key as index in case of arrays  

In dictionary we can assign both key and value as what ever form we want so its feasible to use string as key

We can insert new key value pairs also to the dictionary in given complexicity using these dictionaries

We can delete the key value pairs if we no longer want to use that dictionary values  

We can also search for any key by searching in logarthimic complexicity as the internal structure code of dictionary in python is being implemented by linked lists

Thus the Linkedlist in C,Dictionary in Python are well suitable data structures for the given sccenario