I'm still trying to understand pointers, drawing nodes and everything but I can't seem to understand some things.

For example here is a function that should delete nodes with even values from a list

void delete_even()
{
    
    node* ptr = head;
    while (ptr)
    {
        if (ptr->data % 2 == 0)
        {
            nod* aux = ptr;
            ptr = ptr->next;
            delete aux;
        }
        else
        {
            ptr = ptr->next;
        }
    }

}

As I understand it the pointer named ptr points to head which is the first node in the linked list. 1 What my logic looks like So while ptr=!null check if the data in the head is even. It's not it's 1 so ptr = ptr->next; that means (Ok, so make ptr point to whatever ptr's next elemt is pointing to) and that makes the pointer ptr point to the second node in the list, right? 2 as such

Now that ptr is pointing to the second node and the data element is even, make a new pointer named aux and make point to the same node ptr is currently pointing at! Now make ptr point to the next node, that would be the 3rd node in the list and delete aux that contains the address of the second node;3 like this

Now that I look again it probably doesn't work because the link is broken between the first node and the 3rd node... right?

Some cool guy came and told me to use pointers to pointers as it's much easier. and helped me with this code:

void delete_even()
{
    node **p= &head;

    while (*p)
    {
        if ((*p)->data % 2 == 0)
        {
           node *nextptr=*p;

           *p=(*p)->next;
           delete nextptr;
        }
        else
        {
            p= &(*p)->next;
        }
    }
}

So as I understand it. p is pointing to the pointer named head that is pointing to the first node.4 like this.

p means look at the thing p is pointing at, in this case it should be the pointer head *p means look at the thing p is pointing at, in this, the pointer head and then look again to the thing head is pointing at, so this should be the first node, right?

I think I got that right.

Now while *p!=NULL (while the first node is pointing at anything other than NULL) Verify if the first's node data is even. It's not, it's 1. So make p (the head pointer) have the address of the second node. 5 like that Now we see that the data is 2 and it's even so we make a pointer named nextptr and we make this pointer point to the same thing *p is pointing at, which is the second node, correct? After that we look at the thing *p is pointing (the second node) and we make it move to the next node and we delete the nextptr pointer. 6 last one

On paper it looks the same to me, maybe my drawings and understanding is not right. but I'm spend days trying to make sense to it and it just doesn't... I mean the second code works fine but I just don't understand why when the logic seems the same as the first one. Anyone that knows how to explain better?

CodePudding user response：

So make p (the head pointer) have the address of the second node.

There are two problems with this statement.

First, p is not the head pointer. Rather p points to the head pointer (at this point in the process). When p changes, head is left unchanged. (On the other hand, if *p were to change, that would affect head.)

Second, the new value is not the address of the second node ((*p)->next). Rather, it is the address of the next pointer in the first node (&(*p)->next). Note the &.

So image five should look like the following:

head    p 
  |     |
  V     |
-------- ----   ------------   ------------   ------------
|       V   |   |          |   |          |   |          |
|    -------|   |   -------|   |   -------|   |   -------|
| 1  | next- -->| 2 | next- -->| 3 | next- -->| 4 | NULL |
|    -------|   |   -------|   |   -------|   |   -------|
-------------   ------------   ------------   ------------

See if you can take it from here. (You were doing well until this step, so I think you can. On the other hand, if you or someone else requests it, I am willing to explain the remaining steps.)

Commentary: a trailing pointer can be easier to understand than this pointer-to-pointer approach.

CodePudding user response：

Both implementations are actually wrong. There are several issues with them.

1. There is an edge case that is not being taken care of. It is when the first element, the one pointed by head is deleted - the head pointer needs to be updated with the next value. And obviously, this logic needs to be recursive such that it works with the new head after the previous head was deleted as well.

2. There is also logic missing to link up the last pointer over the current pointer. For that you need to maintain a last pointer and update the last->next pointer with ptr->next to keep the list connected. If the last pointer is null, you know that head needs to be updated.

3. There is also the mixing of too many decisions being made at the same time, which makes the algorithm unnecessarily complex. I like the idiom where the algorithm saves the next pointer before any action be taken. This frees up mental logic to think about what needs to be actually done with the data rather than trying to juggle the two streams at the same time in your head.

4. A minor rhetorical fix while checking for the validity of the pointer. Better check against nullptr than assuming that the null pointer is zero.

I would rewrite it like this:

void delete_even()
{
    // Initialize the iterator
    node* ptr = head;
    node* last = nullptr;

    // loop while the current pointer is not null
    while (ptr!=nullptr)
    {
        // Save the pointer to next node 
        node* next = ptr->next;

        // If the data is even, delete and reconnect everything
        if (ptr->data % 2 == 0) {

            // Delete the data
            delete ptr;

            // Reconnect the previous pointer so the list is intact
            // This is the head node
            if ( last==nullptr ) head = next;
            // There is a previous valid node
            else last->next = next;
        } else {
           // Update last to the last valid node
           last = ptr;
        }

        // Proceed to the next node
        ptr = next;
    }
}