title: Table lookup install function from k&r
body: <p>Section 6.6 of K&amp;R discusses a hash table using a linked list.</p>
  
  <p>In short, a hash table is an array of pointers.  The pointers point to a linked list.  The linked list is a struct that looks like:</p>
  
  <pre><code>struct nlist {             /* table entry: */
      struct nlist *next;    /* next entry in chain */
      char *name;            /* defined name */
      char *defn;            /* replacement text */
  };
  </code></pre>
  
  <p>The name is hashed, and this hash determines the index in the table.  The chapter then shows code to add a name/defn pair to the table:</p>
  
  <pre><code>struct nlist *install(char *name, char *defn) {
      struct nlist *np;
      unsigned hashval;
      if ((np = lookup(name)) == NULL) { /* not found */
          np = (struct nlist *) malloc(sizeof(*np));
          if (np == NULL || (np-&gt;name = strdup(name)) == NULL)
              return NULL;
          hashval = hash(name);
          np-&gt;next = hashtab[hashval];
          hashtab[hashval] = np;
      } else /* already there */
          free((void *) np-&gt;defn); /*free previous defn */
      if ((np-&gt;defn = strdup(defn)) == NULL)
          return NULL;
      return np;
  }
  </code></pre>
  
  <p>Everything makes sense except for the following 2 lines:</p>
  
  <pre><code>np-&gt;next = hashtab[hashval];
  hashtab[hashval] = np;
  </code></pre>
  
  <p>When I try to understand this, I keep coming to the conclusion that the list now links back to itself and if you try to traverse the linked list it will be like a dog chasing its own tail.  I would expect the code to set np->next to NULL.</p>
  
  <p>What am I not understanding?  How come this code works ?</p>