linked lists and free()

[Eric Sosman]

[... ghastly double-spacing fixed ...]
Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:
On 8/30/2013 5:06 AM, Hans Vlems wrote:
[...]
Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}
[...]

That's a classic tradeoff, right . The algorithm is either
head-to-tail, as you do and you need to declare temporary storage or
recursively, in which case the no additional declaration is needed at
the expense of a growing stack. In both cases memory is used.

Yes, memory is used -- but how much? For a list of N nodes,
last-to-first uses memory proportional to N to keep track of its
recursion[*], while first-to-last uses the same constant amount
of memory (two pointers' worth) no matter how long the list is.

I don't think you can say that without qualification, even in the
context of C. gcc can do tail-call optimisation and I've just checked
that I can write a recursive reverse-order freeing function that uses
constant extra space.

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?

[*] A different last-to-first algorithm also uses constant
memory, but running time proportional to the *square* of N.

And yet another (very similar to the code you'd write to reverse a list
in-place) has linear running time and uses constant space. You've be
within your rights to call this a front-to back freeing of a reversed
list (slightly optimised), but it does free the nodes in reverse order.
Another way to look at it is that since a C linked-list can be reversed
in place in linear time with constant storage, there's no significant
difference between freeing the nodes in either order.

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.

 

[James Kuyper]

Op vrijdag 30 augustus 2013 18:00:55 UTC+2 schreef Eric Sosman:

[snip]



--

Eric Sosman

(e-mail address removed)

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.

Eric, thank you for your comments. I must admit that the overhead possibly incurred by malloc() never even crossed my mind. The program is interactive, the user must select input files and select one option on how to manipulate them.
All I cared for were fast response times... And even in the case where 149000 records are loaded, 48 fileds per record doesn't seem to slow down the system.
That is the advantage of systems with cpu's that run in GHz's and memory available in GB's.
Using "classical" programming techniques properly, the underlying processing system is hardly worth considering. Not like it was on a PDP 11/40 with 32 kB memory or a B7700 with "just" three processors and 1 MW main storage. Recursion with little overhead runs real fast on modern Intel gear!
Hans

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.

 

[Ben Bacarisse]

On 9/2/2013 2:47 AM, Hans Vlems wrote:
[... ghastly double-spacing fixed ...]
Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:
On 8/30/2013 5:06 AM, Hans Vlems wrote:
[...]
Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}
[...]

That's a classic tradeoff, right . The algorithm is either
head-to-tail, as you do and you need to declare temporary storage or
recursively, in which case the no additional declaration is needed at
the expense of a growing stack. In both cases memory is used.

Yes, memory is used -- but how much? For a list of N nodes,
last-to-first uses memory proportional to N to keep track of its
recursion[*], while first-to-last uses the same constant amount
of memory (two pointers' worth) no matter how long the list is.

I don't think you can say that without qualification, even in the
context of C. gcc can do tail-call optimisation and I've just checked
that I can write a recursive reverse-order freeing function that uses
constant extra space.

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?

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).

[*] A different last-to-first algorithm also uses constant
memory, but running time proportional to the *square* of N.

And yet another (very similar to the code you'd write to reverse a list
in-place) has linear running time and uses constant space. You've be
within your rights to call this a front-to back freeing of a reversed
list (slightly optimised), but it does free the nodes in reverse order.
Another way to look at it is that since a C linked-list can be reversed
in place in linear time with constant storage, there's no significant
difference between freeing the nodes in either order.

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.

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.

 

[Tim Rentsch]

On 9/2/2013 2:47 AM, Hans Vlems wrote:
[... ghastly double-spacing fixed ...]
Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:
On 8/30/2013 5:06 AM, Hans Vlems wrote:
[...]
Freeing the nodes last-to-first is probably not the best way,
especially if (as you suggest) the list may be long. First-to-last
is usually better, if you'll exercise just a tiny bit of care:

void freeList(struct node *head) {
while (head != NULL) {
struct node *next = head->link;
free(head);
head = next;
}
}
[...]

That's a classic tradeoff, right . The algorithm is either
head-to-tail, as you do and you need to declare temporary storage or
recursively, in which case the no additional declaration is needed at
the expense of a growing stack. In both cases memory is used.

Yes, memory is used -- but how much? For a list of N nodes,
last-to-first uses memory proportional to N to keep track of its
recursion[*], while first-to-last uses the same constant amount
of memory (two pointers' worth) no matter how long the list is.

I don't think you can say that without qualification, even in the
context of C. gcc can do tail-call optimisation and I've just checked
that I can write a recursive reverse-order freeing function that uses
constant extra space.

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?

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).

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.