PDA

View Full Version : Nodes and Pointers, oh my!




Mooey
Mar 20, 2007, 04:51 AM
Hello, fellow programmers.

I am currently pursuing a major in Computer Science. In my current class the only thing we use are pointers/nodes/2d arrays/linked lists(with pointers)/sorted lists(with pointers)/ etc...

Herein lies the problem:
Back in my old class, I was out the day that we learned pointers and nodes because I was extremely sick. I was just wondering if there was a website that could help me understand pointers/nodes a little better so I can wrap my brain around it.

Thanks!



Caezar
Mar 20, 2007, 05:13 AM
I came across (or rather stumbled upon) this website yesterday. You might find something about the topic you want to research.

http://lecturefox.com/

garethlewis2
Mar 20, 2007, 06:58 AM
I know this sounds aloof, but, since you are studying CS, you should have a book for that course, with a title such as 'Introduction to ADTs', it will definately cover it better than a lecture and website, unless the book they recommend for your course is terrible.

Palad1
Mar 20, 2007, 10:21 AM
http://en.wikipedia.org/wiki/Category:Data_structures

garethlewis2
Mar 20, 2007, 10:38 AM
Wikipedia. Silly me. And there I was thinking the OP wanted to think for themselves.

savar
Mar 20, 2007, 11:42 AM
Hello, fellow programmers.

I am currently pursuing a major in Computer Science. In my current class the only thing we use are pointers/nodes/2d arrays/linked lists(with pointers)/sorted lists(with pointers)/ etc...

Herein lies the problem:
Back in my old class, I was out the day that we learned pointers and nodes because I was extremely sick. I was just wondering if there was a website that could help me understand pointers/nodes a little better so I can wrap my brain around it.

Thanks!

You're seriously screwed. Quit posting here and go straight to your prof's office hours. You won't get anywhere in C if you don't understand pointers.

I can't believe how many posts make claims like "I was out the day they taught pointers"...so you missed exactly one day of class all year, and that one day the teacher decided to cover an enormous topic in 80 minutes and then never mention it again?

The scary part is that this isn't your 1st semester. Can't imagine how you passed intro CS without understanding pointers.

Mooey
Mar 20, 2007, 02:20 PM
You're seriously screwed. Quit posting here and go straight to your prof's office hours. You won't get anywhere in C if you don't understand pointers.

I can't believe how many posts make claims like "I was out the day they taught pointers"...so you missed exactly one day of class all year, and that one day the teacher decided to cover an enormous topic in 80 minutes and then never mention it again?

The scary part is that this isn't your 1st semester. Can't imagine how you passed intro CS without understanding pointers.

Well, my second course (the one where they taught us pointers) I had an A up until I missed that day. I made it out with a B, but the class I am in right now is nothing but pointers - which is why I made a 55 on my first test. He said the prefinal makes up for that so if I can make that up, then I am good to go. My professor has tried to teach me, but he's more of a analysist that tells you how to do it and not how you can understand it. I just want to try and understand it before the prefinal pops up so I can make it up.

I also feel bad because my teammates (for my projects) rely on me a lot and I am having to go back and forth between websites to look up how pointers work.

And no, my previous professor took two days to discuss nodes/pointers - I missed the introduction and so I skipped the boat cruise. Then when we got to our lab assignment I realized that it was anything pointer-related so I copied out of the book because I did not understand, lol.

I know this sounds aloof, but, since you are studying CS, you should have a book for that course, with a title such as 'Introduction to ADTs', it will definately cover it better than a lecture and website, unless the book they recommend for your course is terrible.

We don't use a book in this class. He gives us his lecture notes which is extremely difficult to understand.

scan
Mar 20, 2007, 02:24 PM
pointers and nodes are easy. pointer "points" to a node. not sure why people always trouble with this topic. when I learned it, I found it to be very straight forward. perhaps you could elaborate what you would like to learn exactly or more specific to what you don't understand.

savar
Mar 20, 2007, 03:38 PM
Well, my second course (the one where they taught us pointers) I had an A up until I missed that day. I made it out with a B, but the class I am in right now is nothing but pointers - which is why I made a 55 on my first test. He said the prefinal makes up for that so if I can make that up, then I am good to go. My professor has tried to teach me, but he's more of a analysist that tells you how to do it and not how you can understand it.


Well I suggest you ask the TAs then, or somebody in the class who does get it. But here's a simple explanation (I'm bored at work) -- understanding of computer architecture is needed.

Memory is addresed sequentially, like houses on a street. How much memory is contained at each address is the same for all addresses but varies between different computers. Let's say there is 1 byte at each address.

When you create regular variables, like this:

int i;
char c;

The compiler allocates space in program memory. So it might assign i to address 0. From then on, whenever code uses the variable i, the compiler translates that to a low-level (machine code) instruction which basically says "read the 4-byte value at address 0". (It reads a 4 byte value because int is usually 4 bytes on a 32 bit CPU, and the compiler knows this.) So actually, although the int is stored at 0, the CPU is reading bytes 0-3 from memory.

Next, for c, it will allocate 1 byte, because char is usually 1 byte. Since i is already in 0-3, the compiler will allocate the address 4 for this char.

What happens when you declare pointers?

int *j;
char *d;

Same thing. The compiler allocates space, as pointer variables are still variables.

So it now allocates bytes 5-8 for int* j, and bytes 9-12 for char *d. Why did it allocate four bytes for a char pointer? Because char pointer is a different type than char. A pointer is a variable that contains a memory address. On 32-bit machines, an address is usually 4 bytes long, so any pointer will need to be 4 bytes long or else it wouldn't be able to store the entire address.

So it takes four bytes to store the address of a one byte char. If you had a really long struct -- say its 1000 bytes long -- it would still take only four bytes to store the address of that struct, because you store the address of the first byte only.

C has some special syntax to manipulate pointers.

j = &i;
i = 5;
printf("i is %d and *j is %d", i, *j);

What does this code do?
1) Set j to the address of i. We assumed earlier that i is stored at address 0, so j now takes the value 0. If you were looking at this code in a debugger, j would now be equal to 0.
2) Set i to 5. The compiler generates machine instructions which say, "write 5 to address 0 in memory."
3) Print out the values of i and *j. i is obviously 5. What is *j? The '*' is an operator which is called "dereference"...in C it means to take the pointer variable that follows, look at its value, and then retrieve the data stored at the address equal to that value.

So j is equal to 0 (as we said in step 1). Then the CPU gets the data stored at address 0, which as we described in step 2 is the number 5. So this code prints out "i is 5 and *j is 5". So we modified the value of *j by changing i. Keep in mind that j is a separate variable. We modified j once in step 1, but we DID NOT MODIFY j again in step 2, we only modified i. BIG DIFFERENCE. j is still a variable stored in addresses 5-8.

Now, why do we bother storing pointers in the first place? We can reference variables directly because the compiler already knows where they are stored in memory. In the example above, all we really achieved was to provide a 2nd name (*j) for a variable that already existed (i).

Pointers are usually most helpful for constructing certain types of data structures where we want the data to be easily modifiable. If we break our data into separate nodes (could be nodes in a tree, or in a linked list), then we can reorganize the node structure by modifying the pointers to point at different data -- we don't have to copy the data itself to a different place in memory.

Contrast that to other data types, such as an array. If you have an array with 10 large structs stored in it, and you want to add one more, you can't! You have to create a new array with size 11, copy all the data from the first array into the new one, and then add the new element into the last spot.

If you had used a linked list instead of an array, you could simply modify the last element in the list to point to the 11th struct and you're done!

Quick review of pointers now:

Types: Use '*' to make a pointer type:
int i; // int variable
int *j; // pointer to an int
char c; // char variable
chad *d; // pointer to a char

Operators:
Use '*' to dereference a variable...This means access the memory pointed to, not the memory that the variable is stored in.
Use '&' to get a reference to a variable. This means retreive the address of the variable, not the value stored at that address.

Hope this helps. I'm not a teacher and I RARELY write C code, but hopefully I've been able to elucidate a little. Feel free to ask followup questions.

MacDonaldsd
Mar 20, 2007, 04:44 PM
Pointers are complex to get your head around what ever anyone says.

I advise you, like others have said to go and ask your professor as its a complex topic to get your head around and it features a lot in C.

Mooey
Mar 20, 2007, 11:45 PM
Thanks, savar!

That helps tremendously. I am still stuck on some node stuff, but I get the hang of pointers now - thanks to you and www.cplusplus.com.

I'm going to go practice some linked list stuff/sorted list stuff so I can better myself.

Thanks for all that help.

GeeYouEye
Mar 21, 2007, 12:32 AM
By node, do you mean

struct node {
int data;
node *next;
};
?

This is a single entry in a linked list. You create new nodes, and string them together by setting next. For example

node *cursor = new node;
cursor->data = 5;
cursor->next = new node;
cursor = cursor->next;

Right there I've created a list item, set the data therein, attached a new list item to the tail of it, and set my cursor to be the list item I just created. Thus, I have a list. Note that I have no way of going back to the previous item unless I maintain a pointer to the head node, or set up two links within each node, previous as well as next.

garethlewis2
Mar 21, 2007, 02:55 AM
You don't have a book mentioned for the class, and on this you don't bother doing any research on finding a suitable book that you could use outside of lecture hours to brush on your knowledge?

How the hell did you pass any of the other classes.

If you think linked lists are difficult, and they are not, they are possibly besides straight arrays the simplest of the abstract data types, you are going to find hashes and buckets very very difficult without understanding the basics first.