CODEWITHSUNDEEP
c++pointersrecursionmemory-managementlinked-list
theEpsilon
theEpsilon

Reputation: 1919

Would deleting a Linked List recursively cause a stack overflow?

I have a linked list build out of Node objects:

class Node {
   public:
      Node(string data);
      Node* GetNext() const;
      void SetNext(Node* nextNode);
      ~Node();
   private:
      string data;
      Node* next;
};

The destructor is defined below:

Node::~Node() {
   delete next;
}

Where the destructor should be called on the head Node.

My question is this: would deleting the singly-linked list like this cause a Stack Overflow on large lists (it works fine on small i.e., < 10 size lists). If it does, would it be better to use an iterative solution, like

while (head->GetNext() != 0) {
   Node* temp = head->GetNext();
   head->SetNext(temp->GetNext());
   delete temp;
}
delete head;

where there is no defined constructor for Node?

Upvotes: 0

Views: 136

Answers (2)

πάντα ῥεῖ
πάντα ῥεῖ

Reputation: 1

The stack size always limits the depth of recursive calls on a function. Even with the destructor (and other functions without a parameter) it's necessary to keep the return address of that function call (the destructor would get the this pointer as implicit parameter anyways).

So from a certain upper limit of Nodes the stack will overflow, yes.

The iterative way is much more robust regarding this.

Upvotes: 4

jwir3
jwir3

Reputation: 6209

The problem with your solution is that the stack frames are continuously building up on the stacks, for each call to the ~Node() method. Take an example of 3 Node objects, starting at, say 0x01. Deletion of these has the following stack frame backtrace (I assume each Node object contains 1 bit of information, which isn't true, but it makes the list a bit neater):

 (0) Node (0x01): ~Node
 (1) Node (0x02): ~Node
 (2) Node (0x03): ~Node

So, for a million Node objects, you will have a million stack frames before the first one even completes. Each stack frame takes up space on the stack, so, yes, you could run out of stack space.

The iterative solution doesn't suffer from this problem, because, for each iteration, the call to delete a Node completes before the next Node deletion routine runs. This means that you have a single function call on the stack during each iteration (plus or minus the amount you need to complete that function call, but in particular, it's not recursive).

In addition to that problem, there's another problem that's been raised, and that is that you don't have any way of deleting just a single Node object. You can either delete the whole list or part of the list. Imagine what would happen if a client had a reference to Node (0x02) in the previous example, and called delete node. In this case, Node (0x02) and Node (0x03) would be deleted, but Node (0x01) would _still have a reference to the pointer to the memory for Node (0x02). Dereferencing this would cause a crash.

Upvotes: 4

Related Questions