C++ Linked List?

Quote:

Original post by BioProton I just can't grasp the idea.

Are you able to elaborate a bit more on what it is that you're not grasping? You've actually explained the idea on your own...

Quote:

I am talking about a class that contains a pointer to another instance of the same class...

... which would ordinarily suggest you have an understanding already.

I could reiterate the idea, perhaps it might be helpful:

You have a node class with a pointer for the purpose of linking to another instance of that node class. You could have five instances all linked up in sequence, each using their pointer to address the 'next' instance in the sequence. The resulting chain of instances is the so called linked-list.

Your question is kind of vague... but it sounds like you may be having trouble understanding the concept behind a "class" and an "instance of a class" (or "object")

Think of a class as a definition and an object as its living form. Just like you can have a class of type Dog and an actual instance of a Dog (call him Rex.) Now a Dog can bite any other dog ( void Bite( Dog * dog ); ) That should make sense, I hope.

The same way you can have a class, Node that knows about other Nodes. After all, a class knows about itself.

You have the concept right. You basically have two classes, your node class and your linkedList class. The node class contains your data as well as a pointer to a node object, which is the next node in the list. The linked list class has 3 node pointers, a firstNode, a lastNode and a currentNode. The firstNode is the first node in the list, or the head. lastNode is the last node in the list, or the tail. currentNode is used to iterate through the list by grabbing the memory addresses of each subsequent node.

The reason you only need three nodes and not one for each piece of data is because each node exists within its previous node. So if you have 5 nodes, you have your head, which contains a pointer to the second node, which contains a pointer to the 3rd, which contains a pointer to the 4th, which contains a pointer to the 5th (the tail).

Hi. A linked list is a node that knows where the next (and sometimes previous) node is. This is a node:



Here is an empty linked list:


Let's add an item. We add to the front because it's faster, unless we have reasons not to:

Right now, list points to the Node we just made. That node's "next" field points to the rest of the list (which was just NULL from above). The node's "fish" field points to your Golfdish.

Let's loop through the items iteratively:


Let's loop through the items recursively:


You can see there are some limitations to only having 1 pointer. You may want a pointer to the previous node so you can loop backwards or remove nodes from the middle of the list easily.

I wouldn't think of a "LinkedList" class or anything like that. They're useful, but they're not part of the core concept. You should absolutely understand the code above and be able to write it in your sleep.

[Edited by - CadetUmfer on January 3, 2011 11:22:40 PM]

Maybe I didn't ask the question correctly...
How would I add an instance to a linked-list and access its members?

Let's say you want to make a list of Goldfish. Then your node would look like this:


Everything else is exactly the same, except when you make a new Node, you assign your goldfish to it.


The node is just a container that holds your class.

Okay.. I'm with you so far, but now how would I access members of the new Node?

The same way you access anything else:

n->fish->food = guppies;

Also, moved to For Beginners.