Void* or Template for Linked List

[TriTz]

Hi! guys! I have a question about generic linked list.
I made one using C.

typedef struct list{
	void *info;
	struct list *next;
} List;

but now I have to translate it to C++, but I must use templates instead of void*.

template <class T>
class Node{
	public:
	T info;
	Node<T>* next;
	Node(T m, Node<T> *p = NULL) {info = m; prox = p;}
};

template <class T>
class List{
	Node<T> *first;
	
	public:
	List(void){ first = NULL; }
        void insert(T m);
	void print();
};

I figured out that I can only get a list with one type node and not a list with different types of node.

int main(){
        /*One type for list*/
        List<int> L;
        List<float> F;
        List<string> S;
}

This is not what I want.
How can I use generic data nodes with templates?

example:

Listpointer -> int -> float -> string -> int -> char -> NULL

thx

[jsmith]

Polymorphic containers are not an easy problem. There are a couple of options.

1) Use boost::any instances to hold your data values. Solution is something like:

struct node {
    template< typename T >
    node( const T& d ): data( d ), next() {}
  private:
    boost::any data;
    node*       next;
};

struct List {
    template< typename T >
    void insert( const T& d ) {
        if( !head ) {
            head = new node<T>( d ); 
        } else {
            node* tmp = head;
            for( ; tmp->next; tmp = tmp->next );  // <- yes, semicolon here
            tmp->next = new node<T>( d );
        }
    }
  private:
    node* head;
};

2) Use boost::variant to hold the data. Solution is similar to 1), except that
you must know at compile time all of the types you'll store in the list.

3) Custom solution. For example:

(I'm omitting some of the details in case this is a school project.)

class node_base {
    node_base* next;
  public:
    node_base(): next() {}
};

template< typename T >
class node : public node_base {
    T data;    
  public:
    node( const T& d ) : data( d ) {}
};

class polymorphic_list {
    node_base* head;
  public:
    polymorphic_list() : head() {}

    template< typename T >
    void insert( const T& d ) {
       node_base* n = new node<T>( d );
       // ... etc ...
     }
};

In all three cases, the limitation is that someone, somehow has to know the type of the data stored in each node if you want to do anything with it.

In solution 3, you could write polymorphic_list::print() to walk the list and call the print() method on each node, in which case node_base::print() would be declared pure virtual and the derived classes would need to implement it. For example,