One last question on hashes

Discussion in 'C Programming' started by Chad, Oct 26, 2007.

  1. Chad

    Chad Guest

    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, Oct 26, 2007
    #1
    1. Advertising

  2. Chad

    Ben Pfaff Guest

    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, Oct 26, 2007
    #2
    1. Advertising

  3. Chad

    CBFalconer Guest

    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
     
    CBFalconer, Oct 26, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ben Holness

    Hashes of Hashes via subs

    Ben Holness, Oct 5, 2003, in forum: Perl
    Replies:
    8
    Views:
    582
    Ben Holness
    Oct 8, 2003
  2. Steven Arnold

    using hashes as keys in hashes

    Steven Arnold, Nov 23, 2005, in forum: Ruby
    Replies:
    3
    Views:
    179
    Mauricio Fernández
    Nov 23, 2005
  3. Perl Learner

    Hashes of hashes or just one hash ?

    Perl Learner, Jun 8, 2005, in forum: Perl Misc
    Replies:
    11
    Views:
    226
  4. djacober

    Question about hashes of hashes

    djacober, Jul 24, 2005, in forum: Perl Misc
    Replies:
    10
    Views:
    199
    Ian Wilson
    Jul 25, 2005
  5. Tim O'Donovan

    Hash of hashes, of hashes, of arrays of hashes

    Tim O'Donovan, Oct 27, 2005, in forum: Perl Misc
    Replies:
    5
    Views:
    230
Loading...

Share This Page