Is this the best way to utilise tail call recursion traversing a linked list?

Basically I am creating a base class that will be used for classes stored as a linked list, which are traversed and deleted as dictated by a virtual update() function which returns a bool.

I am wondering if this is the most efficient case (I like the fact that it can be a singley linked list in particular):

class Traversable
{
    public:
        Traversable();
        virtual ~Tr开发者_运维知识库aversable();
        void traverse(Traversable** prevNext);
        virtual bool update()=0;
    protected:
    private:
        Traversable* next;
};


void Traversable::traverse(Traversable** prevNext)
{
    if (!update()) /// Virtual function that returns a death flag
    { /// Death
        if (next)
        {
            Traversable* localNext = next;
            delete this;
            localNext->traverse(prevNext);
        }
        else
        {
            *prevNext = NULL;
            delete this;
        }
    }
    else
    { /// This node stays alive, for now
        *prevNext = this;
        if (next)
        {
            next->traverse(&next);
        }
    }
}

Note the linked list is NULL terminated.

I think the careful lack of an assigment operation to a local variable after the next traverse function is called will secure usage of this function using tail calls. Can anyone spot anything I have done wrong, or perhaps suggest a slightly less convoluted approach :p

You're deliberately obfuscating the code in order to "tempt" the compiler into creating a specific result; whether this happens or not is quite probably more dependent on the compiler used, the optimization flags in effect, or even the code compiled that's using the above. The following is more compact code:

void Traversable::traverse(Traversable** prevNext)
{
    bool doUpdate = update();

    *prevNext = doUpdate ? this : next ? *prevNext : NULL;

    Traversable **argNext = doUpdate ? &next : prevNext;
    Traversable *localNext = next;

    do_the_traversal_action();     // not spec'ed ...

    if (!doUpdate)
        delete this;
    if (localNext)
        localNext->traverse(argNext);
}

and still ends the function with a single tail return point. The only reason this uses conditionals is because you're changing prevNext in there.

Edit: what I'm trying to say is that no matter how you code it, in the end it's up to the compiler to decide whether it wants to tail-optimize the function or not. For modern optimizing compilers, there's often switches (-fconserve-stack or -foptimize-sibling-calls in GCC) that have a more immediate effect on this more than the sourcecode itself.

Edit 2: yes if course it's possible to write this function non-recursively; all it is, in the end, is a visitor type pattern. So the actual activity ends up being something like:

static void Traversable::traverse(Traversable *start)
{
    Traversable *cur, *next;

    for (cur = start; cur; cur = next) {
        next = cur->next;

        cur->do_the_traversal_action();     // not spec'ed ...

        if (cur->update())
            continue;                       // not supposed to remove this

        if (next)
            next->prevNext = cur->prevNext; // remove cur from list
        delete cur;
    }
}

Though, when you code it like that, the next obvious question is why one would not implement simple iterator types for Traversable and use std::remove_copy_if() for the visit-and-remove-on-condition task. Or use an STL list to start with.