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

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

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

Solution 3

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.

Solution 4

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 

Solution 5

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

View more solutions

Comments

[gablin]

A linked list without using malloc? Is that even possible?

[letsc]

Why?? I am not sure but why cant it possible when we have stack allocation and well defined copy constructor???

[mrivard]

Welcome to SO :) You can, and should, use the "010101"-button or 4-space indent to have your code snippets marked up as code. I did it for you just now.

[letsc]

Thanx Magnus. I didnt know. m new here. :)

[R.. GitHub STOP HELPING ICE]

@smartmuki: You tagged this question C, then you go asking about "well defined copy constructor"? C has no such thing as a copy constructor, or any constructors at all.

[letsc]

Ahhhh!! I wasnt getting the right word. I meant member-wise copy.. Incovenience regretted..

[Ken Bloom]

Have a look at stackoverflow.com/questions/3002764/…, which is a very special case of creating an immutable list in C++ without using malloc. (It doesn't work in straight C)

[Rup]

You could use alloca I suppose? kernel.org/doc/man-pages/online/pages/man3/alloca.3.html msdn.microsoft.com/en-us/library/5471dc8s.aspx Or you could create large memory pool with a single alloc / local char[] and handle your own allocation within that.

[John Bode]

@gablin: Sure. You could declare an array of nodes statically, and use that as your memory pool. It assumes you have an idea of what the upper bound for the number of nodes will be, but it's a perfectly valid method (and when I was doing Fortran 77 in college, it was the only method). malloc()/free() give you more flexibility, but they're not strictly necessary.

[gablin]

@John Bode: Yes, this is true as long as you have a bounded list. I was referring to an unbounded list but forgot to mention it. ^^

[Seva Alekseyev]

This is all about unwillingness to check the malloc() return value for zero and implement out-of-memory logic, isn't it? :)

[letsc]

yeah that is the normal stuff we do. I was trying to implement it without using malloc. Are our lives gonna be impossible without malloc?? Please help.

[Ken Bloom]

Yes, it's gonna be impossible without malloc.

[Matteo Italia]

"You can avoid malloc but not for free" makes a very bad pun :D

[R.. GitHub STOP HELPING ICE]

Strictly speaking, you could put an array of nodes on the stack or declare them static, and make your function pull the next one from the array instead of using malloc.

[Jens Gustedt]

You are actually missing one, which is easier to use than both of these: VLA.

[Jens Gustedt]

@Nathan: sorry, variable length array, please see my answer

[Ken Bloom]

@R. You are right. Some of the same tricks I came up with for stackoverflow.com/questions/3002764/… could be used here as well.

[Seva Alekseyev]

Still, the amount of available nodes is limited to the value of n at array initialization time. These VLA's are not dynamically growing, are they? It's just a syntactic sugar around a malloc() call, isn't it?

[Seva Alekseyev]

Two words - "custom allocator" - would've sufficed. That avoids malloc() in letter but not in spirit.

[Jens Gustedt]

@Seva: no, they are not dynamically growing, but that wasn't the question. No they are not sugar around malloc but usually allocated on the stack and not the heap.

[Seva Alekseyev]

Syntax sugar around alloca(), then :)

[Jens Gustedt]

@Seva: no not exactly either, since first the scope of such an allocation is, well, the scope and not the function. And then alloca is not part of standard C, thus even less portable than assuming VLA and C99 ;)

[Seva Alekseyev]

Um, the scope of allocation is an implementation detail, isn't it? One can be sure that the VLA is not allocated until the moment of initialization (since the desired size is only known then), but how do you know that it's not freed together with the rest of the stack frame when the function returns? That's how alloca() behaves IIRC.

[Jens Gustedt]

@Seva: It is freed when you leave the scope of its validity, maybe even before you leave the function. This is the idea of scoping variables. On the other hand if the scope is main you can do all stuff you want with it, call functions whatever, until you exit from there. As someone said "You can avoid malloc but not for free" or coined in other terms the compiler has to determine the scope of your allocations somehow.

[Seva Alekseyev]

Provably wrong. I just compiled (with GCC on Mac) a small snippet with a VLA inside an arbitrary scope, and on the exit of the scope, there was a big fat nothing. Like I said, the moment of actual freeing is an implementation detail. Since the VLA is not lexically visible outside of its scope, you cannot tell if it still occupies the memory. And freeing stack variables comes for free (pun intended) with the function exit, since you have to increase the SP in the epilogue anyway.

[Jens Gustedt]

@Seva: I am not sure that I understand what you are trying to prove and in what your findings contradict what I was saying. What I simply tried to say is that you should not use a stack variable when it has fallen out of scope. In terms of VLA this is even more dangerous than for other types of variables, since the stack layout may have changed when you re-enter the scope, for-loops, goto, longjmp must be done quite carefully. But I also think that this discussion deviates too much from the original question.

[Seva Alekseyev]

True, this went way into off-topic territory. I took an exception to your statement that VLAs allocation/freeing behavior is somehow different from that of alloca(). It's the same.

[Vatine]

The main reason to write your own allocator is when you have specific needs from it. That way you can get an allocator atht is perfectly suited for your program. Most times, though, it isn't worth it.