CODEWITHSUNDEEP
c++linked-listsingly-linked-listdouble-pointer
Sarthak Bansal
Sarthak Bansal

Reputation: 65

Inserting a Node in a linked list using double pointers

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

Upvotes: 0

Views: 2156

Answers (2)

user4842163
user4842163

Reputation:

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.

Upvotes: 2

Iverelo
Iverelo

Reputation: 146

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

Upvotes: 1

Related Questions