Linked Lists in C without malloc

Question

#include <stdio.h>

typedef struct node
{
      int i;
      struct node *next;
}node;

node getnode(int a)
{
      struct node n;
      n.i=a;
      n.next=NULL;
      return n;
}

main()
{
     int i;
     node newtemp,root,temp;

     scanf("%d",&i);
     root=getnode(i);
     temp=root;

     while(i--)
     {
         newtemp=getnode(i);

         temp.next=&newtemp;
         if(root.next==NULL)
         {
            root=temp;
         }
        temp=*(temp.next);
     }


     temp=root;

     while( temp.next != NULL )
     {
         printf(" %d ",temp.i);
         temp=*(temp.next);
     }
}

I am trying to create a linked-list without using malloc. The programming is printing only the root and no nodes following it. I couldn`t find the bug. Had there been any memory issue, the gcc compiler would have thrown a segmentation fault.(?) Please ignore the poor programming style..

Answer 1

When you initialise temp.next, what is the value of the pointer that you assign to it?

temp.next=&newtemp;

Why, it's the same one every time! (Draw a picture if you are unconvinced.)

Give it up. If you need an indeterminate amount of memory (which, with an indeterminate number of nodes, you do), then you need to allocate memory.

Answer 2

You can avoid malloc but not for free:

• On Linux/UNIX you could call brk() and write your own memory allocator.
• On every system you can write your own allocator using a fixed size array as a memory source.
• I do do not see what the alternatives would buy over just malloc/free directly. They're there for a reason.
• Returning local variables to be used outside would be simple but is an error and does not work.

Answer 3

You only have two memory spaces that you can use to store nodes, and those are root and newtemp. When you assign a new node to newtemp the old node doesn't exist anymore.

Assuming you entered the number 5 at the scanf, before first iteration of the loop, you have:

5 -> NULL

After the first iteration of the loop, you have

5 -> 4 -> NULL

After the second iteration of the loop, you have

5 -> 3 -> NULL

(The node containing 4 has been completely replaced by the node containing 3).

The only solution is to use malloc, and make getnode return a node*.