CPS 100, Fall 2002, Week #4

Answer the following questions and bring them to your recitation on Sept 23-25, 2002. < Use this definition of Node.

struct Node
{
    string info;
    int    count;      // # occurrences
    Node * next;       // points to next node in list

    Node (const string& s, Node * link)
	: info(s), next(link)
    { }
};

These next questions here are based, in part, on the code in linkedlistdemo.cpp.

Write an iterative version of the function copy from the code and reproduced below.
```
  Node * copy(Node * list)
  // pre: list is NULL/0 terminated    
  // post: returns a copy of list
  {
      if (list == 0) return 0;
      return new Node(list->info, copy(list->next));
  }
```
First make a copy of the first node maintaining two pointers to this: first and last. Maintain the last pointer as always pointing to the last node of the copied list being constructed. Turn in this function during recitation
Examine the functions revList and revList2 in the code.
Both functions satisfy their postconditions: both reverse a linked list by changing pointers. Draw a picture of what happens with the list (a,b,c,d) when the three lines below from revList2 execute. To start you should make a picture of list pointing to (a,b,c,d) using nodes for each letter/word, e.g., something like this
```
            +---+   +---+   +---+   +---+
    list--->| A |-->| B |-->| C |-->| D |->|||
            +---+   +---+   +---+   +---+
```
You should draw three pictures like the one above. The pictures should show where the pointers in the list above point after each fo the three statements below execute. For example, after the first statement executes revRest should point to nodes that represent (d,c,b), with links changed since the recursion has finished. Node * revRest = revList2(list->next); // all reversed but first list->next->next = list; // last points to first list->next = 0; // first poins to NULL
1. Assume that each time a statement including a dreference of some node's next field is executed a cost of 1 unit is incurred. This means temp = temp->next costs 1 unit and that the statement Node * revRest = revList(list->next) costs 1 unit.
  The cost of executing the iterative revList(list) function when list points to an 1-node list and the cost of revList2(list) when list points to an 1-node list are given in the table below? Why are these the costs? Same for 2-node lists. Costs include all costs generated by recursive calls as well as by the original function call.
  Fill in the table for 3, 4, and 5 node lists. The statement list->next->next = list has a cost of 2 since there are two dereferences to get to a next field.
  # nodes iterative revList cost recursive revList2 cost
  1 1 1
  2 6 6
  3
  
  4
  
  5
  
  N
2. Now generalize: What is the cost of executing revList(list) when list points to an N-node list? and what is the cost of revList2(list) when list points to an N-node list? Why? ball-park estimates are fine, big-Oh is fine.
Susan H. Rodger
Last modified: Thu Sep 19 12:25:39 EDT 2002

# nodes	iterative revList cost	recursive revList2 cost
1	1	1
2	6	6
3
4
5
N