Solutions

Problem 1. (6 points) Quickies.

a. The class with no superclass is Object.

b. An immutable object cannot be modified.

c.

d. The class MyHouse will compile if implementations are provided for both prototypes of throughTheRoof (each of which takes a different parameter).

e. Binary search begins by inspecting the middle element of a list or sublist thereof. If the list is linked, you will have to traverse half the nodes in the list/sublist to reach the middle one. Assuming you start traversing from the left end, it will take binary search just as long to reach any given node as it would take a naive search.

Problem 2. (12 points) Bug Hunt.

The compile-time errors and their fixes are as follows.

• The field List.size is private, but the methods DList.copyList and DList.toDList change its value. size should be declared protected, or at least public or package.

• In the abstract List class, the method toDList should be declared abstract. Alternatively, you could provide an implementation (which will always be overridden anyway).

• The static method copyList attempts to use this, but this isn't defined in a static method. The line ``this.size = dbl.length();'' should read ``dbl.size = sngl.length();''. (The dbl-sngl mixup is my mistake, and we'll go easy on grading your correction to this line.)

• The method DList.toDList tries to reference newList.head, but the static type of newList is List, and there's no head field in the class List. Here are two fixes.
  • Change the declaration of newList: ``DList newList = new DList();''.
  • Cast newList: ``((DList) newList).head = head;''.

• The line of code that creates the sentinel doesn't create a sentinel that points to itself. The line is ``dbl.head = new DListNode(null, dbl.head, dbl.head);''. When the DListNode constructor is called, the value of dbl.head is still null; dbl.head isn't assigned an object until after the constructor finishes executing. Hence, the prev and next fields of the sentinel are still null. (Many of you encountered this bug during Homework 4, and it was also discussed on the newsgroup. Lesson: read the newsgroup.)

  One solution is to follow the dysfunctional line with the lines ``dbl.head.prev = dbl.head; dbl.head.next = dbl.head;''.

• When a new node is inserted at the end of the doubly-linked list, the sentinel's prev pointer is not adjusted. The line ``oldTail.next = newNode;'' should be accompanied by the line ``dbl.head.prev = newNode;''.

public void condense() {
  SListNode n = head;
  while (n != null) {
    if (n.next != null) {
      n.item = (String) n.item + (String) n.next.item;
      n.next = n.next.next;
      size--;
    }
    n = n.next;
  }
}