c - creating a linked list without malloc

Yes - you can do that.

e.g.

link l1,l2;
l1.next = &l2;
l2.next = NULL;

Is a perfectly fine and valid linked list of 2 nodes. You could also create a bunch of nodes, and link them together based on your needs, e.g. create a linked list of the argv:

 int main(int argc, char *argv[])
       int i;
       link links[100];
       for (i = 0; i < argc && i < 100; i++) {
          //assuming the nodes can hold a char*
           links[i].data = argv[i]; 
           links[i].next = NULL;
           if (i > 0)
              links[i-1].next = &links[i];
        }

There are of course some drawbacks:

• The number of nodes is determined at compile time in these examples. (in the last example one could malloc a buffer for argc nodes instead of hardcoding 100 though)
• The lifetime of these nodes are the scope they are declared in, they no longer exists when the scope ends.

So you cannot do something like this:

 void append_link(link *n, char *data)
 {
      link new_link;
      n->next = &new_link;
      new_link.next = NULL;
      new_link.data = data;
 }

That is invalid, since when append_link ends, the new_link is gone. And the passed in n->next now points to a local variable that is invalid. If new_link instead was malloc'ed, it will live beyond this function - and all is ok.

There are only two ways in C to create in-memory data structures that don't have a fixed-at-compile-time size:

• with allocated storage duration, i.e. via malloc.
• with automatic storage duration, which in terms of implementation, means "on the stack", either using variable-length arrays or recursion (so that you get a new instance at each level of recursion).

The latter (automatic storage) has the property that its lifetime ends when execution of the block where it's declared terminates, so it's difficult to use for long-lived data. There's also typically a bound on the amount of such storage you can obtain, and no way to detect when you've exceeded that bound (typically this results in a crash or memory corruption). So from a practical standpoint, malloc is the only way to make runtime-dynamic-sized data structures.

Note that in cases where your linked list does not need to have dynamic size (i.e. it's of fixed or bounded size) you can use static storage duration for it, too.

Memory for new nodes has to come from somwhere. You can certainly create individual variables and link them manually:

link a, b, c;
...
a.next = &b;
b.next = &c;
c.next = NULL;

As you can imagine, this approach doesn't scale; if you want more than 3 elements in your list, you'd have to allocate more than 3 link variables. Note that the following won't work:

void addToList( link *b )
{
  link new;
  ...
  b->next = &new;
}

because new ceases to exist when the addToList exits, so that pointer is no longer meaningful¹.

What you can do is use an array of link as your "heap", and allocate from that array. You'll need to keep track of which elements are available for use; an easy way of doing that is initializing the array so that each a[i] points to a[i+1] (except for the last element, which points to NULL), then have a pointer which points to the first available element. Something like the following:

// You really want your "heap" to have static storage duration
static link a[HEAP_SIZE];

// Initialize the "heap"
for ( size_t i = 0; i < SIZE - 1; i++ )
  a[i].next = &a[i+1];
a[i].next = NULL;

// Set up the freeList pointer; points to the first available element in a
link *freeList = &a[0];  

// Get an element from the "heap"
link *newNode = freeList;
freeList = freeList->next;
newNode->next = NULL;

// Add a node back to the "heap" when you're done with it:
deletedNode->next = freeList;
freeList = deletedNode;

Again, you're limited in how many list nodes you can create, but this way you can create a large enough "heap" to satisfy your requirements.