Worksheet, Data Structures and Algorithms, Week 8 -- Thurs Nov 15 2001

Assume the following Java code:

public class Item {

    // Instance variables

    Item next;

    int i;

    String s;



    // Constructor

    public Item(int x, String msg) { i = x; s = msg; next = null; }



    // Other methods ...

}



public class ItemDemo {

    public static void main(String argv[]) {

        Item head = null, newitem = null, ptr = null;

        // code appears in numbered fragments below ...

    }

}

Assume the numbered code fragments below are executed in they order they appear.

Draw a diagram showing variables, values, objects, and references in memory after each code fragment executes.

If the code fragment contains a print or println statement, write what the statement prints.

Draw a variable as a box with the variable name as a label to the side and the value inside the box. Draw an object as a box containing instance variables. Draw references as arrows with a spot at the variable end and an arrowhead at the object end. Draw an X for the null reference.

1. 
   head = new Item(1, "a");
   
   

   Here is the diagram:

                
   
                     +--------------+
   
        +-----+      |      +-----+ |
   
   head |  o--+----->| next |  X  | |
   
        +-----+      |      +-----+ |
   
                     |      +-----+ |
   
                     |   i  |  1  | |
   
                     |      +-----+ |
   
   		  |      +-----+ |
   
                     |   s  |  o--+-+---> "a"
   
                     |      +-----+ |
   
                     +--------------+
   
   

2. 
   newitem = new Item(2, "b");
   
   

3. 
   newitem.next = head;
   
   head = newitem;
   
   

4. 
   newitem = new Item(3, "c");
   
   newitem.next = head;
   
   head = newitem;
   
   System.out.println(head.i + " " + head.next.i + " " + head.next.next.i);
   
   

5. 
   ptr = head;
   
   

6. 
   System.out.print("head -> " + ptr.i + ". " + ptr.s);
   
   

7. 
   ptr = ptr.next;
   
   

8. 
   if (ptr != null) { 
   
       System.out.print(" -> " + ptr.i + ". " + ptr.s);
   
       ptr = ptr.next;
   
   } else System.out.println(";");
   
   

9. 
   if (ptr != null) { 
   
       System.out.print(" -> " + ptr.i + ". " + ptr.s);
   
       ptr = ptr.next;
   
   } else System.out.println(";");
   
   

10. 
    if (ptr != null) { 
    
        System.out.print(" -> " + ptr.i + ". " + ptr.s);
    
        ptr = ptr.next;
    
    } else System.out.println(";");
    
    

11. 
    ptr = head;
    
    

12. 
    if (ptr != null && ptr.i != 2) {
    
         ptr = ptr.next;
    
    } else System.out.println(ptr.i + ". " + ptr.s);
    
    

13. 
    if (ptr != null && ptr.i != 2) {
    
         ptr = ptr.next;
    
    } else System.out.println(ptr.i + ". " + ptr.s);
    
    

14. 
    if (ptr != null && ptr.i != 2) {
    
         ptr = ptr.next;
    
    } else System.out.println(ptr.i + ". " + ptr.s);
    
    

15. Rewrite the code in 8. through 10. as a single while loop.
    
    
16. Rewrite the code in 11. through 14. as a single for loop.