How big can the stack call before this code causes problems?

Question

I optimized the linked list destructor as follows:

template <class T> class LinkedList { /* snip */ T* pData; LinkedList* pNext; }; template <class T> LinkedList<T>::~LinkedList() { delete pData; delete pNext; } 

Now I'm a little worried that this may cause problems with large lists. Can this code cause a stack overflow? If so, how many large lists?

Answer 1

The stack size is determined by a number of factors, such as the OS / compiler / configuration parameters in the system.

I would definitely not use a recursive method to delete items in a list, since you can overflow the stack - you can try this by creating a list with X elements, and if that works, double X until you reach the stack overflow - I almost guarantee that this occurs in several thousand elements (perhaps 10-100 thousand, but, of course, not much more).

Recursive functions to remove binary trees, etc. much more acceptable because (subject to a reasonable balance) the number of recursive levels is log2(n) , not n , so you can have a huge number of elements in front of the stack overflowing.

I took your class and extended it to make it work (this probably doesn't look like how you use it, but it does the task of explaining the problem):

 #include <iostream> using namespace std; template <class T> class LinkedList { public: LinkedList() : pNext(0), pData(0) {}; LinkedList(T e) : pNext(0) { pData = new T(e); } LinkedList(LinkedList* l, T e) : LinkedList(e) { pNext = l;} LinkedList *AppendFirst(LinkedList *l) { l->pNext = this ; return l; } LinkedList *Next() { return pNext; } T Data() { return *pData; } ~LinkedList(); private: T* pData; LinkedList* pNext; }; #if 0 template <class T> LinkedList<T>::~LinkedList() { delete pData; delete pNext; }; #else template <class T> LinkedList<T>::~LinkedList() { LinkedList<T>* p; LinkedList<T>* q; p = pNext; while(p) { q = p->pNext; // Save next link. p->pNext = NULL; // Break the link. delete p->pData; p->pData = NULL; delete p; p = q; } delete pData; }; #endif typedef LinkedList<int> IntList; int main() { for(int x = 0; x < 30; x++) { cout << "Trying " << (1 << x) << " elements" << endl; IntList *head = new IntList(-1); for(int i = 0; i < (1 << x); i++) { head = head->AppendFirst(new IntList(i)); } cout << "Now destroying " << (1 << x) << " elements" << endl; delete head; } } 

If I change #if 0 to #if 1 (or something else with this effect), it works for 128K elements and fails at 256K. If I use the iterative method in #else , I had to stop it when it got to 268435456 (256M records), because there was not enough memory on my computer, and I started to change a lot (I only have 16 GB of RAM, and it doesn't just do it).