Shared pointers delete recursive data structures recursively and the stack overflows

Question

I have a number of long linked lists (they have up to 20,000 items). They have different beginnings but they can eventually point to the same node from some node onwards. I've decided to let such linked list to grow together and share the memory between them.

That is why I ve decided to implement linked list with shared pointers:

#include <memory>
struct SharedLinkedList {
    int someData;
    std::shared_ptr<SharedLinkedList> next;
};

This way everything works fine. The linked lists which are no longer needed are deleted. If they share some part with other linked list only their un-shared part is deleted.

The problem apears when longer linked lists without shared parts are about to be deleted. Deleting starts with the first element. This decreases the number of references to the next element which can be also deleted and this repeats recursively until the stack overflows.

Here is the example of code which creates long linked list and then fails deleting it.

SharedLinkedList* beginningOfList;
SharedLinkedList* actualElement = new SharedLinkedList();
SharedLinkedList* nextElement;

beginningOfList = actualElement;
for (int i = 0; i < 1000; i++) { // 100 is OK, 1000 is KO
    nextElement = new SharedLinkedList();
    actualElement->next = std::shared_ptr<SharedLinkedList>(nextElement);
    actualElement = nextElement;
}
delete beginningOfList;

I thank in advance for either of the following:

1. Explanation of shared_pointers and of what am I missing. How can I use them? And can it even be done using them? Isn't such sharing of memory the thing for which were the share pointers invented?
2. advice how to reimplement my code
3. This code will be used for scientific computations which will be run on my computer. Can I tweak somehow something in order to have bigger size of stack?

Note that this question is not c++11 specific. I don't care which implementation of shared pointes is used. I even implemented my own shared pointers. This allowed me to have a little longer linked lists but the recursion in destructors and stack overflowing also appeared. And I don't see any way how could be shared pointers implemented without recursion in destructors.

EDIT:

Just to aviod confusions: I want to repeat that the whole lists can be shared. So one could call them trees.

Here is the example:

list1 contains: 1,2,3,4,5,6,7.

list2 contains: 6,6,6,1,2,3,4,5,6,7

list3 contains: 10,11,12,1,2,3,4,5,6,7

I want to represent this in 3 SharedLinkedList which do not waste momory by storing 1,2,3,4,5,6,7 several times but they point to the same place. That is why reference counting is needed.

delete list3; is supposed to delete only the part which is not shared i.e. elements 10,11,12.

Answer 1

If you use shared_ptr it will manage ownership for you. When reference count goes to 0 it will call the destructor of the pointee. Now the pointed to object gets destructed and as an element of it the next shared pointer which destructs the next ... . This results in a recursive way of deallocating memory. Now you could try to deallocate the memory iterative. You only have to keep a reference to next element to avoid its destruction and delete it manually later:

void destroy(SharedLinkedList* l) {
  auto next=l->next;  // take 2nd element 
  delete l;           // delete first

  while (next)
    next=next->next;  // move next forward, deleting old next 
  }

Answer 2

In general, shared_ptr is probably not a good idea for linked lists, for the reason you point out. In this case, you probably have to do it by hand, maintaining a parent count in each node. (It's probably possible to work out some sort of loop which avoids the stack overflow with shared_ptr, but the results would probably be more complex than managing the memory by hand.)