Thread: newbie question about linked list

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    91

    newbie question about linked list

    Hi!

    I just stated reading "algorithms in C" by robert sedgewick. I wrote a couple of simple programs to create linked list but each one gave me some problems The problems I have are highlighted in bold. Here is the first simple program:


    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    
    struct node
    {
           int item; 
           struct node *next;
    } *start;
    
    int main()
    {
        int i, N = 4;
        struct node *x;
        start = x;
        
        for(i = 1; i <= N; i++)
        {
              x->next = (struct node*) malloc(sizeof(struct node));
              x = x->next;
              x->item = N-i+1;
              if(i == N)
              {
                   x->next = NULL;
                   break;
              }
              else
                  x = x->next;
        }
        return 0;
    }
    why do i get and error when i run the above program ?

    Here is second program:

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node *link;
    
    struct node
    {
           int item; 
           link next;
    };
    
    void printlist(link t1)
    {
         while(t1 != NULL)
         {
             printf("%d, ", t1->item);
             t1 = t1->next;
         }
    }
    
    int main()
    {
        int i, N = 5;
        link x, t;
        t = x;
        
        for(i = 1; i <= N; i++)
        {
              x = malloc(sizeof(link));
              if(1 == i)
                   t = x;
              x->item = i;
              if(i == N)
                   x->next = NULL;
              x = x->next;
        }
        printlist(t);
        return 0;
    }
    This program complies and links fine but does not print the list as i expected ????

    Also the book uses the malloc function in a different way which I didn't really understand

    x->next = malloc(sizeof *x)
    I don't understand what is going on in this malloc the sizeof operator (takes a pointer to x ????) and there is no typecasting in the return ??


    I am a little flimsy on my basics I guess , any help would be great
    I used devC++ compiler to compile these.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well in the first example, you get an error because on the first time through the loop, there is no "x->next", because you don't have an "x" allocated.

    You don't typecast the return of malloc because it isn't needed. You don't need to typecast assignments to pointers from a void pointer type. The sizeof question takes the size of the object x. (The dereferencing is done at compile time, and gives a constant size of the object.)

    The second example is wrong, because 'link' is a pointer, and 'sizeof( link )' is the size of a pointer, not the size of the actual structure.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    184
    in the first code you are declaring the pointer of type node which is notm pointing anywhere and not even a NULL. it should be something like this

    Code:
    struct node *x;
    
    x= malloc(sizeof struct node);
    
    start=x;
    s.s.harish


    and then a

  4. #4
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    Thank you I see waht I am doing wrong in the first program but I am still a little confused on the second one.

    What change would i make to make the memory assignment correct and make it work ????
    I tried sizeof *link but it doesn't work ????

    the author in the book did this :

    link x = malloc(sizeof *x);

    which is kinda hard to understand since if we proceed from right to left hes take the size of an object before even declaring it and then he intializes it with its own size ????????????

  5. #5
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    SORRY FOR THE DOUBLE POST !!!!!!!!

    I also saw this in the book which confuses me even more. This is a part of a program from the book "algorithms in C" by robert sedgewick page 98 "Check the bold line in the program"

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node *link;
    
    struct node
    {
           int item; 
           link next;
    };
    
    int main()
    {
        struct node heada, headb;
        link t, u, x, a = &heada, b;
        int  i;
        for(i=0, t = a;  i< N; i++)
        {
             t->next = malloc(sizeof *t);
             t = t->next; t->next = NULL;
             t->item = rand() % 100;
        }
    
        return 0;
    }

    The author made a head node and is pointing the head node to the first node of the list but how can he access the t->next without its memory assignment, this is the same thing I was doing in the first program and I used to get an error ?????????

  6. #6
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    Quote Originally Posted by gemini_shooter
    the author in the book did this :

    link x = malloc(sizeof *x);
    uh, dude.............look above you
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  7. #7
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    struct node *a; //this is the same size as ...
    int *a;
    char *a;
    void *a;
    ......

    these all point to a memory location. struct node *a only creates the pointer. there is no memory allocated for the int inside of the structure, nor is there any memory allocated for the pointer inside of the structure. in you first program, you assigned x to start, but x didn't point to anything to begin with. then, when you said x->next, that (x) could be pointing at just about anything...it could be pointing to memory that doesn't even exist. you first have to allocate memory to assign x to point at. then, you can assign memory to the variables within x.
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  8. #8
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    makes sense now !!!

    deep stuff !!!! I still have a lot to learn but then would this statement be right as pointed out in the book

    link x = malloc(sizeof *x); ??????

    Thanks a lot

  9. #9
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    I get it !!!

    man I am really dumb at this stuff but finally I get it

    Thanks a lot for all the help !!!!

  10. #10
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    this line
    Code:
    int *p = new int(5);
    cout << sizeof(*p) << " " << sizeof(p) << " " << sizeof(int) <<  endl;
    prints out
    4 4 4

    sizeof(TYPE) is the only thing i use
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  11. #11
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    This is what Sedgewick basically does:

    Code:
    #include <stdio.h>
    
    typedef struct node *link;
    
    struct node {
            int data;
            struct node* next;
    };
    
    int main(void)
    {
            struct node heada;
            link t;
            t = &heada;  /* comes from the initialisation from the for loop */
    
            printf("Size of *t: %d\n",sizeof(*t));
            printf("Size of t: %d\n",sizeof(t));
    
            return 0;
    }
    Output is:
    Code:
    bash-3.00# ./sizeof3
    Size of *t: 8
    Size of t: 4
    "t" points to the address of heada, so the size of t is just 4 since its just a 32-bit pointer - the size of *t applies indirection to what t is pointing to, in this case the size of struct node which is 8.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. linked list question
    By yeahdixon in forum C++ Programming
    Replies: 2
    Last Post: 03-28-2002, 09:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM