CODEWITHSUNDEEP
calgorithmlinked-list
John Roberts
John Roberts

Reputation: 5986

Linked List Flattening Algorithm Pointers

I am looking at the following algorithm to flatten a tree-like linked list system from the book "Programming Interviews Exposed":

void flattenList( Node *head, Node **tail)
    Node *curNode =  head;
    while( curNode ){
        /* The current node has a child */
        if( curNode->child ){
            append( curNode->child, tail );
        }
        curNode = curNode->next;
    }
}

/* Appends the child list to the end of the tail and updates
 * the tail.
 */
void append( Node *child, Node **tail ){
    Node *curNode;

    /* Append the child child list to the end */
    (*tail)->next = child;
    child->prev = *tail;

    /*Find the new tail, which is the end of the child child
     *list.
     */
    for( curNode = child; curNode->next;
         curNode = curNode->next )
        ; /* Body intentionally empty */

    /* Update the tail pointer now that curNode is the new
     * tail.
     */
    *tail = curNode;
}

I understand that we are passing **tail instead of *tail into the append function to make sure that changes to *tail persist, but what I don't understand is why we don't do the same for child (meaning why don't we pass **child instead of *child)?

Upvotes: 2

Views: 317

Answers (4)

user4240723
user4240723

Reputation: 11

struct node *flatten_nr(struct node *root)
{  


    struct node *temp1, *temp2;

    if (NULL == root) return NULL;
    temp2 = root;
    while (root != NULL)
    {
        if( root->next != NULL)
        {
            temp1 = root;
            /* go to the end of the list and append */
            while (temp1->down != NULL)
            {
                temp1 = temp1->down;
            }
            temp1->down = root->next;
        }
        root = root->down;
    }
    return temp2;
}

Upvotes: 0

WhozCraig
WhozCraig

Reputation: 66244

To immediately answer your question. the child members of a Node are never updated. They're only used to walk the underlying child list.

And honestly, the choice of parameter names (child) could not have been more dreadful (short of calling it parent or some such). See if the following is any clearer at all. It exploits the fact that C is a byval-call system, and actually uses one of the parameters (the node pointer) to find the end of a list starting at a given node without any temp pointer (we use the node pointer itself for the walk, since it is byval):

void append( Node *node, Node **tail )
{
    /* Append the child child list to the end */
    (*tail)->next = node;
    node->prev = *tail;

    /*Find the new tail, which is the end of the child child
     *list.
     */
    while (node->next)
        node = node->next;

    /* Update the tail pointer now that curNode is the new
     * tail.
     */
    *tail = node;
}

I should node, this is not very good code anyway. it makes no checks against NULL for any of the parameters, etc. This should be significantly hardened. I chose to forego the error checking and non-null validation only because the original code left all that out as well. If you desire a significantly more robust version let me know.

Upvotes: 1

Henry
Henry

Reputation: 43788

C uses a "call by value" parameter passing semantics. This means, if you call a function like f(x), only the value of x is passed to the function, not the variable x itself. When you assign a value to the parameter inside the function the x used to call the function does not change.

If you want to be able to change the variable itself, you must pass the address like in this call f(&x) if you then make an assignment to *x inside the function you have changed the variable x.

The flattenList is declared as it is because head is passed by value (it does not change) but tail is passed with its address because the function has to change it.

This is similar to the append function. The first parameter does not change while the second one must be changed inside the function.

Upvotes: 1

Bart van Ingen Schenau
Bart van Ingen Schenau

Reputation: 15768

The comments in append state it quite clearly

/* Update the tail pointer now that curNode is the new
 * tail.
 */
*tail = curNode;

Because you are updating the tail pointer itself (and not just the node it refers to), you need to pass pointer to a pointer in order for the update to be visible outside the function.

For the child pointer, we are only updating the node it refers to, not the pointer itself. Thus there is no reason to complicate the code any further by adding another level of indirection.

Upvotes: 0

Related Questions