在C中插入单链表(指针到指针)

Question

有两个版本的单链表插入函数。

一个是使用一个指针的常见版本，很容易理解：

void insert(struct node *newt) {
struct node *node = head, *prev = NULL;
while (node != NULL && node->data < newt->data) {
prev = node;
node = node->next;
}
newt->next = node;
if (prev == NULL)
head = newt;
else
prev->next = newt;
} 

另一种是使用指针对指针：

void insert(struct node *newt)
{
struct node **link = &head;
while (*link && (*link)->data < newt->data)
link = &(*link)->next;
newt->next = *link;
*link = newt;     //confuse me
}

我对*link = newt;感到困惑。尽管我将newt分配给*链接，但上一个节点仍然指向原始地址？

提前谢谢！

Answer 1

在前面插入节点时，必须更新列表的头。之后插入时，必须更新上一个节点的next字段。使用指向节点的指针可以做到这一点：

最初：

struct node **link = &head;

现在link是指向头指针的指针。如果更新*link，则通过该指针更新头部。

稍后：

link = &(*link)->next;

现在link是指向当前节点的next字段的指针。如果更新*link，则更新该next字段。

在这两种情况下，如果从*link读取，则会得到当前节点。

Answer 2

上一个节点仍然指向原始地址？

在*link = newt;中，它将newt分配给上一个节点的next成员。

CCD_ 13指向CCD_ 14或指向前一节点的CCD_。