c - c中分配连续链表

Question

我试图在 c 中创建一个链表。不同之处在于我想为列表分配内存，以便所有节点都连续存储在内存中。也许数组结构是可行的方法。有什么想法吗？

Answer 1

最明显的方法是在一个 block 中分配一些节点，然后将它们链接到一个空闲列表中。当你需要添加一个节点到你的链接列表时，你将从你的空闲列表的头部获取一个。当你想删除一个节点时，你将它链接回空闲列表:

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;
}