Implementing a simple linked list in C without malloc

Question

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

We usually don't use global variables nor write all the code in main, that's why the first version is more used. — David Ranieri
– David Ranieri, Commented May 3, 2019 at 20:10
That, and you rarely know exactly how long your linked list will need to be when it's created. If you do, there's not much point in resizable structures anyway. — cHao
– cHao, Commented May 3, 2019 at 20:15
You can't add any additional nodes to your version. If you've created one, two, three and while your program runs the user asks for 4 nodes you're in trouble. The code to change links (for example to sort the nodes) is also very painful with your approach. — Dave S
– Dave S, Commented May 3, 2019 at 20:15
Also, it has been demonstrated that such linked lists are usually a bad idea anyway. An array outperforms here, even if you need to delete in middle. — Antti Haapala
– Antti Haapala, Commented May 3, 2019 at 20:19

tadman · Accepted Answer · 2019-05-03 20:13:44Z

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.

Lee Daniel Crocker · Accepted Answer · 2019-05-03 20:19:48Z

3

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

answered May 3, 2019 at 20:19

Lee Daniel Crocker

13.3k4 gold badges33 silver badges56 bronze badges

2 Comments

ndim Over a year ago

Corner case: You could dynamically create a list of statically allocated objects at program startup time. You could link a number of drivers (names and number unknown at compile time) as object files to your executable. Each driver object file contains one statically allocated static struct driver object and registers that from an __attribute__(( constructor )) function. The registering will set up the next pointer for the linked list. Then main() will see runtime generated (once only, on program startup) list of drivers to iterate over. For main(), that list is static.

Jasen Over a year ago

linked lists also have other useful properties that arrays do not, such as ease of insertion or deletion of an item.

Collectives™ on Stack Overflow

Implementing a simple linked list in C without malloc

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related