CODEWITHSUNDEEP
c++visual-c++linked-list
Evil Washing Machine
Evil Washing Machine

Reputation: 1341

Removing a node from a linked list in c++

I'm trying to learn C++ and there is a small confusion I have.

The text which I am learning from tells me that if I want to delete a node of type const T& I should first create a new pointer of that node type, then delete it using the inbuilt C++ delete[]. However, what happens if I just set the link from the to-be-deleted node's previous element to the to-be-deleted node's next element? Something like:

*p = node.previous;
p-> next = node.next;

Or will this cause a memory leak?

I'm confused because I read somewhere else to never, ever delete pointers willy-nilly, but the example code I am working with has something along the lines of:

Node<T> *p = node-to-be-deleted;
delete p;

What is the best way to delete the node?

Upvotes: 1

Views: 1772

Answers (4)

Loki Astari
Loki Astari

Reputation: 264351

Assuming your node looks like this:

struct Node
{
    Node*  previous;
    Node*  next;

    SomeType data;
};

Then:

*p = node.previous;
p-> next = node.next;

Then YES. This will cause a memory leak.
It also leaves p->next->prev pointing at the wrong node.

I'm confused because I read somewhere else to never, ever delete pointers willy-nilly, but the example code I am working with has something along the lines of:

Yes the best way is to "never delete pointers". But this has to go along with some context. You should not be deleting pointers manually because pointers should be managed by an objects that control their lifespan. The simplest of these objects are smart pointers or containers. But for this situation that would be overkill (as you are creating the container).

As you are creating the container (a list) you will need to do the management yourself (Note C++ already has a couple of lost types std::list for a list of values of type t or boost::ptr_list for a list of pointers to T). But it is a good exercise to try and do it yourself.

Here is an example on code review of a beginner making a list and the comments it generated:

http://codereview.stackexchange.com: Linked list in C++

I hope this helps in explains on how to create and delete objects.

Upvotes: 2

soniccool
soniccool

Reputation: 6058

void deleteNode( Node * p )
{
    Node * temp = p->next;
    p->data = p->next->data;
    p->next = temp->next;
    free(temp);
}

Heres something i did a few months ago.

template <class T>
T LinkedList<T>::remove(int pos)
{
    if (pos < 1 || pos > size)
    {
        throw pos;
    }
    ListNode * temp;
    if (pos == 1)
    {
        temp=head;
        head = head->next;
    }
    else
    {
        int i=1;
        ListNode * prev = head;

        while(i<pos-1)
        {
            i++;
            prev=prev->next;
        }
        temp = prev->next;

        prev->next = (prev->next)->next;

    }
    --size;
    return temp->item;
}

Upvotes: 0

Remy Lebeau
Remy Lebeau

Reputation: 595557

Deleting a Node directly only makes sense if Node implements a destructor to update the previous and next pointers of the surrounding Node instances, eg:

Node::~Node()
{
    if (previous) previous->next = next;
    if (next) next->previous = previous;
}

Node *p = node-to-be-deleted;
delete p;

Otherwise, you have to update the Node pointers before then deleting the Node in question, eg:

Node *p = node-to-be-deleted;
if (p->previous) p->previous->next = p->next;
if (p->next) p->next->previous = p->previous;
delete p;

With that said, the best approach is to no implement a linked list manually to begin with. In C++, use a std::list container instead, and let it handle these details for you.

Upvotes: 0

gustaf r
gustaf r

Reputation: 1234

Node* p = new Node; // This is how you allocate a node
delete p; // This is how you delete it

The delete[] operator should be used on dynamically allocated arrays:

Node* nodelist = new Node[ 4 ]; // nodelist is now a (dynamically allocated) array with 4 items.
delete[] nodelist; // Will delete all 4 elements (which is actually just one chunk of memory)

Upvotes: 1

Related Questions