CODEWITHSUNDEEP
c++linked-list
GeorgeTs
GeorgeTs

Reputation: 63

Is p->next->prev the same as p?

I am doing a Linked List implementation for my Uni, and i came across this code on our presentations.

template <class X> bool linkedList<X>::deleteElement(node<X> *p)
if (p=NULL)
    return false;
if(p->next!=NULL)
    p->next->prev = p->prev;
if(p->prev!=NULL)
    p->prev->next = p->next;
else
    head = p->next

I was wondering if the p->next->prev = p->prev; part is the same as saying p = p->prev; because the previous of the next of p, is p itself.

Thanks in advance for any answers.

EDIT 1: Fixed a typo and added a bit more code to make this more clear.

Upvotes: 6

Views: 5693

Answers (2)

Remy Lebeau
Remy Lebeau

Reputation: 596352

I was wondering if the p->next->prev = p->prev; part is the same as saying p = p->prev

No, it is not. It is setting the prev field of the next node that follows the p node in the list.

The code is removing the p node from the list. The two surrounding nodes on either side of the p node need to be updated to stop pointing at the p node and instead point at each other. What you showed is only half of the necessary update. You need to add the other half: if (p->prev != NULL) p->prev->next = p->next;. You also need to check if p points at the head node of the list, and if so then update the head to point at p->next instead. Likewise with the list's tail node, if any, to point at p->prev.

Also, the if(p=NULL) in your code is wrong, it should be if(p==NULL) instead. And the if(p->next==NULL) in your code is also wrong, it should be if(p->next!=NULL) instead.

Here is the correct implementation:

template <class X> bool linkedList<X>::deleteElement(node<X> *p)
{
    if (p == NULL)
        return false;
    if (p->next != NULL)
        p->next->prev = p->prev;
    if (p->prev != NULL)
        p->prev->next = p->next;
    if (p == head)
        head = p->next;

    // if your list has a tail:
    if (p == tail)
        tail = p->prev;

    // if your list owns the memory for the nodes:
    delete p; // or however you free it

    return true;
}

And lastly, you should consider using the STL std::list container instead of a manual implementation.

Upvotes: 8

Claudiu
Claudiu

Reputation: 229361

Not quite. p is a local variable. p->next->prev is an instance variable on p->next. Changing the former won't affect the structure at all, while changing the latter will. To put it another way, their values may be the same, but the memory addresses where those values are stored are different.

Upvotes: 9

Related Questions