linked lists and free()

Discussion in 'C Programming' started by Hans Vlems, Aug 30, 2013.

  1. Hans Vlems

    Eric Sosman Guest

    That's surprising. I reasoned: "If the head isn't freed until
    after the tail, then the head-releaser does additional work after
    the tail-releaser returns, so tail-call optimization doesn't apply."
    But perhaps (or "likely") I've overlooked a clever rearrangement.
    Would you be willing to share your code?
    It seemed to me that the O.P.'s goal was not to free the nodes
    in a specified order, but simply to free all the nodes. (He started
    by asking whether `free(head)' would release the whole list.) From
    his outline, I imagined something along the lines of

    void freeList(struct node *head) {
    if (head != NULL) {
    freeList(head->link);
    free(head);
    }
    }

    .... and I wanted to point out a cheaper alternative.
     
    Eric Sosman, Sep 2, 2013
    #21
    1. Advertisements

  2. Hans Vlems

    James Kuyper Guest

    Why did you bother to quot the attribution lines, the sig, and a bunch
    of blank lines - without bothering to quote any of that actual text of
    the message you're responding to. I had to go back to Eric's message to
    confirm which comments you're referring to.
    The thing is, not only does freeing the list in head-to-tail order
    execute faster, the code for doing so is also slightly simpler and
    easier to understand. If there were any significant advantage to doing
    the freeing recursively, your comments would be reasonable - but there
    is none.
     
    James Kuyper, Sep 2, 2013
    #22
    1. Advertisements

  3. Well, I am tempted to bluff, but I'll come clean. In my eagerness to
    get a tail call, I forgot we were talking about a reverse-order freeing!

    However, it obviously *is* possible if one is prepared to write ghastly
    code, so I took another run at it to get

    void free_rev(node *np, node *prev, int up)
    {
    if (np) {
    node *next = np->next;
    if (up)
    free(np);
    else np->next = prev;
    free_rev(next, np, up);
    }
    else if (!up)
    free_rev(prev, 0, 1);
    }

    which is horrid by any standards but it does do as I said (and gcc
    obliges by eliminating the tail calls).
    Yes, we are in danger of going off the rails. There's a simple,
    forward, linear time, constant space way to free a linked-list, and
    anything else is as brain fluff.
     
    Ben Bacarisse, Sep 2, 2013
    #23
  4. Hans Vlems

    Tim Rentsch Guest

    Sort of a combination of in-place reversal and forward freeing.
    Much easier of course with a helper function

    void
    reverse_order_free( node *np ){
    forward_order_free( reverse_onto( np, 0 ) );
    }

    with both subfunctions being constant-stack-space tail recursive
    (and reverse_onto() returns the head of the newly reversed list).

    If one is determined to have a single function, it might be
    written this way:

    void
    last_to_first_free( node *n, node *p ){
    if( n ){
    node *x = n->next;
    if( n != p ) n->next = p, last_to_first_free( x, n );
    else free( n ), last_to_first_free( x, x );
    } else if( p ){
    last_to_first_free( p, p );
    }
    }

    taking advantage of the circumstance on the "freeing" pass that
    no backpointer is needed. (I make no claim that this writing is
    any more or less horrid than the free_rev() one.) This version
    is also tail-call-optimized by gcc, as one would expect since
    it follows the same basic approach as free_rev().

    Incidentally, free_rev() has a mild case of undefined behavior.
     
    Tim Rentsch, Sep 2, 2013
    #24
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.