i'm new to c and i was wondering why do i need to reserve memory for a
new node when moving one (node)

assuming i have a struct like:

struct Test {
    int data;
    struct Test *link;
    }

i traverse the list and see that Test->link == NULL. fine, so i make a
new node. why then, do i see
malloc in my example code. why ? the pointer already has been declared,
it only has to be initiated. right ?
the pointer just points, not stores.

- A pointer is a variable designed to yeld the address of an object.
- When defined, it's not initialized (in most cases).
- There are a few portable ways of assigning a pointer:
  - assign the null pointer constant (aka 0 or NULL)
  - assign the address of an object
  - assign the value returned my malloc() (and brothers)
  - assign the value returned my fopen() (only for FILE* pointers)
  - assign the value of another pointer (or pointer expression)
    of the same type
  - assign the value of another pointer (or pointer expression)
    of any type if its type is void*.
  - assign the value of another pointer (or pointer expression)
    of type void*
(I may have forgot some, correction welcome)

Some example:

   char *pa = 0;
   char *pb = NULL;
   char a;
   char *pc = &a;
   char *pd = malloc (10); /* <stdlib.h> */
   FILE *pe = fopen ("yadayada","r"); /* <stdio.h> */
   char *pf = pd + 1;
   void *pg = pd;
   char *ph = pg + 4;

(kinda pseudo-code)

{
   /* allocates a new node */
   struct Test *pnew = malloc (sizeof *pnew);

   /* success ?*/  
   if (pnew != NULL)
   {
      /* add the new node at the end of the list */
      pTest->link = pnew;

      /* mark the new end of the list: VERY important */
      pTest->link->link = NULL;
   }

p->link = &t;  /* t is a variable of type (struct Test) */
p->link = q ;  /* q is variable of type (struct Test*) */
p->link = malloc(sizeof struct Test); /* Create a new node */

The only thing you care is it should point to something where
you can store data. Not necessarily a malloc'd one.

Dynamic allocation is used so that you can create nodes as and
when you need them, and you can get rid of it when you no
longer need them....

Hope this helps.

- Umesh

--

I had it figured out once i read the man page for malloc and thinking about it
for a bit.
malloc returns a pointer to the allocated memory and thus the pointer gets
initiated.

I was thinking with the wrong mindset, seems to happen a lot. Most questions i
post
though get me so frustrated i solve them myself in maximum a day ;-)

just wondering what it's good for, or if it's still implemented.

also, isn't a binary tree almost the same thing ?

The difference between a link list and a binary tree is search time. A
link list can be searched linearly. Lets say you have linked list and
the 50th element is x. You pass that link list and you need to find x.
It takes 50 iterations! A binary tree on the otherhand is not linear.
You can add nodes in any order specified by your algorithm. This could
lead to faster search times.

My 50 node link list example may not sound too bad but if you have to
constantly search the link list or if the list is very long like a
file system (perhaps) you can get horrible performance times. AI
algorithms may use binary trees to search for solutions; these data
structures are everywhere!

Joel Spolsky (http://www.joelonsoftware.com) has suggested that pointers
and pointer arithmetic are responsible for the high rate of dropout in CS
courses at the time of their introduction. :-)

--
Duncan Bayne

     - Web    http://homepages.ihug.co.nz/~dhbayne/
     - Cell   (+64) (0)25 626 3023