C Exercise 2

Linked list manipulations

Assume you have a structure like this:

     struct node {
         int dat;
         struct node *next;
     };

a) Complete the body of the following function "new_node":

     struct node* new_node(int d)
     {

     }

What should new_node do? Given an integer value as paramter, new_node should malloc a structure of type "node", fill its "dat" field with the value passed as parameter, and initialize the "next" field of the structure with 0. The function should return the address of the newly allocated structure.

b) Write a function:

   struct node* append(struct node *h, struct node *n)
   {

   }

What does append do?

Let's say you are calling it from main like this:

   main()
   {
        struct node *h = 0;
        h = append(h, new_node(10));
        h = append(h, new_node(20));
        h = append(h, new_node(30));
   }

The result of the three calls to append should be: you should get a linked list having 3 nodes - the first node containing 10, next one 20 and the last node 30. The pointer variable "h" should contain the address of the first node of the list.

c) Write a function "count" which will return total number of nodes in a list; "count" should be a recursive function (do not use a global variable for maintaining count).

     n = count(h); /* returns number of nodes in list pointed to by h */

d) Write a function "insert_before" which will insert a new node before an existing node.

       h = insert_before(h, b, n); /* Insert "n" before "b"; "h" is starting address */

Take care to handle all special cases. Test your code thoroughly. First write an iterative version of this function and then try to write a recursive version.

e) Write a "reverse" function which works like this:

Suppose your list contains 10, 20, 30.

      h = reverse(h); 
      print_nodes(h); /* This will print 30, 20, 10 */

"reverse" does not create a new list - it simply changes the pointers in the existing list.

Write iterative as well as recursive versions

f) Write a recursive "print_nodes" function which will print the data contained in all the nodes of the list.