Nested shared_ptr destruction causes stack overflow

Question

This is a more of design problem (I know why this is happening, just want to see how people deal with it). Suppose I have a simple linked list struct:

struct List {
    int head;
    std::shared_ptr<List> tail;
};

The shared_ptr enables sharing of sublists between multiple lists. However, when the list gets very long, a stack overflow might happen in its destructor (caused by recursive releases of shared_ptrs). I've tried using an explicit stack, but that gets very tricky since a tail can be owned by multiple lists. How can I design my List to avoid this problem?

UPDATE: To clarify, I'm not reinventing the wheel (std::forward_list). The List above is only a simplified version of the real data structure. The real data structure is a directed acyclic graph, which if you think about it is just a lot of of linked lists with shared tails/heads. It's usually prohibitively expensive to copy the graph, so data sharing is necessary.

UPDATE 2: I'm thinking about explicitly traversing down the pointer chain and std::move as I go. Something like:

~List()
{
    auto p = std::move(tail);
    while (p->tail != nullptr && p->tail.use_count() == 1) {
        // Some other thread may start pointing to `p->tail`
        // and increases its use count before the next line
        p = std::move(p->tail);
    }
}

This seems to work in a single thread, but I'm worried about thread safety.

Answer 1

If you're having problems with stack overflows on destruction for your linked datastructure, the easiest fix is just to implement deferred cleanup:

struct Graph {
    std::shared_ptr<Graph>  p1, p2, p3;   // some pointers in your datastructure
    static std::list<std::shared_ptr<Graph>>   deferred_cleanup;

    ~Graph() {
        deferred_cleanup.emplace_back(std::move(p1));
        deferred_cleanup.emplace_back(std::move(p2));
        deferred_cleanup.emplace_back(std::move(p3));
    }
    static void cleanup() {
        while (!deferred_cleanup.empty()) {
            std::list<std::shared_ptr<Graph>>  tmp;
            std::swap(tmp, deferred_cleanup);
            tmp.clear(); } }
};

and you just need to remember to call Graph::cleanup(); periodically.