遍历链表的不同方法

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;
}

什么是区别，第二个用途是什么？

- template boy

---

这是查看实际汇编代码的好例子。如果一开始你不理解也没关系，只要比较汇编行数的差异就足够了。我经常将小样例粘贴到http://gcc.godbolt.org/中。它有过滤器，使得它比使用-S编译，然后查看未经过滤的结果更方便。 - technosaurus

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成员），那么指向指针的方法会提供优雅的解决方案。

祝好运。

- WhozCraig

Answer 2

在第一个代码示例中，变量node是指向Node结构体的指针。它包含存储Node结构体的内存位置的地址。

在第二个代码示例中，变量node是指向Node结构体的指针的指针。它包含一个内存位置的地址，该内存位置包含存储Node结构体的内存位置的地址。

这听起来令人困惑，主要是因为变量名在两个代码示例中都相同，并且几乎与Node相同。让我们重写代码示例，以便更清楚地了解指针的含义。

第一种情况：

Node* node_pointer = head;

while (node_pointer != NULL) {
    // node_pointer points to a Node
    // do something to that Node, then advance to the next element in the list
    // ... something ...
    node_pointer = node_pointer->next;  // advance
}

第二种情况：

Node** node_pointer_pointer = &head;

while (*node_pointer_pointer != NULL) {
    // node_pointer_pointer points to a pointer which points to a Node
    // do something to that Node, then advance to the next element in the list
    // ... something ...
    node_pointer_pointer = &((*node_pointer_pointer)->next);  // advance
}

在这两种情况下，变量 head 都是指向 Node 结构体的指针。这就是为什么在第一种情况下它的值直接赋给了 node_pointer 的原因：

node_pointer = head;

在第二种情况下，使用 & 操作符获取 head 的内存地址。

node_pointer_pointer = &head;

Node是什么?它是一个结构体，包含（可能还有其他的）一个next字段，该字段是指向Node的指针。这就是为什么在第一个代码示例中可以直接将next的值赋给node_pointer，但在第二个代码示例中必须使用&运算符引用它的原因。

为什么第二种方法很有用？在这个例子中，它并不实用。如果您只想遍历链表的元素，则只需要指向Node结构的指针即可。

然而，当您想要操作下级指针时，指向指针的指针非常有用。例如，假设您已经遍历完链表，现在想要添加一个新节点到尾部。

在上面的第一种情况中，node_pointer没有用，因为它的值是NULL。您无法再进行更多操作。

在第二种情况下，虽然*node_pointer_pointer的值为NULL，但node_pointer_pointer的值不是NULL，它是链表中最后一个节点的next字段的地址。因此，我们可以把一个新的Node结构体的地址赋值给该next。

*node_pointer_pointer = make_new_node();  // make_new_node() returns a pointer

请注意*node_pointer_pointer中的星号或解引用运算符。通过解引用node_pointer_pointer，我们可以得到next指针，并且我们可以将其赋值为一个新的Node结构体的地址。

还要注意，如果node_pointer_pointer指向空列表的头部，则此赋值仍然有效。解引用它会得到head，并且我们可以将其赋值为一个新的Node结构体的地址。

- Michael Laszlo