LINKED LIST EXERCISES

READING 
-------
Kernighan and Ritchie, 
Sedgewick, 3.3, 3.4
King, 17.1 -17.5 (Dynamic storage and linked lists)
      425-426 (Stack)

EXERCISES
---------

 1. What is wrong with the following declaration?

          struct element { float f; struct element link; }

 2. Suppose that a linked list is made up of nodes of type

          typedef struct node* link;
          struct node { int key;  link next; };

    that you are given a pointer "list" of type link, which
    points to the first node of the list; that the last node
    has NULL as its link; and that there are at least two nodes on the
    list.  Write a code fragment to delete the second node of the list.

 3. Under the same conditions as the previous question, write a code
    fragment to add a new node just after the second node of the list.

 4. What is printed by the following code fragment on your system, and
    what does it mean?

         int x, a[10];
         char y;
         printf("%d %d %d\n", sizeof(x), sizeof(y), sizeof(z));

 5. What is the difference between the following given the following
    declaration

         typedef struct node* link;
         struct node { int key; link next; };
         
         A. link x = malloc(sizeof(*x));
         B. link x = malloc(sizeof(*link));
         C. link x = malloc(sizeof(struct node));

 6. What does the following program print out?

          #include <stdio.h>
          #include <stdlib.h>
          typedef struct node* link;
          struct node { int key; link next; };
          int main(void) {
             link x, y, t;
             x = malloc(sizeof *x);
             y = malloc(sizeof *y);
             x->next = y; x->key = 1;
             y->next = x; y->key = 1;
             for (t = x; t->key < 100; t = t->next)
                t->key = x->key + y->key;
             printf("%d\n", t->key);
             return 0;
          }



















.
.
.
.
		   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. 
        list->next = list->next->next;
    
    To free the node, too, put "t = list->next" before and "free(t)" after
    this statement.

 3. 
        link t = malloc(sizeof *t);
        t->next = list->next->next; list->next->next = t;

 4. The sizeof macro returns the number of bytes used to store
    a variable. In C, a "byte" is the size of a character. However,
    most people use the term "byte" to refer to 8 bits. In C, the
    number of bits in a byte is defined by the constant CHAR_BIT
    which can be larger. The number of bytes used to store an int
    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.

 5. None. A is usualled 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.

 6. The smallest Fibonacci number that is not less than 100: 144