linked list implementation

[aegis]

I've seen code for linked list implementations where the
Node class has a data member for some type
in addition to a pointer to another Node. The
issue? The "some type" is, from what I have seen,
never a pointer to "some type", hence you would
have to have a default constructor for the
"some type". But what about a case where
a default constructor might not be ideal?

It would seem more sensible to me to have
the data member of the Node class, to be
a pointer to "some type". Thoughts?

 

[Ian Collins]

I've seen code for linked list implementations where the
Node class has a data member for some type
in addition to a pointer to another Node. The
issue? The "some type" is, from what I have seen,
never a pointer to "some type", hence you would
have to have a default constructor for the
"some type". But what about a case where
a default constructor might not be ideal?

I don't think I've ever seen such a case, care to post an example?

It would seem more sensible to me to have
the data member of the Node class, to be
a pointer to "some type". Thoughts?

That's why most do!

 

[joseph cook]

I've seen code for linked list implementations where the
Node class has a data member for some type
in addition to a pointer to another Node.  The
issue?  The "some type" is, from what I have seen,
never a pointer to "some type", hence you would
have to have a default constructor for the
"some type".  But what about a case where
a default constructor might not be ideal?

It would seem more sensible to me to have
the data member of the Node class, to be
a pointer to "some type".  Thoughts?

Well, then you just have to worry about even more memory management as
you allocated the sub-field. I don't understand the part about the
default constructor. Why do you need to default construct them?
Can't you pass the information to the Node when you create?

Node n = new Node(43);
Node(int value) : m_value(value){} // Nt default constructed, but
"value" is unique.

Joe Cook

 

[sebastian]

I don't really understand your question. The bottom line is that the
type will need to allow for copy-construction - there is really no way
around that.

#include <list>

struct foo
{
foo( char )
{ }

foo( foo const& )
{ }
};

int main( void )
{
std::list< foo >
foos( 3, foo( 'a' ) ); // fine, copy constructor used
foos.push_back( foo( 'b' ) ); // fine, copy constructor used
foos.resize( 10 ); // error, no match for foo::foo( )
return 0;
}

 

[Joshua Maurice]

I've seen code for linked list implementations where the
Node class has a data member for some type
in addition to a pointer to another Node.  The
issue?  The "some type" is, from what I have seen,
never a pointer to "some type", hence you would
have to have a default constructor for the
"some type".  But what about a case where
a default constructor might not be ideal?

Not really. std::list just requires that the contained element be copy
constructable, not default constructable. Big difference. (The
forthcoming C++0x standard changes the requirement into move
constructable, which is even better.)

It would seem more sensible to me to have
the data member of the Node class, to be
a pointer to "some type".  Thoughts?

Then define it like that:
std::list<your_type *>
instead of
std::list<your_type>

This is fine, unless you also want std::list to have ownership
semantics over the contained pointed-to objects, in which case, yes,
std::list does not do that. This is a real use case which I
occasionally hit. You're welcome to roll your own on top of std::list.
It's a ~20-30 line exercise left to the reader.

 

[Juha Nieminen]

I've seen code for linked list implementations where the
Node class has a data member for some type
in addition to a pointer to another Node. The
issue? The "some type" is, from what I have seen,
never a pointer to "some type", hence you would
have to have a default constructor for the
"some type". But what about a case where
a default constructor might not be ideal?

Are you talking about your (maybe hypothetical) own linked list
implementation, or are you talking about std::list?

If you are making your own linked list implementation, then there are
two possibilities:

1) In the constructor of the Node structure, call the data member
constructor (or copy constructor) is called appropriately.

2) If this is not feasible for some reason, then you'll have to resort
to lower-level trickery: Rather than instantiate objects of type Node,
only reserve space for them (using eg. std::allocator or ::new) and then
use placement-new to construct the data member with the proper
constructor parameters.

 

[James Kanze]

I don't think I've ever seen such a case, care to post an
example?

That's why most do!

Do they? Mine never did, and the implementations of std::list
that I've seen don't either.

But I don't see the reason behind the original posters comments.
Why would a Node type which contains the data type require a
default constructor for the data type?

 

[Ian Collins]

Do they? Mine never did, and the implementations of std::list
that I've seen don't either.

You're right, I was answering with my C programmers hat on! I really
should find better things to do on a Sunday afternoon...