ANSWERS TO LINKED LIST EXERCISES


 1. Missing * before link.  This is a meaningless "recursive" declaration,
    defining what a structure is in terms of what a structure is.  With the
    * it makes sense because it says that link is a pointer to an
    element, whatever that is.

 2.  (a)   list->next = list->next->next;

           To free the node, too, put "t = list->next" before and "free(t)" after
           this statement.

     (b)   link t = malloc(sizeof *t);
           t->key = 17;
           t->next = list->next->next;
           list->next->next = t;

     (c)   int count(link x) {
              int cnt;
              for (cnt = 0; x != NULL; x = x->next)
                 cnt++;
              return cnt;  
           }

     (d)   int max(link x) {
              int m;
              for (m = -1; x != NULL; x = x->next)
                 if (x->key > max)
                    m = x->key;
              return m;       
           }

 3.  (a)   int count(link x) {
              if (x == NULL)
                 return 0;
              return 1 + count(x->next);
           }

     (b)   int max(link x) {
              int val;
              if (x == NULL)
                 return -1;
              val = max(x->next);
              if (val > x->key)
                 return val;
              else
                 return x->key;
           }


 4.        int count(link list) {
              int cnt = 0;
              link t = list;
              if (list == NULL)
                 return 0;
              do {
                 cnt++;
                 t = t->next;
              } while (t != list);
              return cnt;
           }

 5. The sizeof macro returns the number of bytes used to store
    a variable. In C, a "byte" is the size of a character. In C,
    the number of bytes used to store an int (or other object) may
    be different on different systems: the sizeof macro enables
    you to allocate the right amount of memory without worrying about
    the specific details of your system.

    To be pedantic, the above code should really be

       printf("%d", (int) sizeof(int));

    since sizeof does not return an integer, so the cast is needed.

 6. None. A is usually preferred, since if you change the type
    of x the malloc statement is still valid. Note also that you
    don't really need the parentheses in A.

 7. 144 (the smallest Fibonacci number that is not less than 100)