c++ - 遍历链表的不同方式

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

你显然明白第一种方法。

第一个和第二个之间的根本区别在于用于枚举列表的指针所在的位置。首先，指针 values 通过局部变量使用，每次将其更新为当前节点的 next 指针的值。在第二种情况下，一个指向指针的指针用于保存“当前”指针的地址。它指向的指针是“列表中”的实际指针，而不仅仅是它的值。最初它寻址 head 指针。每一步它都指向当前节点的 next 指针。当算法完成时，它将保存链表中 last 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 成员)，指向指针的指针可以提供优雅的解决方案。

祝你好运。