Hello, I am studying for my AP Exam tommorrow on C++ and I can''t figure out Linked Lists... This is the class...node struct node { int info; node *next; }; node *list; The pointers are throwing me off because we never learned what they were...and here is some code... node *GetNode(int sum); //Creates a new node containing num and a NULL Pointer //Returns a pointer to this node void Append(node *& list, int num) { if (list == NULL) list = GetNode(num); else { node *temp = list; while (temp->next != NULL) temp = temp->next; temp->next = GetNode(num); } } What I don''t understand is list like an array even though its just (node *list? I dont understand how you can have this...pointers are too confusing! Thanks! <- Digital Explosions -> "Discipline is my sword, faith is my shield do not dive into uncertainty, and you may live to reap the rewards" - (Unreal Championship)

Hmm, well in an over-simplified description, the node just has a copy of itself, thus repeating infinitely, but it doesn''t fill up the memory because the child node is only the "possibility" of a node. If you want a more accurate description I probably can''t help you much other than saying that pointers are just memory addresses.

-~-The Cow of Darkness-~-

its ok I understand now! lol, Pointers are addresses to variables...

apparently the book didn''t mean that node *list; was a list as in an array, its just one node...so now I understand how to link nodes up in a linked list fashion...but thanks for the confidence booster! lol...next up! Binary Trees! w00t!

<- Digital Explosions ->
"Discipline is my sword, faith is my shield
do not dive into uncertainty, and you may live to reap the rewards" - (Unreal Championship)

hehe I was joking, its gunna be hard as hell, but oh well, I think I can take the A next year because I am retaking the course cause they are switching it to java for next year...

<- Digital Explosions ->
"Discipline is my sword, faith is my shield
do not dive into uncertainty, and you may live to reap the rewards" - (Unreal Championship)

Sorry to be off topic, but you really are doomed, anyways:

void Append(node *& list, int num)

I''v never seen that done before for some reason. Thats a reference to a pointer to a node type right? Whats the point of adding the extra indirection?

Unless it was an inline function so the compiler could maybe not create a stack variable when it was optimizing, (which it obviously isn''t an inline function), then why add the reference? It wont save you space, it will actually just use up 4 more bytes!

It will be a reference to a pointer to a node type, so:

type    reference           pointer          nodesize    4 bytes             4 bytes          ?data    address of pointer  address of node  ?rather than justtype    pointer          nodesize    4 bytes          ?data    address of node  ? 

which is the same thing.



OK, for hi-jacking the thread, I''ll help a little:
pointers contain the address in memory that refers to another location in memory. They really just are addresses, so they can contain any location in memory, but because C++ is type-safe (kind of), pointers are of certain types. The pointers don''t actually take up any more or less room depending on what they point to, but you need to know what type of thing they point to so you know how to deal with it (floats are stored different in memory than ints, and ints are stored different than strings, etc).

There is a reason for linked lists, they solve a simple problem having to do with memory management.

In an array, the data is contiguous, as you probably know. And when you declare an array as such:

int someArray[SIZE];

SIZE has to be a constant, no exceptions, so the size cannot be determined by the user, a variable, or anything else, it must be known before the program is ever run.

The solution to this problem is of coarse dynamic memory, as such:

int * somePointerToAnArray = new int[size];
you can use somePointerToAnArray in any way you could use someArray, except you can make it any length you want when you create it. Later, because you created this memory for your program dynamically, or on the go, you have to delete it using delete[] somePointerToAnArray;

But what if you wanted to resize the array, or delete an element, or add an element to the back? Tough luck. You would have to destroy the entire thing, create a new one with the size you want, and put the old array in there how you want it (without an element, etc).

Linked lists solve this problem, because every element (or node) in the list has a pointer to the next element in the list (and for doubly linked lists, they also have one to the previous element).

Thus, memory is arranged like thus:

FirstNode       Node Data           Data NextNode * --> NextNode * --> ... 

You know there is no next node when NextNode * points to nothing.

With this system, you can add a new node by dynamically creating it, and then moving the previous last node''s NextNode pointer to point to the new one, and setting the new node''s NextNode pointer to point to nothing. To delete a node, you just delete the node, and then set the previous nodes pointer to the one after the deleted note''s NextNode, or if the deleted node was the last node in the list, you set the previous nodes pointer to nothing, or 0, or NULL, (all the same thing).

There are advantages (dynamic memory) and disadvantages (some extra space, lots of overhead depending on the type and usage of the linked list, etc) to linked lists. But unless you want to use a more complicated structure, they are often necessary.

Hope this helps, good luck on the exam. .sen