Реализация простого связанного списка в C без malloc

Question

Все реализации, которые я видел в Интернете, используют указатель для объявления узлов, а затем используют malloc для создания пространства для них, например:

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

int main() 
{ 
  struct Node* head = NULL; 
  struct Node* second = NULL; 
  struct Node* third = NULL; 

  head = (struct Node*)malloc(sizeof(struct Node));  
  second = (struct Node*)malloc(sizeof(struct Node)); 
  third = (struct Node*)malloc(sizeof(struct Node));
...

Но я также могу создать то же самое без указателей и malloc, как это:

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

struct node head = {0, NULL};
struct node one = {1, NULL};
struct node two = {2, NULL};
struct node tail = {3, NULL};

int main(){
   head.next = &one;
   one.next = &two;
   two.next = &tail;
...

Мой вопрос: почему 1-й метод используется чаще всего, почему мы должны объявлять каждый узел как указатель и зачем нам нужен malloc? (Просто чтобы указать, я знаю, почему struct Node *next; объявлено как указатель в объявлении структуры).

Answer 1

Если вы заранее точно знаете, сколько элементов будет в вашем списке, то вам, вероятно, лучше использовать массив, а не список.Весь смысл связанного списка в том, чтобы иметь возможность увеличиваться до неизвестного размера во время выполнения, и это требует динамического выделения памяти (т. Е. Malloc).

Answer 2

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

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

int main(){
  struct node nodes[4];

  for (int i = 0; i < 4; ++i) {
    nodes[i].id = (3 - i);

    if (i != 0) {
      nodes[i].next = &nodes[i-1];
    }
  }

  return 0;
}

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

malloc используется потому, что вы часто не знаете, сколько у вас будет, или они добавляются и удаляются непредсказуемо. Решение общего назначения выделит их по мере необходимости. Специализированная реализация может выделять их как один блок, но это очень ситуативно.

Здесь срок службы nodes находится только внутри этой функции, поэтому, как только эта функция завершается, данные исчезают. Другими словами:

struct node* allocateNodes() {
  struct node nodes[10];

  return &nodes; // Returns a pointer to an out-of-scope variable, undefined behaviour
}

Это не сработает. Вам нужно более длительное распределение, которое именно то, что malloc предоставляет:

struct node* allocateNodes() {
  struct node *nodes = calloc(10, sizeof(struct node));

  return nodes; // Returns a pointer to an allocated structure, which is fine
}

Проблема в том, что если вы malloc ответственны за вызов free, чтобы освободить память, значит, она становится более трудной.

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