memory allocation in C, LInked List in a Heap

Question

I'm building a single linked list and trying to allocate memory for it like so

struct node *new_node = (node*) malloc(sizeof(node) * 5);

so enough memory for 5 nodes. Now accessing the first node via:

new_node->data = new_data;

is fine, but when I go to link another node to new_node->next, I forget how I say that the new node is a part of the memory I've already allocated. I don't want to malloc each time I want a new node as for the purposes of the assignment I'm working on, we want to malloc as infrequently as possible.

Any clues greatly appreciated, this far I haven't been able to find what I need on the great wide webs.

John!

Answer 1

The very simplified solution when memory for any new element is allocated separately:

#include <stdio.h>
#include <stdlib.h>

struct node
{
 int data; // some data, not a link to next element
 struct node * next;
};

int main()
{
 struct node *head = NULL; //
 struct node *tail = NULL; //
 // creating the first node
 head = (node*) malloc(sizeof(node));
 if(head != NULL)
 {
  tail = head;
  tail->next = NULL;
  // fill the data here
 }
 // creat any more
 for(int i = 1; i < 5; i++)
 {
  tail->next = (node*) malloc(sizeof(node)); // create new
  if(tail->next != NULL)
  {
   tail = tail->next; // move tail to next
   tail->next = NULL;
   // fill the data here
  }
 }
}

Of course, operations with nodes (insertion, deleting, etc) should be organized as functions.

But if you want to save your original memory allocation approach, consider the following:

    // allocation memory for 5 elements
 struct node *new_node = (node*) malloc(sizeof(node) * 5);
 // arranging pointers
 for(int i = 0; i < 4; i++)
 {
  new_node[i].next = &new_node[i+1];
 }
 new_node[4].next = NULL; // like a sign of the END

Answer 2

You got it wrong, you don't need to allocate space for five nodes and point to them with the first node, instead

struct node *head = malloc(sizeof(struct node));
if (head == NULL)
    return errorHandler();
head->next = malloc(sizeof(struct node));
.
.
.

and so on.

What I do there is I allocate space for one, node and when I need a new node, I allocate space for it and point to it with the next field of my struct node.

Answer 3

Node* five = malloc( 5 * siozeof(Node) );
int nxt = 0;

Node* p = &five[nxt++];
p->next = &five[nxt++];

etc