CS35 Homework #2:

Interfaces and Testing

Due 11:59pm Wednesday, 19 September 2007

You should save your programs in your cs35/homework/02 directory. This directory will appear if you run update35. The program handin35 will only submit files in this directory. For this assignment, you should work by yourself.

Implement an Interface
Create a class SList that implements the following interface using a singly-linked list. Note this interface is similar, but not identical to the DLinkedList interface discussed in class. In particular, most of the methods add or return elements/items instead of Nodes which have contain both elements and links.
public interface LinkedList { 
  /** Returns the number of elements in the list */
  public int size();

  /** Returns whether the list is empty */
  public boolean isEmpty();

  /** Returns the element in the first node of the list,
   *  or null if no such element exists */
  public String getFirstElement();
  /** Returns the element in the last node of the list,
   *  or null if no such element exists*/
  public String getLastElement();

  /** Inserts the given element at the head of the list */
  public void addFirst(String item);

  /** Inserts the given element at the end of the list */
  public void addLast(String item);

  /** Returns true if given element appears in list, false otherwise */
  public boolean hasItem(String item);

  /** Removes the *first* occurence of given element from the list.
   *  Return true if element found and removed, false otherwise */
  public boolean remove(String item);

  /** Returns a string representation of the list */
  public String toString();

Write Testing Code
Write a test class TestLinkedList that tests your SList. You should think of good test cases that check all the methods of the class and test any special cases that might cause problems. In a README file, summarize what types of special cases your test code checks.

Optional Components
If you are feeling adventurous and have finished the rest of the assignment, try extending your interface/class to use generics. Note this is completely optional and completing/skipping this component will not affect your homework score. You may find the GenericNode class from Friday's class helpful. You may also want to practice your search and replace in vim. In command mode, type :%s/old text/new text/gc. The gc at the end will prompt you to confirm if you want to replace a given match. Omitting the c will skip the confirmation step.

Along with your java source code, you should hand in a file named README and your Makefile if you used one. These files will be imported automatically via handin35. Your README should include a brief summary of your results, along with any known problems/bugs in your code.

Once you are satisfied with your programs, hand them in by typing handin35 at the unix prompt. You may run handin35 as many times as you like, and only the most recent submission will be recorded.