Oy, question on linked lists

First of all, does anyone have a link to a page that offers a tutorial on C linked lists? I have one here, but I can't seem to understand it very well.


Ok now for my question. I see that in changing the data of an element in a list, you use the -> operator. I may be totally missing something, but I don't know what the -> operator does. Can anyone explain it to me? I saw it like this:

struct person {
char name[20];
struct person *next;
};
struct person *new;
struct person *head;
head = NULL;
new = (person*)malloc(sizeof(struct person));
new->next = head;
head = new



Thanks for you assistance.

when you access the members of a struct you use the dot operator:

struct foo bar;

bar.foonumber1 = 5;
if (bar.foonumber2 == 6)
bar.foonumber3 = 2;

but you have to derefrence when you access the members of a pointer to a struct:

struct foo *bar;

bar = malloc (sizeof (struct foo));

(*bar).foonumber1 = 5;
if ((*bar).foonumber2 == 6)
(*bar).foonumber3 = 2;

much in the same way that you need to derefrence any pointer if you want to work with what it points to. however, because the above notation is cumbersome, the following is a shortcut and produces exactly the same output as above:

struct foo *bar;

bar = malloc (sizeof (struct foo));

bar->foonumber1 = 5;
if (bar->foonumber2 == 6)
bar->foonumber3 = 2;

The arrow has to do with dereferencing a pointer. There is a precidence issue in:

*new.next;

The . and the * I think have the same precidence so therefore associativity comes into effect. I know that in most cases C statements have EDIT *right* associativity, but I forget what happens in this case. It is too much trouble to look up. The solution is to create a new operator.

new->next;

Otherwise you have to do something like this to get the proper result:

(*new).next

I don't remember all the rules in my head, but it goes something like that.

Oy, I guess I can understand that. So essentially new->next is the same as (*new).next, since new is a pointer, right?

So does -> have any other applications? What's the definition of that operator?

Yes, otherwise associativity screw things up if you don't use parenthesis.

I don't know what the formal name is, but it has no other application in this specific context.

I computer only does (essentially) 2 things-- it adds, and it accesses memory locations-- addressing.

Many noobies are confused by the term 'pointer'. When you are learning, and even later, it is perhaps easier to think of a 'pointer' in the terms of 'address of'. So next time you say 'pointer', replace that with 'address of', instead.

As TrollKing has listed, using the '->' operator really is only used with structures.

This is because of how memory is accessed (how the compiler builds the addressing) for accessing fields in a structure.

Let's look under the hood:

Code:

typedef struct                             /* my structure */
   {
   int     theNum;
   char  alphaStr[9];
   long  bigNum;
   }theStruct;

void foo(theStruct*);                  /* a function to call */

theStruct myStruct;                    /* global variable */

myStruct.theNum = 10;              /* some code */
strcpy(myStruct.alphaStr,"ABCDEFGH\0");
myStruct.bigNum = 123456L;
. . .

foo(&myStruct);
. . .

Further, let's say that we are 'long-word aligned'. This just means that when the compiler figures out how to address the fields in the structure, it will align the start of each field on a 4-byte boundary. Some chips require this, others simply operate faster because you're accessing data in chunks of 'native-size' to the CPU. In any event, alignment results in 'padding' unused data space within the structure.

Now, having said that (it's actually useful to know), let's look at what this structure actually looks like in RAM (we'll assume it sits at location 0x001F5B9A.

Code:

Address        RAM (Bytes)
-----------------------------------------------------------------
001F5B9A     00 0A 00 00 40 41 42 43
001F5BA2     44 45 46 47 00 33 0D 16
001F5BAA     00 01 E2 40 DD F7 1C 09
001F5BB2     78 00 00 FF FF FF C7 8A
. . .

In memory, as you can see by the raw coredump above, the address where the structure starts is 0x001F5B9A. If we were to break RAM up by structure field, it would look like this:

Code:

Address        RAM (fields in bytes)
-----------------------------------------------------------------
001F5B9A     00 0A                                     ;theNum (10 decimal)
001F5B9C     00 00                                     ;pad bytes
001F5B9E     40 41 42 43 44 45 46 47 00  ;alphaStr
001F5BA7     33 0D 16                                ;pad bytes
001F5BAA     00 01 E2 40                           ;bigNum
. . .

Okay, now that you have some understand of how things look in RAM, understand that the compiler references the structure based on the address of the first byte of the structure itself (0x001F5B9A). All the fields are referenced by offset (0x001F5B9A+0x0 [0d] = theNum, or 0x001F5B9A+0x4 [4d] = alphaStr, or 0x001F5B9A+0x11 [17d] = bigNum).

When you have a function where the structure variable has been declared/defined within it, you access the fields of the structure using '.'-- this is because the compiler will calculate the offsets to each field- relatively. You are working with the actual structure, not a pointer to the structure.

When you pass the address of the structure variable to another function (like foo(), above), foo() doesn't have the structure, it just gets the address of the variable which contains the address of the structure-- a pointer.

Thus, you use '->' to go _indirectly_ through the contents of the variable passed-- which is the address of the structure in RAM.

I'm sorry I can't draw a picture-- pictures are so much simpler. Hopefully, my example above will also teach you other things.

Wow lots of info. Thanks.

Originally posted by Sayeh

*snip*

just remember that all this stuff is compiler-specific.

>>>strcpy(myStruct.alphaStr,"ABCDEFGH\0");
An oversight here, I believe You don't need the \0 at the end of the string, it's already null terminated as it is a string literal.