在c中分配连续的链表

Question

我试图在c中创建一个链表.扭曲是我想为列表分配内存,以便所有节点连续存储在内存中.也许阵列结构是可行的方法.有任何想法吗？

Answer 1

显而易见的方法是在块中分配多个节点,然后将它们链接到一个空闲列表中.当您需要将一个节点添加到链接列表时,您将从空闲列表的头部获取一个节点.如果要删除节点,请将其链接回空闲列表:

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