Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!cs.umn.edu!talon.UCS.ORST.EDU!usenet!ogicse!intelhf!ichips!iwarp.intel.com!inews!hopi!bhoughto
From: bhoughto@hopi.intel.com (Blair P. Houghton)
Newsgroups: comp.lang.c
Subject: Re: Deleting linked lists.
Keywords: C,  C++.
Message-ID: <3507@inews.intel.com>
Date: 28 Mar 91 02:19:47 GMT
Article-I.D.: inews.3507
References: <2636@borg.cs.unc.edu> <2655@borg.cs.unc.edu>
Sender: news@inews.intel.com
Distribution: na
Organization: Intel Corp, Chandler, AZ
Lines: 42

In article <2655@borg.cs.unc.edu> warner@tsc.cs.unc.edu (Byron Warner) writes:
>struct list *next;
>while (ptr) { next = ptr->next; free(ptr); ptr = next; }

Quul.

>but also some one suggested recursion:
>void listfree(List *l) {
>		if (l->next != NULL)
>			listfree(l->next);
>		free(l->data);
>		free(l);
>	}

Yes, this is, in the lispest of all possible worlds, the
Way To Go, but here in this one we're constrained by time
and space.  Instead of declaring a word (`next'), you've
declared a library element (`listfree') requiring
compilation, testing, documentation, debugging, and any
number of ancillary maintenances, with the net effect that
you've quintupled the complexity of the code and saved
automatic allocation of a lousy word.

I got bit by a tightly-looping recursion just last week; it
had to operate on such a large list that it clogged the
stack frame and crowbarred me off the CPU.  It should be
obvious that in while freeing a list with elements that
consist of a few bytes each you end up jamming possibly
hundreds of bytes per element onto the stack...

BUT if you just use the temporary, you increase by
one word and it's all downhill from there; no stack
pops, no rlimits, no nothing; plus you gain dramatically
in speed, since the loop can spin with the pc, but
the recursion has to slog blocks around just to get to
the next list-element.  (No, it doesn't really, but
just pushing and popping stack-pointers is huge overhead
compared to assigning temps...)

				--Blair
				  "This did call for a
				   discussion, didn't it?"