迭代链表的不同方式

Question

迭代链表时我想到的第一件事就是这样做:

Node* node = head;

while (node)
{
    // do something to node
    node = node->next;
}

但有时我看到人们做了这么复杂的事情:

Node** node = &head;

while (*node)
{
    // do something to node
    node = &(*node)->next;
}

有什么区别,第二个用于什么？

Answer 1

你显然理解第一种方法.

第一个和第二个之间的根本区别在于用于枚举列表的指针驻留在哪里.在第一个中,指针值通过局部变量使用,每次都将其更新为当前节点next指针的值.在第二种方法中,指向指针的指针用于保存"当前"指针的地址.它所指向的指针是一个"在列表中"的实际指针,而不仅仅是它的值.最初它解决了head指针.每一步都会解决当前节点的next指针.当算法完成时,它将保持链表中最后一个 next成员的地址,其值最好为NULL.

第二个具有明显的优点,但没有简单的枚举.此方法更常用于维护方案,例如位置列表插入和删除.

示例:仅使用具有以下节点形式的链接列表的头指针,编写一个将新节点附加到列表末尾的函数:

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

使用第一种枚举方法需要维护先前的指针和特殊考虑因素来检测初始的NULL头指针.以下函数执行此操作,并始终返回链接列表的头部:

struct Node * ll_insertTail(struct Node *head, int data)
{
    struct Node *prev = NULL, *cur = head;

    while (cur)
    {
        prev = cur;
        cur = cur->next;
    }

    cur = malloc(sizeof(*head));
    cur->data = data;
    cur->next = NULL;

    if (prev == NULL)
        return cur;

    prev->next = cur;
    return head;
}

相同的操作,但使用指针指针方法来实际指针成员(不仅仅是它们的值)走路将是这样的:

struct Node* ll_insertTail(struct Node *head, Type data)
{
    struct Node **pp = &head;

    while (*pp)
        pp = &(*pp)->next;

    *pp = malloc(sizeof(**pp));
    (*pp)->data = data;
    (*pp)->next = NULL;

    return head;
}

这可以通过要求调用者首先传递头指针的地址来进一步增强.这增加了它允许您将函数的返回值用于列表头指针之外的其他内容的优点.例如:

int ll_insertTail(struct Node **pp, int data)
{
    while (*pp)
        pp = &(*pp)->next;

    if ((*pp = malloc(sizeof(**pp))) == NULL)
    {
        perror("Failed to allocate linked list node");
        return EXIT_FAILURE;
    }

    (*pp)->data = data;
    (*pp)->next = NULL;
    return EXIT_SUCCESS;
}

调用为:

    int res = ll_insertTail(&head, data);

后两种情况都是可能的,因为通过地址而不是简单地按值使用指针.对于简单的枚举,使用指针指针方法是没有意义的.但是,如果您需要在列表中搜索节点的特定节点或位置并保留使用指针的机制(head可能是某些next成员),指针指针可以提供优雅的解决方案.

祝你好运.