在链表中按排序顺序插入节点时，为什么要使用双指针？

Question

typedef struct node node;
struct node {
    int data;
    node *next; 
};

int insert_asc(node **phead, int data) {
    node **traser;
    node *newnode = malloc(sizeof(node));
    if (newnode == 0)
        return 0;
    newnode->data = data;

    for (traser = phead; *traser != 0; traser = &(*traser)->next)
        if (data <= (*traser)->data)
            break;

    newnode->next = *traser;
    *traser = newnode;
    return 1;
}

我感到困惑的是当您解除双重指针时。 为什么(*traser)->next保留下一节点的地址？ *traser在这里具体是什么？

- raven39

---

发布一个最小化、可编译的代码。 - Melon

"traser"是一种追踪前一个节点的“next”指针的方法。如果要在列表中间插入，则需要修改前一个节点的链接，使其指向新节点。 - Gerhardh

我建议你在代码上进行一些“橡皮鸭调试”。如果你尝试使用简单的“链表”在纸上完成所有操作，也可能会有所帮助。 - Some programmer dude

与小黄鸭聊天时，也要查看C运算符优先级。 - David C. Rankin

Answer 1

在这里，您使用双指针来跟踪列表的头。

如果您在此处使用简单指针并交换节点，则可能会丢失列表某些节点的地址。

这是因为如果您将简单指针传递到列表的头部，那么您将在函数中操作您头部地址的副本，因此当您在函数中交换位置时，您的头部地址仍将保持不变，如果您将头部与另一个节点交换，则您的函数修改列表后，旧头部之前的所有节点的地址都将丢失。

编辑：pythontutor.com 是一个工具，通过其出色的可视化工具帮助我轻松地理解了链表的行为，我强烈建议您使用它。

- alamit

---

问题实际上和列表头没有太大关系。可以用一个单指针node *prev代替前一个节点的.next元素来完成。 - Gerhardh

他的回答很公正，并回应了标题中提出的问题，而该问题似乎与最后一个问题不同。然而，你会把列表指针的地址传递给函数，这样函数就可以在其中进行更改，并在调用程序中看到更改。如果仅传递了指针本身，那么函数将收到一份副本，并且对任何更改都会在返回函数时丢失，直到更新的列表指针被返回并在调用程序中再次赋值。底线是，你不会冒失去“某些节点”的风险，而是冒失去你的“列表地址”的风险。 - David C. Rankin

Answer 2

在发布的代码中，双指针用于两个不同的目的：

• node **phead：链表的头部通过引用传递，因此如果新节点必须插入到链表的头部，则可以通过insert_asc进行更新。在C语言中无法通过引用传递，实现它的惯用方法是通过将指向要由函数更新的值的指针传递给函数，因此使用了双指针phead。

• node **traser：为了避免对空列表和在列表头部插入进行特殊处理，程序员使用指针来跟踪插入新节点的位置。traser首先指向列表的头部，即phead的值，在确定必须在当前节点之后插入新节点时，将其更新为指向节点之间的链接，即当前节点的next成员。这是一种优雅的实现插入而不需要特殊情况的方法。由于C语言允许使用指针，因此可以实现这一点，但在Java或JavaScript中不可能，因为这些语言没有广义指针。

请注意，通过在比较指针时使用NULL而不是0可以使代码更易读：

typedef struct node node;
struct node {
    int data;
    node *next; 
};

int insert_asc(node **phead, int data) {
    node **traser;
    node *newnode = malloc(sizeof(node));
    if (newnode == NULL)
        return 0;
    newnode->data = data;

    for (traser = phead; *traser != NULL; traser = &(*traser)->next) {
        if (data <= (*traser)->data)
            break;
    }
    newnode->next = *traser;
    *traser = newnode;
    return 1;
}

请注意，给定值为data的新节点将插入到具有相同data值的节点之前。在这种情况下没有区别，并且对于具有许多重复项的列表可能会更快，但如果有效载荷更为复杂，则此插入方法将实现非稳定排序，而使用< 而不是<=将使排序稳定。

以下是另一种实现的示例，该实现不使用双指针作为插入点并且需要额外的测试用于特殊情况：

int insert_asc(node **phead, int data) {
    node *cur;
    node *newnode = malloc(sizeof(node));
    if (newnode == NULL)
        return 0;
    newnode->data = data;

    cur = *phead;
    if (cur == NULL || cur->next == NULL) {
       newnode->next = cur;
       *phead = newnode;
    } else {
        while (cur->next != NULL && data < cur->next->data)
            cur = cur->next;
        newnode->next = cur->next;
        cur->next = newnode;
    }
    return 1;
}

- chqrlie