Inserting a Node in a linked list using double pointers

Question

I recently saw an implementation of deleting a node from a single linked list using a double pointer . Other than making the code more beautiful does this implementation have any benefits efficiency wise . Also how can I implement a similar approach towards inserting a node to a linked list ( without keeping track of previous Node ). I am really curious if there is any better algorithm out there to achieve this

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

@Thomas No, please no links to code. The OP should provide a minimal reproducible example in their question. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jun 29, 2016 at 14:54

score 2 · Accepted Answer · 2018-01-17 08:53:30Z

For insertion to the back of a list storing only the head, no tail (which would imply a small list where linear-time insertion is acceptable), you can do this by introducing the extra pointer indirection to eliminate special cases:

Simple Version (Pointers to Pointers to Nodes)

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

... which you can reduce to just:

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

As opposed to, say:

Complex Version (Pointers to Nodes)

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

Or to be fair and remove comments:

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

No Special Case for Simple Version

The main reason the first version doesn't have to special case empty lists is because if we imagine head is null:

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

Then the for loop condition is immediately false and we then assign the new node to the head. We don't have to check for that case separately outside the loop when we use pointers to pointers.

Insertion Sort

If you want to do an insertion sort instead of simply inserting to the back, then this:

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

Performance

As for performance, not sure it makes much difference to eliminate the extra branch, but it definitely makes the code tighter and reduces its cyclomatic complexity. The reason Linus considers this style to be "good taste" is because in C, you often have to write linked list logic often since it's not so easy and necessarily worthwhile to generalize linked lists since we have no class templates there, e.g., so it's handy to favor a smaller, more elegant, less error-prone way to write this stuff. Plus it demonstrates that you understand pointers quite well.

Iverelo · Accepted Answer · 2016-06-30 16:30:39Z

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

Don't have anything to compare this to so hard to say but this is about as efficient as you can remove a node from a linked list. Note that the function name Delete would be more accurate as Remove since it does not actually clean up the node it removes from the list.

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

One way is to look ahead. Best shown in an example following the format of your Delete function.

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

Collectives™ on Stack Overflow

Inserting a Node in a linked list using double pointers

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related