One last question on hashes

[Chad]

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.

 

[Ben Pfaff]

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.

 

[CBFalconer]

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.