Solutions

Problem 1. (6 points) Quickies.

a. Another name for static fields is class variables.

b. Advantages of a linked list over an array (any one will suffice):

• An item can be inserted at the beginning of a linked list without the need to move all the other items.
• The size of a linked list can always be increased by one quickly (specifically, in O(1) time) without ever taking the time to allocate and copy a whole array (which takes O(n) time).

c. Advantages of an array over a linked list (any one will suffice):

• Any single item can be read or changed quickly (specifically, in O(1) time) simply by knowing its position in the array.
• An array takes less memory (by a constant factor) than a linked list to store the same number of items.

d. Yes. myMethod can be overloaded by a second implementation of myMethod in MyClass that has a different signature. myMethod can be overrided by a third implementation of myMethod in a subclass of MyClass that has the same signature.

Problem 2. (8 points) Inheritance.

a. m returns 5

b. int i = ((XPlus) x).r();

c. return super.m();

d. The very last line of code causes a compile-time error. All the other lines compile and run without incident.

Problem 3. (5 points) Lists made of cons cells.

public static void main(String[] args) {
  Cons v = new Cons();
  v.cdr = new Cons();
  v.cdr.cdr = new Cons();
  v.cdr.cdr.cdr = v.cdr;
  v.car = 2;
  v.cdr.car = 3;
  v.cdr.cdr.car = 9;
}

public void breakLoop() {
  if (cdr != null) {
    if (cdr.car == -1) {
      cdr = null;
    } else {
      int i = car;
      car = -1;
      cdr.breakLoop();
      car = i;
    }
  }
}