A many-to-many mapping data structure

Question

What would be a good way representing: i. Given a key, return all the data values associated with that key AND ii. Given a data value, return all the keys that are associated with that data.

So far, all I can think of is to maintain all keys in a sorted linked list where each "key" node has a key value and a vector of pointers to data nodes (in addition to linked list bookkeeping). Likewise, maintain all data values in a sorted linked list and each "data" node has a data value and a vector of pointers to the relevant keys.

Could you please offer me a hint for a more appropriate solution to this problem?

Answer 1

Use two indices: the first index allows you to map a key value to the corresponding tuples that contain that key value; the second index allows you to map a data value to the tuples that contain that data value. Each index can be implemented as a hash table, binary tree, or any other data structure you like that provides fast lookups.

For instance, databases implement ideas like this to enable fast lookups and searches.