CSE 131 / 501N (Fall 2013)
Recitation Questions

Consider the following class definition (as presented in lecture) and then answer the questions below.
class ListItem {
   public int number;
   public ListItem next;

   ListItem(int number, ListItem next) {
      this.number = number;
      this.next = next;
   }

   public String toString() {
      if (next == null)
         return "" + number;
      else
         return number + " " + next;
   }
}

  1. Carefully draw an object and reference diagram corresponding to the result of executing the following code. If an object is "shared" by two or more lists, draw it only once with multiple arrows pointing to it. Remember that Java evaluates expressions left to right, but always evaluates parameters before making a procedure call.
    
    ListItem a, b, c, d;
    a = new ListItem(1,null);
    b = new ListItem(2,null);
    b.next = a;
    c = new ListItem(3,b);
    d = new ListItem(4, new ListItem(5, new ListItem(6, b)));
    c = c.next;
    
    System.out.println("a = (" + a + ")");
    System.out.println("b = (" + b + ")");
    System.out.println("c = (" + c + ")");
    System.out.println("d = (" + d + ")");
    
    

  2. What output would be printed as the result of executing the code given in Problem 1?

  3. A ListItem object (as defined above) is stored in memory as two contiguous memory cells (contiguous means that they are consecutive, one immediately following the other). The first cell of the object corresponds to the number being held by the ListItem, and the second cell contains the memory address of the next ListItem. Draw an object and reference diagram for ListItems being held in the following memory. There are two lists, one starting at memory location 112, and the other starting at memory location 104. In memory, the null value is represented as 0.

    Memory AddressMemory Contents
    100107
    1010
    102112
    103116
    104134
    105118
    106109
    107100
    108103
    109114
    110116
    111106
    112111
    113102
    114116
    1150
    116122
    117114
    1180
    119110

  4. In problem 3, which memory locations are not used in either list?

  5. Suppose we store the value 118 into memory location 117. Now what would the object and reference diagram look like? Now which memory locations are not used in either list?

  6. Assuming that memory locations are allocated in order starting from address 200, draw a memory table like the one in Problem 3 that would result at the end of the execution of the code in Problem 1. Which memory locations are not used in any of the lists?