Archived

This topic is now archived and is closed to further replies.

linked lists...?

This topic is 5337 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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)

Share this post


Link to post
Share on other sites
Man, if you don''t know what pointers are, you have zero chance on the AP test. Sorry to be the voice of doom.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
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-~-

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
It might not be a big confidence booster, but if you don''t understand pointers and linked lists, you aren''t going to make it very far on the AP Exam. Out of all the AP Exams I took in high school it was by far the most difficult (and the one I studied the most for). It made the AP Physics exam look like a cake walk. The good news is that no matter how hard the exam is and how well (or horrible) you do, it still looks good that you took it when applying to colleges, and the material covered will definitely give you a huge head start in your entry level classes.

The_Ethernopian

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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 node
size 4 bytes 4 bytes ?
data address of pointer address of node ?

rather than just
type pointer node
size 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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Imagine a line of people holding out their right hands and placing it on the shoulder of the person in front.

Over their shoulder have a bag with something in it.

This is your linked list of people.

Say you want to add a new bag with something in it to the list.

Create a person (that''s your node - you''ll have a pointer to the memory it takes up)

Give the person the bag with something in it (that''s the integer value)

Where should you put the person in the list? How many different kinds of places in the linked list of people are there?

There''s the two ends and somewhere in the middle.

To put the person on top of the list would be for them to go to the end and place their hand on the end persons shoulder. This is setting the pointer to ''next'' to point to the next person (node).

To put the person on the bottom of the list would be for them to go to the other end and have a hand placed on their shoulder. You have to tell the end person (node) that its next pointer now points to the new person (node - the node is a pointer to memory, remember?). Also the new person (node) doesn''t have a shoulder to place their hand on so you set the ''next'' pointer to 0 (or NULL)

To put the person in the middle of the list the new person needs their next pointer setting and the previous person in the list needs their hand moving to the new persons shoulder.

Share this post


Link to post
Share on other sites