Выделите последовательный связанный список в 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;
}

Answer 2

Вы можете сделать что-то вроде этого

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

struct node linkedlist[50];

Это выделит место для структуры связанного списка в смежных местах.

Answer 3

Да, используйте массив. Более интересно, почему вы этого хотите. Если ваша программа требует, чтобы это работало, то вам нужно убедиться, что ваш массив достаточно большой для хранения всех узлов, которые могут быть выделены. Если нет, вы можете выделить пакеты узлов.

FYI. Я видел эту стратегию, использовавшуюся в прошлом, исходя из предположения, что последовательно расположенные узлы будут приводить к меньшему количеству пропусков кэша при поиске в списке. В интересующей системе это не дало существенного улучшения производительности. [Конечно, недостаточно профилирования!]

Answer 4

Если вы смотрите на связанный список, не беспокойтесь о том, где в памяти они находятся. Вот для чего нужны указатели на узлы.

Если вы хотите, чтобы они были последовательными, выделите массив.