链表实现中的虚拟节点

Question

我正在尝试实现一个单链表。

要求是: 1.按数据顺序插入2.从头中移除

我需要在我的实现中有一个虚拟节点吗？另外，虚拟节点应该放在列表的开头还是列表的结尾？

我在谷歌上搜索答案，发现在删除列表中的最后一个节点时，虚拟节点很有帮助。但是，我不明白是怎么做到的。有人能解释一下吗？

Answer 1

链表如下所示：

struct list_node {
    struct list_node *next;
    void *data;
};

struct list_node *head;

在C中，你永远不需要链表中的虚节点。

伪节点用于允许在不提供指向指针的指针的语言中的单链表中实现“移除当前”操作。就这样。

当有指向节点的指针时，可以通过将下一个节点移动到节点顶部并释放下一个节点来删除该节点。虚拟节点确保总是有下一个节点来实现此操作。

然而，在C中，保留指向下一个节点的指针会更好。在迭代开始时，这是一个指向head的指针；在开始之后，这是一个指针list_node::next，其中list_node是之前查看的节点。

Answer 2

实现单链表不需要伪节点。它们用作定义与列表元素结构不同的列表结构的替代方法。

根据您的要求，您应该定义一个列表结构，其中包含指向列表头部的指针和指向列表尾部的指针。这将使在末端插入和从头部移除这两个操作操作n恒定时间。

当列表为空时，必须注意正确地维护这些指针。

下面是一个简单的例子：

struct list_elem_s {
    struct list_elem_s *next;
    int data;
    //... other payload fields
};

struct list_s {
    struct list_elem_s *head;
    struct list_elem_s *tail;
};

// initialize a list as empty
void list_initialize(struct list_s *list) {
    list->head = list->tail = NULL;
}

// free all elements from a list
void list_delete(struct list_s *list,
                 void (*free_node)(struct list_elem_s *node)) {
    struct list_elem_s *node;
    while ((node = list->head) != NULL) {
        list->head = node->next;
        node->next = NULL;
        if (free_node)
            free_node(node);
    }
    list->tail = NULL;
}

// add a node at the tail
void list_push(struct list_s *list, struct list_elem *node) {
    node->next = NULL;
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }
    list->tail = node;
}

// remove a node at the head
struct list_elem *list_pop_head(struct list_s *list) {
    struct list_elem_s *node;
    if ((node = list->head) != NULL) {
        if ((list->head = node->next) == NULL)
            list->tail = NULL;
    }
    return node;
}