Oy, question on linked lists

This is a discussion on Oy, question on linked lists within the C Programming forums, part of the General Programming Boards category; First of all, does anyone have a link to a page that offers a tutorial on C linked lists? I ...

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    21

    Question 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.

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    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;
    hello, internet!

  3. #3
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    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.
    Last edited by Troll_King; 08-16-2002 at 08:16 AM.

  4. #4
    Registered User
    Join Date
    Aug 2002
    Posts
    21
    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?

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    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.

  6. #6
    Sayeh
    Guest
    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.

  7. #7
    tammo21
    Guest
    Wow lots of info. Thanks.

  8. #8
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    Originally posted by Sayeh

    *snip*
    just remember that all this stuff is compiler-specific.
    hello, internet!

  9. #9
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>>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.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question regarding linked lists.
    By IXxAlnxXI in forum C++ Programming
    Replies: 2
    Last Post: 10-18-2007, 12:54 AM
  2. Question regarding comparing two linked lists
    By cyberfish in forum C++ Programming
    Replies: 2
    Last Post: 08-23-2007, 04:28 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 09:50 AM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21