Ben Pfaff wrote:

> Chad <(E-Mail Removed)> writes:

>

>> On page 145 in second edition of the book "The C Programming

>> Language" by K &R, they have the following lines of code in

>> install()

>>

>> hash->next = hastab[hashval];

>> hashtab[hashval] = np;

>>

>> I'm assuming that this is meant to insert NULL at the end of

>> the linked list. If that is the case, I am not seeing how NULL

>> is actually getting put at the end of the linked list.

>

> This code inserts np at the *front* of the linked list. NULL

> is already at the end of the linked list, so there's no need to

> add it.
The point of this sort of list formation is that the total work may

be much less. Even if the end result desired is a list in the

order inserted, the total work is:

a list reversal O(n) with small constants

n insertions O(1) with small constants

for a net of O(n) performance. However if each value is inserted

at the end, for i = 0 through n, the insertions require:

n insertions O(i) with larger constants.

and the work is of the form K(1 + 2 + 3 ... + n), which is easily

seen to be larger.

--

Chuck F (cbfalconer at maineline dot net)

Available for consulting/temporary embedded and systems.

<http://cbfalconer.home.att.net>

--

Posted via a free Usenet account from

http://www.teranews.com