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

Answer 4

You can statically declare an array of node structures and pick new nodes from that array. But then you would've implemented a lame, woefully specialized custom allocator. And the maximum number of nodes available will be the size of that array.

Alternatively, you can use recursion as an allocation mechanism, and do things to the list on the bottom of the recursion stack.

Both approaches are about equally cludgey.

Answer 5

Of course you can build a linked list or any other data structure without dynamic memory allocation. You can't, no matter how hard you try, though, build it allocating no memory at all.

Alternative:

Create a global or static memory pool where you can put your objects, imitating the heap/malloc/free. FreeRTOS does something like. In this situation, you will have a big memory chunk allocated statically since the begining of your program and will be responsible for managing it, returning the correct pointers when a new node is needed and marking that memory as used.

P.S.: I won't question why you want to avoid malloc. I supose you have a good reason for it.

In you program, when you do, in line 20:

     node newtemp,root,temp; 

You are allocatin thre nodes, one of them, "newtemp". Then you do in line 28:

     newtemp=getnode(i); 

It just copies the contents of the returned node over your old "newnode" (controversal, isn't?)

So you do, just bellow:

     temp.next=&newtemp; 

That sets a pointer that initially comes from "root.next" to your "newnode".

     if(root.next==NULL) 

Will be "NULL" at first pass, but then, only replace the same contents.

    temp=*(temp.next); 
     { 
        root=temp; 
     } 

Is, again, copying data from a single allocated object, "*(temp.next)", to another, "temp". It does not create any new node.

It will work if you do like this:

#include <stdio.h>

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

#define MAX_NODES   10

node    *create_node( int a )
{ 
    // Memory space to put your nodes. Note that is is just a MAX_NODES * sizeof( node ) memory array.
    static node node_pool[ MAX_NODES ];
    static int  next_node = 0;

    printf( "[node  *create_node( int a )]\r\tnext_node = %d; i = %d\n", next_node, a );
    if ( next_node >= MAX_NODES )
    {
        printf( "Out of memory!\n" );
        return ( node * )NULL;
    }

    node    *n = &( node_pool[ next_node++ ] );

    n->i = a;
    n->next = NULL;

    return n; 
} 

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

    root = create_node( 0 ); 
    temp = root; 

    for ( i = 1; ( newtemp = create_node( i ) ) && i < MAX_NODES; ++i )
    { 
        temp->next = newtemp; 

        if ( newtemp )
        {
            printf( "temp->i = %d\n", temp->i );
            printf( "temp->next->i = %d\n", temp->next->i );
            temp = temp->next;
        }
    }


    for ( temp = root; temp != NULL; temp = temp->next )
        printf( " %d ", temp->i );

    return  0;
}

The output:

    $ gcc -Wall -o list_no_malloc list_no_malloc.c 

$ ./list_no_malloc
[node   next_node = 0; i = 0)]
[node   next_node = 1; i = 1)]
temp->i = 0
temp->next->i = 1
[node   next_node = 2; i = 2)]
temp->i = 1
temp->next->i = 2
[node   next_node = 3; i = 3)]
temp->i = 2
temp->next->i = 3
[node   next_node = 4; i = 4)]
temp->i = 3
temp->next->i = 4
[node   next_node = 5; i = 5)]
temp->i = 4
temp->next->i = 5
[node   next_node = 6; i = 6)]
temp->i = 5
temp->next->i = 6
[node   next_node = 7; i = 7)]
temp->i = 6
temp->next->i = 7
[node   next_node = 8; i = 8)]
temp->i = 7
temp->next->i = 8
[node   next_node = 9; i = 9)]
temp->i = 8
temp->next->i = 9
[node   next_node = 10; i = 10
Out of memory!
 0  1  2  3  4  5  6  7  8  9 

Answer 6

A linked list is something of indeterminate length, and anything of indeterminate length cannot be created without malloc.

I suggest you simply use malloc to allocate the next link in the chain.

Answer 7

When malloc is used, the 'pointer' to that location is passed on to the variable (which is a pointer).

node* new = (node*)malloc(sizeof(node));

Every time this code is used a "new" location is pointed to. On the contrary, you are using normal variables, which have 'statically' allocated memory. That implies, whenever you refer to 'temp' or 'newtemp', you are referring to the same location EACH TIME.

Now you tell me how can you store a 10 element long list using just 3 (root, temp, newtemp) memory locations. You might want to draw out memory locations to imagine what is happening. But remember, each time you call 'temp' its the SAME memory location. For that we must use malloc (or calloc), for dynamically allocating memory.

In that case, we can make do with few pointers (far lesser than the memory used by the list).

Answer 8

Since nobody yet answered this question about the malloc part in the spirit of modern C (aka C99). If your compiler is conforming to that you have variable length arrays:

node myNodes[n];

where n has some value that is only determined at run time. You probably shouldn't overdo it with this approach since this is limited to the size of the stack, and otherwise you might encounter a stackoverflow.