CSE 131 Module 8: List Structures

• Module Home
• Studio
• Lab
• Practice Problems
• Practice Quiz
• Extensions
• Bridges

Practice Problems

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 Address	Memory Contents
   100	107
   101	0
   102	112
   103	116
   104	134
   105	118
   106	109
   107	100
   108	103
   109	114
   110	116
   111	106
   112	111
   113	102
   114	116
   115	0
   116	122
   117	114
   118	0
   119	110

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?

Solutions