List unflattening

yamaryl · March 16th, 2016, 11:45 AM

There is this old thread in the forum dedicated to the second edition :

List Unflattening

This section of the book apparently is still exactly the same in the third edition. I believe this part should be overhauled in the next edition.

More specifically, I think

- it is worth discussing that there is no algorithm able to unflatten any lists, independently of how those lists were flattened. The unflattening algorithm is specific to the flattening algorithm (at least I believe so)

- at first, it's unclear which flattened list organisation the author attempts to unflatten...

- and finally, it is unclear why the author overlooked the easiest unflattening algorithm :

Code:

void unflatten(Node** head, Node** tail)
{
    if (!(*tail)) return;
    Node* track = *tail;
    while (track)
    {
        if (track->child)
        {
            *tail = track->child->prev;
            track->child->prev = NULL;
            (*tail)->next = NULL;
        }
        track = track->prev;
    }
}