how to create a heterogeneous link list in c or c++

Question

A link list that can hold float,integer,character,etc data and algorithm should be well and not very complex

I thought of creating a structure with void pointer that will point to subsequent nodes. but problem is that i cannot use templates with structure.

coming down to c, i have to test each character entered by user to test whether it is integer , float or character or not.then we can proceed further

please suggest an efficient algorithm/code

Solution 1

If you want to do this yourself you'll basically want to create an array or linked list of elements that encode both the data and the type of data. You could use a struct that includes a type indicator and a union of the various types that you want to handle, and the create an array or linked list of that struct:

typedef struct {
    int type_indicator;
    union {
        float f;
        int i;
        double d;
        void *p;
        char c;
    }
} generic_item;

generic_item generic_array[10];

I'll leave it to you to come up with an appropriate enumeration for the type indicator and to add a function pointer for your algorithm. If you want a linked list instead of an array, you'll obviously also need to add a generic_item *next pointer.

I haven't looked into the boost options that other answers link to, but I'd probably look there first before trying to roll my own solution.

Solution 2

Using boost::variant or boost::any. Depends on your needs.

Solution 3

NOTE: This is a purely C answer.

This data structure is what I would start out with:

typedef struct heterogeneous_list
{
    enum { CHAR, STRING, FLOAT, INT } type;
    void *item;
    struct heterogeneous_list *next;
}

When I got the item from the user, I would store it in the list (assuming current points to the end of the list):

current->next = malloc(sizeof(heterogeneous_list));
case (/* whether the user entered a char, string, float, or int */
{
    case /* char */:
        current->next.item = malloc(sizeof(char));
        current->next.type = CHAR;
        current->next.next = NULL;
        break;
/* and so forth, for string, int, and float */
}
current = current->next;

When iterating through the list, it is easy now to process what is in the list based on type. The following code assumes current is the current item in the list being looked at in an iteration (a for-loop going through the list):

char currentItemChar;
char * currentItemString;
float currentItemFloat;
int currentItemInt;

case (current->type)
{
    case CHAR:
        currentItemChar = *((char*) current->item);
        // process a character
        break;
    case STRING:
        currentItemString = (char*) current->item;
        // process a string
        break;
    case FLOAT: 
        currentItemFloat = *((float*) current->item);
        // process a float
        break;
    .
    .
    .
};

That's what I would do.

Solution 4

http://www.boost.org/doc/libs/1_48_0/doc/html/variant.html

(which of course also mentions C/C++ unions before explaining what boost variants give you over this)

Solution 5

A heterogeneous linked list can be created by using a void * as a pointer to a data item:

struct Node
{
    Node * previous;
    Node * next;
    void * p_data;
};

Before implementing a heterogenous container, one might ask if the design can be changed to use homegeneous containers instead.

View more solutions

Comments

[sbi]

"which of course also mentions C/C++ unions before explaining what boost variants give you over this" I consider your void* just as bad. -1 from me.

[avakar]

@sbi, I didn't get your comment, but FYI, the question is also tagged with c.

[djhaskin987]

Everyone, I hit enter on accident before I completed this post.

[sbi]

@avakar: Oops. That's a legitimate objection to my close vote. I still don't like this, but as a pure C answer it's probably as good as it gets. Downvote removed. (You might want to point out that this is a C answer, though, at the top of your answer. C/C++ mixed answers often confuse the public into downvoting based on the tag they're coming from.)

[pravs]

i have tried a method and problem arises when you will traverse the link list.just think over it

[pravs]

your idea has clicked and triggered a path to solve this problem.. thanks

[Thomas Matthews]

@pravs: The method for traversing a linked list is the same regardless of the data in a node; in fact, there doesn't need to be data in the node!

[pravs]

I agree with you but that is possible only when the head(start) of link list is too a void pointer rather than Node* type

[Thomas Matthews]

@pravs: The head of a linked list points to a Node. It has nothing to do with the data type inside the node.