Assignment 1

The Assignment

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Attach the source code of your Java application. Send me only the source code (.java files); do not include the .class or any other files. Do not zip or otherwise bundle the .java files.

Recommendations

Write DLLNode first.

• It should have three private instance member variables: Object value, DLLNode next, and DLLNode prev.
• It should have at least 1 public constructor (public DLLNode(Object value, DLLNode prev, DLLNode next)) and 6 public methods (a get and set for each of your three private member variables--getValue, setNext, etc.)
• Your variable names and methods can be named differently than I've described here.
• I recommend that your toString method print out the prev and next links, as well as the contents of the node. Something like this:
      [(null) <- node1 contents -> (node2 contents)]
  This will be helpful in debugging.

Write DLList.

• At first, don't include the "implements List" part. Just write the methods one at a time and make sure DLList compiles after each one.
• Start with add and toString. Then do the various size, contains, indexOf, and gets methods. Then do the removes. Finish with the equals method (remember, this is whether two DLLists are equal).
• Ideally, you should also test each method as you write it to make sure it works. For example, after you write contains, create a new DLList in the main method of DLList. Does an empty list contain the String "hello"? Now add the String "hello" to your DLList. Does contains now return true when you ask if it contains a String "hello"? Does it return false when you ask if it contains the String "other"? Good--contains is to be working correctly. Now you can move on to the next method.
• Your DLList toString output should contain only the contents of the list, not any of the links between the nodes. (Unlike DLLNode's toString.)
• Read the List API documenation for each method you are implementing! You need to know what your methods are supposed to do. (You do not need to document the methods of DLList that are inherited from List, since the documentation will also be inherited. However, you must write the methods to perform exactly as described in the List API.)
• Don't worry about the efficiency of your alogrithms. Worry instead about coder efficiency and code clarity--how you can you write correct code the quickest? Reuse other methods whenever you can. For example, you can use indexOf to implement contains; you could use get to implement set. You can also write private helper methods. For instance, a private method that returns the DLLNode at a given index would be very helpful for add, set, get, and remove at a position. Reusing code whenever you can cuts down on possible bugs: you can test a helper method, makes sure it works correctly, and then reuse it from a number of other methods. Even if you do find a bug later, it'll only be in that one helper method. You won't have to search through your entire class for all that code you cut-and-pasted.
• Once you have your methods written, add the unhighlighted methods. It is probably best to have them all just throw an UnsupportedOperationException, like this:

  public Object[] toArray() {
    throw new UnsupportedOperationException();
  }
  

  Then add the "implements List" part and try to compile again. This will tell you where you have deviated from the List interface.

Write DLLTest

• Write this class last.

Help Getting Started

For those of you who have absolutely no idea of how to start.

DLLNode.java. First, write the DLLNode class as described above. There's examples in the textbook of single-linked Nodes. In DLLNode, you are just building the node data structure; you are not actually connecting anything together. You never actually create a new DLLNode(...); in DLLNode.java. Make sure your node will hold an Object, not a String or some other less general class.

DLList.java. The only member variable you really need is private DLLNode head; Write the add(Object o) method first. The code below is a guide. /*comments*/ mean you need to replace these with code. //comments explain how you should be thinking about the problem; you can remove these after you write the code.

public boolean add(Object obj){
  //we can't just attach obj to our list;
  //we need to put it in a node first.
  /*
   *create a new DLLNode newNode containing obj
   */
  //Now you can add this node to your list.
  //But there are two cases you need to deal with:
  // -- when the list is empty, which means head == null
  // -- you already have some node(s) in the list.
  if (head == null) { //list is empty
    /*
     * Make head point to your new node.
     * You don't need to change any of newNode's links
     * because there are no other nodes to point to
     */
  }else {
     //You need to get to the end of the list
     //so you can add newNode there.
     //You only have a reference (head) to 
     //the start of the list, so you'll need a cursor
     //to move from the start of the list to the end
     //along the chain of nodes.
     
     DLLNode curr = head;  
     
     //Now curr is pointing to the first node.
     //And you know curr != null, because if there
     //was no first node, you wouldn't be in this else
     //block right now.
     
     while (curr.getNext() != null) {
     
       //we want to move along the list until curr
       //points to the last node, just before we fall
       //off the end of the list and curr goes to null.
       //(If you get any NullPointerExceptions, it is 
       //because you "fell off the end of the list" 
       //somewhere.)
       /*
        * Make curr point to the next node in the list
        */
     
     }
     
     //now curr is pointing at the last node 
     //(since curr.getNext() == null)
     
     curr.setNext( /* to what? */ );
     /*
      * finish connecting newNode to the end
      * of the list.  (Remember there's 2 links.)
      */
  }
  //now we're done adding our node to the list
  //we need to return true if we successfully added
  //the element.  (Some lists don't allow nulls or 
  //duplicate items, and so would return false if they
  //were given such an item.  We take any kind of item,
  //so we'll always return true.)
  return true;
}    

This is only one way to do it. Note that we are not using or maintaining a tail variable in this example. If you needed this help, be sure to trace this code on paper for adding an item to list that already contains 0, 1, 2, and 3 objects. Make sure you know how it works. Note how traversing the list happens. If you need to reach a certain position in the list, you can create a counter, starting at 0, and increment it each time you move along the list to a new node. Then you could stop traversing when you reach the position you need.

Grading:

Out of 10 points:

1 - Compiles

If you send me the three files and they compile, it's worth a point.

2 - Documentation and Coding Standards

Make sure you document all your classes. Again, you may want to reread the documentation and coding standards guidelines for this class. (Note below that you may not need to document the methods of DLList.)

1.5 - DLLNode

A proper doubly-linked list Node ADT, where each node has an Object value/contents, and references/links to 2 other DLLNodes. Also has a working toString method.

4.0 - DLList

Needs to implement the List interface, with the 13 highlighted methods fully and correctly implemented. Documentation of these methods is not required as long as you implemented them as described in the List interface documentation.

0.5 - toString

Returns a readable String version of a DLList that does not reveal implementation details. (This is invaluable for debugging!)

1.0 - DLLTest

Prints, reverses, and re-reverses a DLList as described in the assignment specs. DLLTest actually reverses the list, and doesn't just print it backwards.

You can use this program -- DLLGrader.java -- to check your implementation. This is basically how I will grade your program, though I might change or add a few things. Passing DLLGrader doesn't guarantee that your implementation is completely correct, but it should catch most of the bugs.

Solution

Zach's Solution. Remember, there's always more than one way to do it; this is just the way I did it. The most important criteria for a program is whether it works correctly. A close second is whether someone else can read (and so maintain) it.