SDSU CS 596 Java Programming
Fall Semester, 1998
Assignment 3 Solution
To Assignment Index
© 1998, All Rights Reserved, SDSU & Roger Whitney
San Diego State University -- This page last updated 24-Oct-98

Contents of Doc C, Assignment 3 Solution 

Doc C, Assignment 3 Solution Slide # 2

Comments

Some people had their Enumeration return Node objects. This is not good. The structure of the linked list should be internal to the SortedLinkedList class. Returning Node objects requires users of the SortedLinkedList to deal with Node objects. This make is it more work to use the SortedLinkedList class. It also means that any changes to the Node class may require all code that uses the SortedLinkedList class to be modified. It also allows code outside of the SortedLinkedList class to modify the structure of a linked list without using the SortedLinkedList methods. All of this is bad news.

In the solution given below I apply the principle of "Just do it once". There are various locations in the SortedLinkedList class that require traversing the linked list: in toString(), in clone(), in add(), and a number of other standard list operations which were not part of the assignment. I put the code to traverse the list in the enumeration. I then use the enumeration whenever I need to traverse the list. "Just do it once" reduces the time needed to develop the code (no repeated code to type), reduces errors (repeated code may be incorrectly copied), and makes the code easier to modify and maintain (only have to find and modify the one place it was done). My clone() method was very easy to write, due the application of "Just do it once". The work of traversing the original linked list and adding the nodes to the cloned linked list is already done. Asking you to rewrite the toString() method using the enumeration was a hint to apply the "Just do it once" principle.

Normally I would not implement both a ListIterator and an Enumeration for the same class. If I did do implement both for the same class, I would apply the "Just do it once" principle and use the ListIterator in the implement of the Enumeration. I did not do this in the solution because the ListIterator was optional. I wanted to show people how to implement the Enumeration if they did not implement the ListIterator. 
Doc C, Assignment 3 Solution Slide # 3

Solution

package MyLinkedList;
import sdsu.compare.*;
import java.util.Enumeration;
import java.util.ListIterator;
import java.util.ConcurrentModificationException;

// SortedLinkedList Class 

public class SortedLinkedList implements Cloneable 
   {
   private Comparer compare;
   
   private Node frontOfList = null;
   
   //Iterators are to be fail-fast. modificationCount tracks
   // the number of changes to the list. Iterators use it to see
   // if the list was modified (has different modificationCount)
   // not using the iterator.
   private transient int modificationCount = 0; 
   
   public SortedLinkedList( Comparer listComparer )
      {
      compare = listComparer;
      }
      

Doc C, Assignment 3 Solution Slide # 4


   public void add( Object data )
      {
      modificationCount++;
      
      // Using the null object pattern would remove the 
      // need to check for the different cases here. 
      if ( frontOfList == null )
         {
         frontOfList = new Node( data, null, null );
         return;
         }
      
      else if  ( compare.lessThan( data, frontOfList.getData() ))
         {
         frontOfList = new Node( data, null, frontOfList );
         }
      
      else
         {
         LinkedListEnumeration cursor = (LinkedListEnumeration) elements();
         Node next;
         do
            {
            next = cursor.nextNode();
            }
         while ( cursor.hasMoreElements() && 
                     compare.lessThan( next.getData() , data ) );
         if  (compare.lessThan( next.getData() , data ) )
            next.append( data );
         else
            next.prepend( data );
         }
      }
   

Doc C, Assignment 3 Solution Slide # 5


   public Object clone() throws CloneNotSupportedException
      {
      SortedLinkedList newList = (SortedLinkedList) super.clone();
      
      newList.frontOfList = null;
      
      Enumeration elements = elements();
      while (elements.hasMoreElements()) 
         newList.add( elements.nextElement());
      return newList;
      }
      
   public String toString() 
      {
      // The compiler translates "string" + "string" to:
      //     StringBuffer _temp = new StringBuffer();
      //      _temp.append( "string" );
      //      _temp.append( "string" );
      // Using StringBuffer explicitly eliminates the possible
      // creation of new StringBuffer inside the while loop.
      StringBuffer listAsString = new StringBuffer();
      
      Enumeration elements = elements();
      while (elements.hasMoreElements()) 
         {
         listAsString.append( elements.nextElement() );
         listAsString.append( " " );
         }
      return listAsString.toString();
      }
      
   public Enumeration elements()
      {
      return new LinkedListEnumeration();
      }

Doc C, Assignment 3 Solution Slide # 6


   public ListIterator listIterator()
      {
      return new LinkedListListIterator();
      }
   
   private void remove( Node toRemove )
      {
      if ( toRemove == null )
         return;
         
      if ( toRemove == frontOfList )
         frontOfList = toRemove.getNext();
      toRemove.remove();
      modificationCount++;
      }
   




//
LinkedListEnumeration Class




   // Much of the class used inner classes, so it seemed reasonable
   // to do so here, even though we have not covered them yet.   
   private class LinkedListEnumeration implements Enumeration
      {
      // next points to the next element to return
      Node next = frontOfList;
      
      public boolean hasMoreElements()
         {
         if ( next == null )
            return false;
         else
            return true;
         }
      



      // Internally to SortedLinkedList class it is useful to 
      // enumerate through the nodes. This method allows
      // this to happen. Note, this method is not accessable
      // outside of the SortedLinkedList class.
      Node nextNode()
         {
         Node nodeToReturn = next;
         next = next.getNext();
         return nodeToReturn;
         }
         
      public Object nextElement()
         {
         Node nextNode = nextNode();
         return nextNode.getData();
         }
      }// End LinkedListEnumeration
   






//
LinkedListListIterator Class




   // Here is the optional part of the assignment. I did not use 
   // the LinkedListListIterator in the LinkedList because it was 
   // optional
   private class LinkedListListIterator implements ListIterator
      {
      // Use next and previous to handle boundary condition,
      // if user iterates to the end of the list, next becomes null.
      // Can still iterate backwards through list by using previous
      // Could have kept track of last returned instead.
      private Node next = frontOfList;
      private Node previous = null;
      private int nextIndex = 0;
      
      // Iterator can move in different directions 
      // Need to know when removing nodes, which direction
      // we went last.
      private boolean forward = true;
      
      // The iterator keeps track of the modifications it makes to the 
      // linked list. If the iterators modification count does not match
      // the linked list modifcation count, then linked list was changed
      // by some other means - iterator throws exception as it is fail-fast
      private int expectedModificationCount = modificationCount;
      
      public void add( Object toAdd)
         {
         throw new UnsupportedOperationException(
                "Can not use add in ordered linked list list iterator");
         }
      
      public boolean hasNext()
         {
         return next != null;
         }
         



      public boolean hasPrevious()
         {
         return nextIndex > 0;
         }
   
      // Use nextNode and previousNode for two reasons:
      //   1. Separate the task of next into two logical parts
      //   2. Internally in the SortedLinkedList class it is useful
      //       to iterate through the nodes. (not shown here)
      // Note, these methods are not accessable outside of 
      // the SortedLinkedList class
      Node nextNode()
         {
         forward = true;
         previous = next;
         next = next.getNext();
         nextIndex++;
         return previous;
         }
      Node previousNode()
         {
         forward = false;
         next = previous;
         previous = previous.getPrevious();
         nextIndex--;
         return next;
         }
         
      public Object next()
         {
         checkForComodification();
         return nextNode().getData();
         }



      public Object previous()
         {
         checkForComodification();
         return previousNode().getData();
         }
         
      public int nextIndex()
         {
         return nextIndex;
         }
         
      public int previousIndex()
         {
         return nextIndex - 1;
         }
      
      /**
       * Removes the last element returned by iterator
       */
      public void remove ()
         {
         if (forward)
            {
            // When moving forward last returned element is previous
            SortedLinkedList.this.remove( previous );
            previous = next.getPrevious();
            nextIndex--;
            }
         else
            {
            // When moving backward last returned element is next
            SortedLinkedList.this.remove( next );
            next = previous.getNext();
            }
            
         // Keep track of changes iterator makes to the list
         expectedModificationCount++;
         }



      public void set( Object newValue )
         {
         throw new UnsupportedOperationException(
                "Can not use set in ordered linked list");
         }
      final void checkForComodification() 
         {
         if (modificationCount != expectedModificationCount)
            throw new ConcurrentModificationException();
         }
      } // End LinkedListListIterator
} //End SortedLinkedList




//
Node Class




// This class has not changed from the assignment posting
final class Node {
   private Object data;
   private Node next = null;
   private Node previous = null;
   public Node( Object initialData) {
      this( initialData, null, null );
   }
   public Node( Object initialData, 
                  Node previousInList, 
                  Node nextInList )   {
      data = initialData;
      next = nextInList;
      previous = previousInList;
      if ( next != null )
         next.previous = this;
      if ( previous != null )
         previous.next = this;
   }



   public void append( Object data ) { 
      new Node( data, this, next); 
   }
   public void prepend( Object data ) { 
      new Node( data, previous, this); 
   }
   public void remove() {
      if ( previous != null )
         previous.next = next;
      if ( next != null )
         next.previous = previous;
      previous = null;
      next = null;
   }
      
   public Node getNext() { 
      return next; 
   }
   public Node getPrevious() { 
      return previous; 
   }
   public Object getData() {
      return data;
   }
   
   public void setData( Object newData ) {
      data = newData;
   }
}




	Copyright © 1998 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
	
 All rights reserved. 






	
		
	 visitors since 24-Oct-98