Consider the following buggy definition for a doubly-linked list:

 1 class DoublyLinkedIntSeq { 2 private class Node { 3 int data; 4 Node prev, next; 5 Node(int d) { data = d; next = prev = null; } 6 }; 7 private Node head, tail; 8 private Node current; 15 private boolean wellFormed() { ... } 35 public DoublyLinkedIntSeq() { 36 head = tail = null; 37 assert wellFormed() : "Invariant false after constructor"; 38 } 41 public void insert(int v) { 42 assert wellFormed() : "Invariant false before insert"; 43 if (current == null) { 44 if (tail != null) { 45 Node n = new Node(v); 46 n.next = tail; 47 tail.next = n; 48 tail = tail.next; 49 } else { 50 head = tail = new Node(v); 51 } 52 current = tail; 53 } else { 54 Node p = new Node(v); 55 p.prev = current.prev; 56 p.next = current; 57 current.prev.next = p; 58 current.prev = p; 59 current = p; 60 } 61 assert wellFormed() : "Invariant false after insert"; 62 } 63 64 public void advance() { // no bugs here! 65 if (!hasCurrent()) throw new IllegalStateException("at end already"); 66 current = current.next; 67 } 68 69 public boolean hasCurrent() { // no bugs here! 70 return current != null; 71 } 72 73 public void print() { // no bugs here! 74 for (Node p = head; p != null; p = p.next) { 75 if (p != head) System.out.print(","); 76 System.out.print(p.data); 77 } 78 System.out.println(); 79 } 

To test the code, we try the following test:

 82 DoublyLinkedIntSeq a = new DoublyLinkedIntSeq(); 83 a.insert(112); 84 a.insert(66); 85 a.print(); 

This code crashes on line 57:

Exception in thread "main" java.lang.NullPointerException at DoublyLinkedIntSeq.insert(DoublyLinkedIntSeq.java:57) at DoublyLinkedIntSeq.main(Driver.java:75) 

• In class we talked about rules for dereferencing. How was this rule violated on line 57?

• If we do the simplest thing to follow the rule and avoid the crash, the print call on rule 76 will only print 112. What should be on line 57? (Fix the whole bug)

• In an independent test, someone does:

   87 DoublyLinkedIntSeq b = new DoublyLinkedIntSeq(); 88 b.insert(42); 89 b.advance(); 90 b.insert(88); 91 b.print(); 

  Whether or not the first bug (b) is fixed, this will print 42,8842,8842,8842,... ad infinitum. Why? Explain!

• This problem would have been detected before the infinite loop by wellFormed() but it didn't get a chance because of the way that the programmer ran the test case. What is the job of wellFormed() and What problem could it have detected? Why doesn't it always run? (How is the invariant checking controlled by the tester?) Explain the reasoning behind this convention!

• Fix the code.