使用双指针在链表中插入一个节点

Question

最近看到一个用双指针删除单链表节点的实现。除了使代码更美观之外，此实现在效率方面有任何好处。此外，我如何实现类似的方法来将节点插入链表（不跟踪先前的节点）。我真的很好奇是否有更好的算法可以实现这个

Node* Delete(Node *head, int value)
{
    Node **pp = &head; /* pointer to a pointer */
    Node *entry = head;
    while (entry ) 
    {
        if (entry->value == value)
        {
            *pp = entry->next;
        }
        pp = &entry->next;
        entry = entry->next;
    }
    return head;
}

Answer 1

Other than making the code more beautiful does this implementation have any benefits efficiency wise.

没有什么可以将它与很难说的进行比较，但这与从链表中删除节点一样有效。请注意，函数名称 Delete 与 Remove 更准确，因为它实际上并不清理它从列表中删除的节点。

Also how can I implement a similar approach towards inserting a node to a linked list ( without keeping track of previous Node ).

一种方法是向前看。最好在遵循删除函数格式的示例中显示。

void insert(Node *head, int value)
{
    Node *entry = head;
    while (entry)
    {
        if (entry->next == NULL)
        {
            entry->next = new Node(NULL, value);
            return;
        }
        else if (value < entry->next->value)
        {
            entry->next = new Node(entry->next, value);
            return;
        }
        entry = entry->next;
    }
}

Answer 2

对于只存储头部、没有尾部的列表的后面插入（这意味着线性时间插入是可接受的小列表），您可以通过引入额外的指针间接来消除特殊情况来做到这一点:

简单版本（指向节点指针的指针）

void List::push_back(int value)
{
    // Point to the node link (pointer to pointer to node), 
    // not to the node.
    Node** link = &head;

    // While the link is not null, point to the next link.
    while (*link)
        link = &(*link)->next;

    // Set the link to the new node.
    *link = new Node(value, nullptr);
}

... 您可以将其简化为：

void List::push_back(int value)
{
    Node** link = &head;
    for (; *link; link = &(*link)->next) {}
    *link = new Node(value, nullptr);
}

相对于，说：

复杂版本（指向节点的指针）

void List::push_back(int value)
{
    if (head)
    {
        // If the list is not empty, walk to the back and
        // insert there.
        Node* node = head;
        while (node->next)
             node = node->next;
        node->next = new Node(value, nullptr);
    }
    else
    {
        // If the list is empty, set the head to the new node.
        head = new Node(value, nullptr);
    }
}

或者为了公平起见并删除评论：

void List::push_back(int value)
{
    if (head)
    {
        Node* node = head;
        for (; node->next; node = node->next) {}
        node->next = new Node(value, nullptr);
    }
    else
        head = new Node(value, nullptr);
}

简单版无特例

第一个版本不必特例空列表的主要原因是因为如果我们想象 head 为空：

Node** link = &head; // pointer to pointer to null
for (; *link; link = &(*link)->next) {}
*link = new Node(value, nullptr);

然后 for 循环条件立即为假，然后我们将新节点分配给 head。当我们使用指向指针的指针时，我们不必在循环外单独检查这种情况。

插入排序

如果你想做插入排序而不是简单地插入到后面，那么这个：

void List::insert_sorted(int value)
{
    Node** link = &head;
    for (; *link && (*link)->value < value; link = &(*link)->next) {}

    // New node will be inserted to the back of the list
    // or before the first node whose value >= 'value'.
    *link = new Node(value, *link);
}

性能

至于性能，不确定消除额外的分支会有多大区别，但它肯定会使代码更紧凑并降低其圈复杂度。 Linus 认为这种风格是 "good taste" 的原因是因为在 C 中，你经常不得不经常编写链表逻辑，因为它不是那么容易而且必然值得推广链表，因为我们没有 class 模板，例如，所以倾向于使用更小、更优雅、更不易出错的方式来编写这些东西是很方便的。再加上它表明您对指针的理解非常好。

使用双指针在链表中插入一个节点

Inserting a Node in a linked list using double pointers

c++

linked-list

double-pointer

singly-linked-list