In a linked list, in what order are nodes removed by the destructor?

Question

In a linked list, in what order are nodes removed by the destructor?

Does it go first to last or last to first?

Answer 1

Either order is possible -- the only way to be certain is to inspect the specific implementation you're using.

In general, for a singly-linked list, I would expect a first-to-last ordering because it's easier to implement and a bit more efficient:

LinkedList::~LinkedList()
{
    Node *node = mHead;
    while (node) {
        Node *next = node->mNext;
        delete node;
        node = next;
    }
}

Versus a last-to-first ordering, which for a singly-linked list will generally require some sort of recursion:

void deleteList(Node *node)
{
    if (node == 0) {
       return;
    }
    deleteList(node->mNext);
    delete node;
    return;
}
LinkedList::~LinkedList()
{
   deleteList(mHead);
}

So again -- the only way to be sure is to look at your linked list implementation.

Answer 2

I imagine that since the compiler reads code. From up to down the destructor deletes from first to last. you can even use { }| to ensure the re allocation of memory before it will usually happen.