Highlight sequential linked list in c

Question

I am trying to create a linked list in c. The twist is that I want to allocate memory for the list so that all nodes are sequentially stored in memory. Perhaps the structure of the array is the way to go. Any ideas?

Answer 1

The obvious way would be to select several nodes in a block and then link them together into a free list. When you need to add a node to a linked list, you will get it from the head of your free list. When you want to remove a node, you bind it back to 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; } 

Answer 2

If you are looking at a linked list, do not worry about where they are in memory. This is what the pointers on the nodes are for.

If you want them to be consistent, select an array.

Answer 3

Yes, use an array. More interesting is why you want it. If your program requires this to work, you need to make sure your array is large enough to store all the nodes that can be allocated. If not, you can highlight batches of nodes.

FYI. I saw this strategy used in the past on the assumption that consecutively allocated nodes will lead to fewer misses in the cache when searching the list. In the system of interest, this did not actually improve performance. [Not enough profiling, of course!]

Answer 4

You can do something like this

 struct node { int data; struct node *next; }; struct node linkedlist[50]; 

This will allow you to allocate space for the linked list structure in adjacent places.