Linked Lists and Classes

Hi, I've found this example of a linked list on the web:

http://www.dreamincode.net/code/snippet82.htm

..and my question is this: in the example the author has a structure within the class called 'node' and within that is the usual linked list things, but why not just place these things right in the class itself? Instead of creating new 'nodes' you would create new 'myLinkedListClasses'. I guess what I'm really wondering is if one approach is better(more efficient) than the other or if they're really just the same in the end(as they do both work fine).

Thanks,
Roger

A linked list is a collection of nodes, so the linked list class models that. If you just have nodes linked together, then you still have a linked list, but there is less encapsulation.

OK, so my next question would be: would implementing the linked list without this encapsulation(the 'node' struct) be less efficient in terms of memory usage or even performance?

Thanks laserlight for your fast reply

Probably no difference at all - you still need an item of data and link to the next item in the list in some way, and the struct is just there to simplify the processing of those bits.

--
Mats

Quote:

---

OK, so my next question would be: would implementing the linked list without this encapsulation(the 'node' struct) be less efficient in terms of memory usage or even performance?

---

I think that it depends on the implementation. Logically, there would be very little difference, since it is not a matter of doing away with the node struct, but doing away with the linked list class as a container. Your suggestion is not "instead of creating new 'nodes' you would create new 'myLinkedListClasses'", but "instead of creating a linked list object you would create new 'nodes'".

Intrusive lists are typically slightly faster in real-world usage. However, they require you to change the class you want to put into the list. Non-intrusive lists are more generic and preferable unless you've proven that the intrusive list is worth the hassle.

What do you mean by "intrusive" CornedBee?

Intrusive lists are where the links are members of the data class.
Non-intrusive lists are where the data class is a member or pointee of a node class.