链表实现中的虚拟节点

Question

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

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

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

我用谷歌搜索了答案，发现虚拟节点在删除列表中的最后一个节点时很有用。但是，我无法理解如何。有人可以解释一下吗？

Answer 1

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

根据您的要求，您应该定义一个列表结构，其中包含一个指向列表头部的指针和一个指向列表尾部的指针。这将使这两个操作，在末尾插入和从头部移除都运行 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;
}

Answer 2

链接列表如下所示：

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

struct list_node *head;

您永远不需要 C 语言链表中的虚拟节点。

虚拟节点用于允许 "remove current" 操作在不提供指向指针的指针的语言中的单链表中实现。就这些了。

当您有一个指向节点的指针时，您可以通过将下一个节点移动到它上面并释放下一个节点来删除该节点。虚拟节点确保始终有下一个节点来实现此操作。

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

链表实现中的虚拟节点

Dummy nodes in Linked List implementation

c

linked-list

data-structures

singly-linked-list