Data structures (linked list)

[struntz]

Hello everyone!
its been awhile since i've last posted, but school is out again! Yes! Anywho!
I've been searching and searching for some good tutorials on single and doubly linked lists, and stacks. I've found alot in C, but not C++! I was looking for the most efficent way to make a linked list, i see some people making a node class and then a list class, and they seem to make it more confusing than it really is. One time I saw a tutorial that used 3 seperate classes! So if anyone found a site that helped them understand linked lists, and would like to share, it would be greaT! thanks!

But of course if you would like to try and teach me yourself, post up your cleanest looking linked list!

[parksie]

Well, this is all in C and I wouldn't say it's the most efficient (I did it as an educational thing trying to work it out myself!).

In C++, you can go a long way with nested classes. Are you familiar with the STL "iterator" pattern? That basically means that your implementation is irrelevant, so you can keep all the link classes private.

I think I'm rambling....

[CornedBee]

There are two ways to classify linked lists.
single-/double-linked:
List can be single linked or double linked. SLs only contain a reference to the next item, DLs to both the next and previous item.
Container/Inline lists:
Most lists are container lists: they are one or more structures/classes that contain some kind of data. The linked list is most important. Nearly all examples you'll find are for such lists.
Some classes are made as inline lists. An example is CRuntimeClass in MFC. The linked list is hard-coded into the class. You do this for classes where all instances need to be connected. The functionality of the class is most important, the linked list is less important. Working with such classes is usually dangerous as those linked lists are made only for internal use.

Container lists consist of either only one struct/class which holds the data and the links and where you have to keep track of he start yourself, or of at least two structs/classes: one represents a node (and is often hidden inside the class) and one represents the list, containing first and last member and providing manipulation functions.

Most C++ LLs are templated so they can store any type of data. C LLs often stored any 32-bit value (16 bit in earlier times) which could also be void pointers to memory blocks.