Correct way of erasing a linked list

Suppose, I have a singly linked list and its basic building block is,

struct Node {
  Data d;
  Node *pNext;
  // methods
  ~Node();
};

The head of the linked list is stored as,

Node *m_Head; // member of some class

When, I am done with the list, I will clean it by deleting each node as,

void Erase()
{
  Node *pIter, *pTemp = m_Head;
  while((pIter = pTemp) != 0)
  {
    pTemp = pIter->pNext;
    delete pIter;
    pIter = pTemp;
  }
}

I thought, if I can simplify this. So I came up with an idea where I can clean this whole linked list with j开发者_开发问答ust a single instruction !

delete m_Head;

and destructor will look like:

Node::~Node() { delete this->pNext; }

Here my concern is, will it cause recursion (implicitly due to delete) ? If yes, then it's definitely a concern for bigger linked lists. Will compiler be able to help in any way for optimizing that ?

[Note: Not using any library facility like std::list or other.]

---

I think the question that you have to ask is, does each Node in the list own its pNext Node? If not, then it has no business deleting its pNext node in its destructor.

In most linked list implementations all the nodes are owned by the list, a node doesn't own all the nodes after it in the list. It makes more sense to keep the nodes as dumb (POD-structs) and let all of the logic reside in the list.

It's definitely a design "smell" that your node has a destructor but no copy constructor or copy assignment operator. I think this approach will cause more complexity when you come to code implementing insert, splice and erase single element functions as you will have to manually manage the pNext pointers in any case to avoid unintentional destruction of the entire tail of a list.

---

Of course: Only do this for learning purposes or when you are sure that your own List is really better for your use case

---

It depends. Possibly your compiler will detect a tail recursion and emit code that is conceptually equivalent to using a loop.

If not, then yes, it will recurse. Usually, some thousands of recursions should be possible on commodity boxes, if stack pressure is small (like in your case). However, there is no guarantee, and indeed, for really large lists, this can be a problem.

Also, I think that recursion is indeed not entirely appropriate for the concept of sibling nodes. A node hierarchy, like with quadtrees, cries for recursion, but I have a not so good time thinking in recursion (which forms a call hierarchy) when the list-concept is about sibling-nodes.

You may also consider the manual loop as a easy-to-achieve optimization over the recursion that will make your code more robust in a guaranteed way.

Btw, you could also should rip out the deletion of nodes into a holder class:

class List {
public:
    ~List() {
        for-each-node
            delete-node
    }

private:
    class Node {
        Node *node_;
        ...
    };
    ...
};

This is basically how the standard library's list is usually implemented. It makes the whole implementation easier to achieve and conceptually more correct (Nodes don't own their sibling logically)

---

Most compiler do tail call elimination in default setting. Some smarter one can convert non-tail calls to tail calls.

So, this method okay as long as you have some optimization turned on.

---

Raw pointers ? Manual calls to delete ?

Why not, simply:

struct Node {
  Data d;
  std::unique_ptr<Node> next;
};

Then you don't even have to worry about memory management at all, it's automatic!