map creation using link list in c

[can-mohan]

Hi Guys,

Any body knows what is the efficient way to create the map (key,value pair ) using linklist using c .Apart from this in this map one key can have multiple values and i need to display those values. I don't want implementation in c++.

example string1->"james"
         string1->"mike"
         string1->"harry";

[Schol-R-LEA]

Does it have to be a linked list? There are several options, really, but we'd need to know what you're goal is and what the constraints on the design are.

If it must be a linked list, the simplest solution is to have an ordered list of ordered lists. You would need two node types, one for the key/value sets and the second for the values themselves:

struct key_node 
{
    key_type key;     /* where key_type is whatever type the key is */
    struct value_node* values;
    struct key_node* next;
};

struct value_node
{
    char* value;
    struct value_node* next;
};

The insert function would search through the key_nodes for the position of the key, and if it isn't present, would create a node for it; then it would search through the values to find the location for the value, and insert it there.

Mind you, that's what you would want to do if you needed it to be a linked list. There are better alternatives which would be more efficient, at least potentially, depending on how large the data set is and how much you knew about it in advance.

For example, if you knew that the key was an integer value in a fixed range, you could use a simple lookup key. This would just be an array of the value_node type which is the size of the full range of keys. It would probably use a lot of memory, but with a fairly small range (say, less than 10000) it would be reasonable, and lookup on the keys would be a simple array index.

If the keys are of some other type, such as strings, but you had a good idea of the maximum size, you could use a hash table. This is again an array of a simplified key_node type:

struct key_node 
{
    key_type key;
    struct value_node* values;
} KEY_TABLE[SIZE];

where SIZE is the maximum expected number of keys. You would apply a transformation to the key, called a hash function, that returns an integer value in the range of array indices. Ideally, the has for any key would be unique, but that doesn't need to be the case, as there are ways of resolving hash collisions that can be applied to it. On insertion, you would hash the key to get the index, then if there is a key already there, you would check to see if it matched the key you were searching on. If it is, you would then search the list of values. If there is no value there you would insert the key there. If there is a different key already there, you would apply your choice of resolution methods, the simplest of which is to just move one array element down and check the value there, until you found either a match or an empty slot. Lookup would be very similar, except if you didn't find a match you would return an error indicator of some kind.

If you weren't sure about the size, there are ways of having extensible hash tables, but that can get complicated quickly. Instead, you would probably turn to a binary tree of some sort:

struct key_node 
{
    key_type key;
    struct value_node* values;
    struct key_node *left, *right;
};

The tree is constructed by adding the first node, AKA the root, then inserting the succssive nodes to either the left or the right depending on whether the key value is less than or greater than the root. You would descend down the tree until you found the right location for the particular key node. For example, if you already have the tree

               6
             /   \
            4     7
           /  \    \
          2    5    8

and had a new node 3, you would add it at the left of 2.

               6
             /   \
            4     7
           /  \    \
          2    5    8
           \
            3

This is a fairly efficent structure; you can usually find a given node after only a few lookups. There is a down side to it, though: a simple binary tree can easily get unbalanced, depending on the order of inserts. In the worst-cse, it becomes the same as a linear list. To avoid this, there are several ways of rebalancing a binary tree. Types of automatically rebalancing binary trees include red-black trees, splay trees, AVL trees, and tries. Which you would use would depend on what the most appropriate one for your needs is, and how complicated you were willing to make the tree.

Finally, if you were dealing with a very large amount of data, or had to work with data stored on disk, you would want to look at B-Trees and their derivatives.

Finally, as an old supporter of Project Xanadu, I might as well mention enfilades, just for the sake of mentioning them somewhere.

[can-mohan]

Thanks for your input. key -value pair will be like string type and I am going to read from configuration file .key will have maximum size 20 character and value length might be 30-40 characters.

[Schol-R-LEA]

OK, assuming the key can have any arrangement of alphanumeric values, 20 x 36! is a huge range, but that doesn't rule out anything except a simple lookup table. What matters more is how many keys you can expect to have in the file. Since you describe it as a configuration file, I would assume that the number of keys wouldn't be tremendous, less than 100 most likely. A hash table with a suitable hash function should work nicely in that case.

However, that's based on the assumption that you actually meant that it is a file for configuring the program; if it is a more general sort of data file, the size would be less predictable. If you expect a really large data set, a B-tree would probably be the way to go; you would use the B-Tree to cache the data rather than keeping it all in memory at once.

Can you give more details about what it is configuring?

[can-mohan]

It will have MIB information.

[Schol-R-LEA]

MIB? Can you be a bit more specific? As this disambiguation page implies, there are several possible meanings for that acronym.

In any case, the really necessary questions are:

• How many keys do you expect to use?
• Can all of the configuration data fit in memory at one time?
• Will you need to read from the configuration file more than once?
• Will the data be updated or changed during the program run?
• Will you need to write out to the file at any point?