Linked Lists :(

Hey boys :)

So I am taking this c++ course in college and its really tuff :(

I get most of it to an extent but I would love it if one of you boys could explain making a linked list/nodes/and so fourth to me in a simple and basic way. I just don't get it :(

You would be so much help and I'll love you forever <33
Here is a basic node structure:

1
2
3
4
5
template<typename T>
struct node {
    T data;
    node * next;
};


You don't have to understand the "template" part, but you should. This allows the node to hold any type of data, rather than just an integer or double. The "data" variable holds the information in the node. The "next" pointer will point to the next node in the linked list. At the end of a linked list, the last node's "next" pointer should be set to NULL.

The way a linked list works is that memory is allocated for each piece of data you enter into the list. To traverse the list, you would simply use another pointer to hold the memory location of the current node, and then use a loop to set it to the current node's "next" value until you reach the node with the data you're searching for.

To add to the end of a linked list, you need only to create a temporary node with the new data, set its "next" pointer to NULL, and change the memory location of the previous node's "next" pointer to the new node. You should have a "last" and "first" node in your class to hold the positions of the first and last nodes in the list. This allows you to create a new node and change the previous node's pointer without losing the memory space, causing you to have allocated, unused memory.

Let me know if you need clarification on anything.
Thank you :) I'm still a, little bit confused though :(

Why is it important to change thee value of the memory space rather than to just make a, new variable fire it? Also, the nation part that confuses me is when changing the value of the link/node like how does that work and why is it important and stuff. You know?

Thank you so much <33333333333
Ok, let's say we have 3 nodes in our list, and we're adding a new one.

So this is our node structure:

first -> node 2 -> last

First and Last correspond to the pointers in your class used to point to the locations in memory of the first and last nodes in the list.

So now we need to add a new node.
First, we need to create a temporary pointer to a new node. We set this new node's "next" pointer to NULL so that it points to nowhere. Then, we set the memory location of the "last" node's "next" pointer to the temporary pointer's memory location. Then, we just set the memory location of the "last" pointer to the temporary pointer. Now, our structure looks like this:

first -> node 2 -> node 3 -> last

Does that make any more sense?

If you were to set the "last" pointer to the memory address of the temporary pointer without first setting the "next" pointer in the "last" pointer's struct, that pointer would still point to NULL, and you would have nothing pointing to your new node. This would leave a piece of memory allocated, but with no way to use it. This can cause severe problems, such as memory leaks.
What specifically don't you understand? If you point (lol no pun int.) it out, then I can help you in a cool way :) (maybe not so cool)
Last edited on
Hmmm, I don't know exactly what I'm confused about :( I just don't get it UGHHHH

Maybe it would be easier to write out the most basic linked list code and then write comments on why this does that and such?

You guys are awesome !
Do you understand how an array looks in memory and how we use them C++?

Don't know if this will help, but: http://mathhead200.com/pics/comp_sci-list.png
Last edited on
Hey boys :)
if one of you boys could explain...

Fun fact - some girls are also good programmers. I hear they're allowed to vote now too.
Last edited on
Have you seen this, Rachael? It makes a pretty good analogy which might help you understand what a linked list is and how to use it.
http://www.cprogramming.com/tutorial/lesson15.html

@quirky: Careful...

-Albatross
@Albatross

=P I wasn't having a poke at women I was just pointing out how strange it is to assume it's only guys here.
Topic archived. No new replies allowed.