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 ? :confused:

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 ???? :confused:

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 ?? :confused:

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

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.

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

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 ????????????

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;
}

---

:confused: :confused: :confused:
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 ?????????

Quote:

---

Originally Posted by gemini_shooter

the author in the book did this :

link x = malloc(sizeof *x);

---

uh, dude.............look above you

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.

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

I get it !!!

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

Thanks a lot for all the help !!!!

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

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.