Basic Linked List Question

[INeedAHero]

Let's say you have a delete function.

Should you delete the node itself, or just the information in the node?

To me, it would make more sense to delete the node itself, but my notes say otherwise...I think I just copied it down wrong.

Thanks in advance.

[Zaita]

Delete the node.

[AngryHopeCat]

Yes, if you have a pointer called 'cur' pointing towards the node you want to delete, and a pointer called 'prev' pointing towards the node before the node you want to delete, the code would look something like this:

prev->next = cur->next; // make the previous node point to the next node
delete cur; // delete the node
cur = prev->next; // adjust your cur to point to the the next node 

[INeedAHero]

Thanks for the help!

Another quick question.

Suppose I have a doubly linked list (so each node has a next AND a prev pointer)....would it still be wise to maintain the prev pointer, along with the curr pointer?

Or would it be more efficient to just use the curr pointer, since the list is now doubly linked?

I'm interested in the most efficient option.

[AbstractionAnon]

When deleting a node from a doubly linked list, you have to update both the previous node's forward pointer and the next node's previous pointer, keeping in mind that you could be deleting either the first node in the list, or the last node in the list.

If you look at std::list.erase() as a model, it returns an iterator to the next element, or to end().