Создание связанного списка без malloc в C

Для размещения узлов без malloc также есть возможность использовать для этой цели стек. Это интересно только как небольшое упражнение, но в реальном коде было бы плохой идеей.

Идея состоит в том, что всякий раз, когда необходимо выделить новый узел, вы делаете рекурсивный вызов, а затем продолжаете остальную логику программы без возврата из этого рекурсивного вызова. Только когда программа может выйти, вы избавитесь от рекурсии. Это не очень удобно для работы, приводит к трате памяти, так как в этом стеке находятся не только выделенные узлы, но и некоторые другие данные, которые больше не нужны. Кроме того, при удалении узла из списка повторное использование пространства невозможно, если только вы не поддерживаете также свободный список.

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

#include <stdio.h>

struct listNode
{
    int value;
    struct listNode *next;
};

void printList(struct listNode *head) {
    while (head != NULL) {
        printf("%d -> ", head->value);
        head = head->next;
    }
    printf("NULL\n");
}

void deleteFromList(struct listNode **headPtr, struct listNode **tailPtr, int value) {
    while (*headPtr != NULL && (*headPtr)->value == value) {
        *headPtr = (*headPtr)->next;
    }
    if (*headPtr == NULL) {
        *tailPtr = NULL;
        return;
    }
    struct listNode *current = *headPtr;
    while (current->next != NULL) {
        if (current->next->value == value) {
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    *tailPtr = current;
}

void appendToList(struct listNode **headPtr, struct listNode **tailPtr, struct listNode *new) {
    new->next = NULL;
    if (*tailPtr != NULL) {
        (*tailPtr)->next = new;
    } else {
        *headPtr = new;
    }
    *tailPtr = new;
}

// This is the main program's logic, but it gets called recursively whenever a node
//   is inserted into the list:
void menu(struct listNode *head, struct listNode *tail) {
    struct listNode new;
    char choice;
    while (1) {
        printf("[i]nsert, [d]elete, [p]rint, [e]xit: ");
        scanf(" %c", &choice);
        switch(choice) {
            case 'p':
                printList(head);
                break;
            case 'i':
                printf("insert value: ");
                scanf(" %d", &new.value);
                appendToList(&head, &tail, &new);
                menu(head, tail); // Recursion
                return;
            case 'd':
                printf("delete value: ");
                scanf(" %d", &new.value);
                deleteFromList(&head, &tail, new.value); 
                break;
            case 'e':
                return;
        } 
    }
}
    
int main()
{
    menu(NULL, NULL);
    return 0;
}