Using pointer to a struct to create linked list and Memory allocation in C

Question

I have a concept question I suppose. When I need to create a linked list, but I am just given a pointer to a struct (and the struct contains some data type and pointer "next"). How would I ensure that I am creating the other links and not just the root node? I am not using malloc or else this would be more apparent answer. This list is acting as malloc itself.

Thanks in advance!

To Clarify:

There will be single dimension array which will act as a block of memory of fixed sized. The linked list will then "allocate" by removing a node and putting it into the array or "free" data by removing it from array to add back to list.

example

(struct defined by some data type and pointer) struct is called node

node array[10];  //this acts as memory
node* linked_list;  //this gives or removes data to memory (array)

Answer 1

This is similar to how we did things in my Data Structures class using FORTRAN 77 (back in the mid-Cretaceous); we allocated a fixed-size array and used it as our memory pool.

Basically, you have to maintain a "free" list; these are the nodes that are available for use. When you first start up, you initialize each element in your array to explicitly point to the next element:

struct node {T data; struct node *next; } pool[N]; // for some type T
...
for (i = 0; i < N-1; i++)
  pool[i].next = &pool[i+1];
pool[i].next = NULL;

Your free list initially points to the first element in the pool:

struct node *free = &pool[0];

When you allocate a node, you retrieve the element that free points to, update free to point to the next available element in the list (if one exists), then initialize the element as necessary:

if (free) // is there a free node available
{
  struct node *newNode = free;
  free = free->next;
  newNode->data = ...;
  newNode->next = NULL;
  ...
}

When you're done with a node, you add it back to the head of the free list:

node->next = free;
free = node;

Naturally, real code would be better organized than this, but this should be enough to give you an idea of what to do.

Answer 2

I can't be sure if this applies to your particular question, but I do would like to point out something about creating a linked list without using malloc.

It doesn't really matter how you allocate the nodes of the linked list, be it dynamically or statically. What matters is that every node actually exists and the pointers are valid.

For example, we can build a linked list from an array.

#include <stdio.h>

typedef struct node_t {
    int value;
    struct node_t *next;
} node;

int main() {

    int i;
    node linked_list[10];

    // build the linked list
    for ( i = 0; i < 10; i++ ) {
        linked_list[i].value = i * i;
        linked_list[i].next = ( i < 9 ) ? &linked_list[i+1] : 0;
    }

    // now traverse it
    node *head = &linked_list[0];
    while ( head ) {
        printf( "%d\n", head->value );
        head = head->next;
    }
}

EDIT: in order to use an array as the place from which to "allocate" or "free" the linked list nodes, you can augment the node struct with a flag to indicate if the node is being used or not.

typedef struct node_t {
    char in_use;
    int value;
    struct node_t *next;
} node;

EDIT2: let's give it one last try. Below is the function that "allocates" one node from the array (or returns NULL if none is available). Assume linked_list is global.

node *get_node() {
    int i;
    for ( i = 0; i < 10; i++ )
        if ( !linked_list[i].in_use ) {
            linked_list[i].in_use = true;
            return &linked_list[i];
        }
    return 0;
}

EDIT3: if the array is to be used as a memory pool the way to go is John Bode's answer.

Answer 3

There are several possible scenarios:

• The linked list is using malloc. The linked list is then responsible for the allocation and de-allocation of nodes. This is the standard implementation.

• The linked list is using a statically allocated chunk of memory, ie a static array of fixed size. Such a linked list is more complex, as you would have to keep track of which parts of the array that contain data. You will also need to keep track of the linked list size.

• The linked list is an "array of nodes with index lookup table". It is then not allocating any data, but instead every node contains contains array indices. The linked list will need to keep track of the list size.

• The linked list is not performing any allocation. Allocation is done by the caller (statically or dynamically). In this case the linked list only keeps track of the next pointers and allocates nothing. This version is poor object-oriented design, as it breaks the private encapsulation of data.

EDIT after op change: Seems you are using version 3 above then. Google for "linked list using array" or similar.