c - creating a linked list without malloc

Question

in order to create a linked list(which will contain an attribute of next and previous node),i will be using pointers for the 2 next and previous nodes,yet i was wondering if i could complete the code without using malloc(allocating memory): for example: instead of malloc-ing:

link *const l = (link *)malloc(sizeof(link));

if(l == NULL)
  /* Handle allocation failure. */
  ...

l->data = d;
l->next = list->head;

head = l;

can i simply create a new link variable with the attributes formatted(value,pointer to next and previous link),and simply link the last link in my last link in the chain to this one? my list file is b,for example.

link i;
i.date=d;
getlast(b).next=&i

i appologize ahead for the fact i am new to c,and will be more than glad to receive an honest solution :D

edit: i tried using malloc to solve the matter.i will be glad if anyone could sort out my error in the code,as i can not seem to find it.

#include <stdio.h>
#include <malloc.h>

struct Node{
    int value;
    struct Node * Next;
    struct Node * Previous;


};
typedef struct Node Node;
struct List{
    int Count;
    int Total;
    Node * First;
    Node * Last;
};
typedef struct List List;
List Create();
void Add(List a,int value);
void Remove(List a,Node * b);
List Create()
{
    List a;
    a.Count=0;
    return a;

}

void Add(List a,int value)
{
    Node * b = (Node *)malloc(sizeof(Node));
    if(b==NULL)
        printf("Memory allocation error \n");
    b->value=value;
    if(a.Count==0)
    {
        b->Next=NULL;
        b->Previous=NULL;
        a.First=b;

    }
    else
    {
        b->Next=NULL;
        b->Previous=a.Last;
        a.Last->Next=b;

    }
    ++a.Count;
    a.Total+=value;
    a.Last=b;
    }
void Remove(List a,Node * b)
{
    if(a.Count>1)
    {
        if(a.Last==b)
        {
            b->Previous->Next=NULL;
        }
        else
        {
            b->Previous->Next=b->Next;
            b->Next->Previous=b->Previous;
        }

        }
    free(b);
    }

Answer 1

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.

Answer 2

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.

Answer 3

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.

---

^{1. Obviously, the phsyical memory location that new occupied still exists, but it's now free for other processes/threads to use, so the value contained in that address will no longer be what you expect.}

Answer 4

Not really.

You could create a variable for each and every node in your list, but what happens when you want another node? Fifty more nodes? These variables also won't hang around after you've left the scope they were defined in, which means you'd either have to make everything global or use static storage and expose a pointer to them. This means that all pointers to them after that scope will be invalid. These are both very ugly solutions.

If you don't understand what I mean by scope, here's a quick example:

int main() { /* Entering function scope. */
    int x = 5;
    { /* Entering block scope. */
        int y = 7;
        printf("%d\n", y);
    } /* Exiting block scope, all variables of this scope are gone. (y) */
    printf("%d %d\n", x, y); /* Won't compile because y doesn't exist here. */
} /* Exiting function scope, all non-static storage variables are gone. (x)

You could also create a global array, thinking that this gets around having a lot of different variables, but if your solution is to implement this using an array, why are you using a linked list and not an array? You've lost the benefits of a linked list by this point.