CODEWITHSUNDEEP
c
Joe
Joe

Reputation: 21

Implementing a simple linked list in C without malloc

All the implementations I have seen online use pointer to declare nodes and then will use malloc to create space for them like this:

struct Node  
{ 
  int data; 
  struct Node *next; 
}; 

int main() 
{ 
  struct Node* head = NULL; 
  struct Node* second = NULL; 
  struct Node* third = NULL; 

  head = (struct Node*)malloc(sizeof(struct Node));  
  second = (struct Node*)malloc(sizeof(struct Node)); 
  third = (struct Node*)malloc(sizeof(struct Node));
...

But I can also create the same without pointers and malloc like this:

struct node {
   int  id;
   struct node* next;
};

struct node head = {0, NULL};
struct node one = {1, NULL};
struct node two = {2, NULL};
struct node tail = {3, NULL};

int main(){
   head.next = &one;
   one.next = &two;
   two.next = &tail;
...

My question is, why the 1st method is mostly the one used, why do we need to declare each node as pointer and why do we need malloc? (Just to point out I know why struct Node *next; is declared as pointer int the struct declaration).

Upvotes: 2

Views: 1350

Answers (2)

Lee Daniel Crocker
Lee Daniel Crocker

Reputation: 13171

If you know ahead of time exactly how many items will be in your list, then you're probably better off using an array rather than a list. The whole point of a linked list is to be able to grow to an unknown size at runtime, and that requires dynamic memory allocation (i.e., malloc).

Upvotes: 3

tadman
tadman

Reputation: 211540

You should do this with local variables, not global ones, but the general idea would be the same. You should also steer towards having arrays and not heaps of otherwise unrelated variables:

struct node {
   int  id;
   struct node* next;
};

int main(){
  struct node nodes[4];

  for (int i = 0; i < 4; ++i) {
    nodes[i].id = (3 - i);

    if (i != 0) {
      nodes[i].next = &nodes[i-1];
    }
  }

  return 0;
}

Where something like that assembles them in reverse order for convenience, but they're all grouped together in terms of memory initially.

malloc is used because you often don't know how many you're going to have, or they get added and removed unpredictably. A general-purpose solution would allocate them as necessary. A specialized implementation might allocate them as a single block, but that's highly situational.

Here the lifespan of nodes is within that function alone, so as soon as that function ends the data goes away. In other words:

struct node* allocateNodes() {
  struct node nodes[10];

  return &nodes; // Returns a pointer to an out-of-scope variable, undefined behaviour
}

That won't work. You need a longer lived allocation which is precisely what malloc provides:

struct node* allocateNodes() {
  struct node *nodes = calloc(10, sizeof(struct node));

  return nodes; // Returns a pointer to an allocated structure, which is fine
}

The problem is if you malloc you are responsible for calling free to release the memory, so it becomes more work.

You'll see both styles used in code depending on the required lifespan of the variables in question.

Upvotes: 3

Related Questions