Allocate a consecutive linked list in c

Im trying to create a linked list in c. The twist is that I want to allocate the memory for the list so that all the nodes are consecutively stored in memory. Maybe an array structure is the way to go. Any id开发者_开发技巧eas?

---

The obvious way would be to allocate a number of nodes in a block, then link them together into a free list. When you need to add a node to your linked list, you'll grab the one from the head of your free list. When you want to delete a node, you link it back onto the free list:

struct node { 
     struct node *next;
     // other data here.
};

node *free_list;

#define block_size 1024

void initialize() {
    free_list = malloc(block_size * sizeof(struct node));

    for (i=0; i<block_size-1; i++)
        free_list[i].next = &free_list[i+1];
    free_list[block_size-1].next = NULL;
}

struct node *alloc_node() { 
    struct node *ret;
    if (free_list == NULL)
        return NULL;
    ret = free_list;
    free_list = free_list->next;
    return ret;
}

void free_node(struct node *n) { 
    n->next = free_list;
    free_list = n;
}

---

If you're looking at a linked list, don't worry about where in memory they are. That's what the pointers on the nodes are for.

If you want them sequential, allocate an array.

---

Yes, use an array. More interesting is why you want this. If your program requires this to work, then you'll need to make sure your array is big enough to store all the nodes that might be allocated. If not, you can allocate batches of nodes.

FYI. I've seen this strategy used in the past on the assumption that sequentially allocated nodes would result in fewer cache misses when searching the list. In the system of interest, that didn't actually give much a performance improvement. [ Not enough profiling of course!.]

---

You could do something like this

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

struct node linkedlist[50];

This would allocate space for linked list structure in contiguous locations.