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