c - 为链表编写前缀的惯用方法是什么？

Question

我已经开始用 C 编写链表实现:

typedef struct node node;
struct node {
    node *next;
    int value;
};

我可以轻松编写将新节点附加到列表末尾的函数 append:

void append(node *head, int value) {
    if (! head->next) {
        head->next = malloc(sizeof(node));
        head->next->value = value;
        return;
    }

    append(head->next, value);
}

如果我使用像 Scheme 这样的函数式语言编写 prepend，显而易见的做法是简单地返回一个新节点，其中“next”指向前一个头部:

(define (prepend head value)
        (cons value head))

我可以很容易地用 C 写这个:

node *prepend(node *old_head, int value) {
    node* head = malloc(sizeof(node));
    head->value = value;
    head->next = old_head;

    return head;
}

但是现在我的 append 函数没有返回任何东西，只是改变了列表，而我的 prepend 函数确实返回了一些东西但没有' t 改变原始列表。这是链表实现方式的副作用，但感觉不对。

一个解决方案可能是重写 prepend 以添加一个新节点，但使用前一个头部作为新值，使用新节点作为旧头部的值...

void prepend(node *head, int value) {
    node* new = malloc(sizeof(node));
    memcpy(new, head, sizeof(node));

    head->next = new;
    head->value = value;
}

但是这也让人感觉不对。

另一种解决方案可能不是将列表表示为头节点，而是表示为指向头节点的不同结构:

typedef struct list list;
struct list {
    node *head;
};

现在我的 prepend 函数可以只更改 list->head 指向的位置，而不必返回任何内容。这感觉最干净，但它引入了额外的负担；现在我必须使用辅助函数来追加和许多其他函数(或以不同方式实现它们)。

在 C 中实现此功能的惯用方法是什么？

---

注意:我是 C 的新手，非常感谢任何关于我的代码风格或正确性的评论，即使与问题无关。

Answer 1

在我看来没有“正确”的答案，但我喜欢struct list 方法。您甚至可以使其对最终用户不透明。然后，您可以将底层实现更改为双向链表或由数组支持，用户无需更改任何代码即可利用它。