«

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.

Chad <> 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.
--
"A lesson for us all: Even in trivia there are traps."
--Eric Sosman

Ben Pfaff wrote:
> Chad <> 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