Question

Please help with this Java Program. Thank you!

we will be implementing an Ordered List ADT. Our goal is to implement the interface that is provided for this ADT. Notice that there are two interfaces: OrderedListADT builds on ListADT. In this homework, you'll only be responsible for the OrderedListADT.

Figure 1: UML Overview

1

Requirements

Create a doubly linked implementation of the OrderedListADT interface. Note that the book includes most of the source code for a singly linked implementation of OrderedListADT - plan to read over it, and reuse whatever is appropriate. In particular, notice which exceptions are used. You will need to create a total of four classes: DoubleOrderedList, DoubleNode, DoubleList, and Driver (for testing):

DoubleNode: A class that represents a doubly linked node. The source from LinearNode.java may be useful. [5 points]

DoubleList: A class that represents a doubly linked structure, with functionality to remove nodes. The source from LinkedList.java may be useful. Must implement ListADT<T> and Iterable<T>. [15 points]

DoubleOrderedList: A class that extends the functionality from DoubleList by adding a method to add new elements. The source from LinkedOrderedList.java may be useful. Must extends DoubleList<T> and implements OrderedListADT<T>. [15 points]

Driver: This will be the class that contains the main, and testing code you write. [5 points]

Lastly, write appropriate testing documentation -
Attached to this assignment are six files. The rst ve are from the textbook's source code but have been

slightly modifed - the package declaration was removed.

ListADT.java: This interface defines the list ADT.

OrderedListADT.java: This interface defines the ordered list ADT.

NonComparableElementException.java, EmptyCollectionException.java, ElementNotFoundException.java: These les implement the various exceptions your collection will need.

Driver.java: This le contains a very simple test case for DoubleOrderedList, and the output associated with it.

LIST.JAVA below

 
/**
 * ListADT defines the interface to a general list collection. Specific
 * types of lists will extend this interface to complete the
 * set of necessary operations.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public interface ListADT<T>
{
    /**  
     * Removes and returns the first element from this list. 
     * 
     * @return the first element from this list
     */
    public T removeFirst();

    /**  
     * Removes and returns the last element from this list. 
     *
     * @return the last element from this list
     */
    public T removeLast();

    /**  
     * Removes and returns the specified element from this list. 
     *
     * @param element the element to be removed from the list
     */
    public T remove(T element);

    /**  
     * Returns a reference to the first element in this list. 
     *
     * @return a reference to the first element in this list
     */
    public T first();

    /**  
     * Returns a reference to the last element in this list. 
     *
     * @return a reference to the last element in this list
     */
    public T last();

    /**  
     * Returns true if this list contains the specified target element. 
     *
     * @param target the target that is being sought in the list
     * @return true if the list contains this element
     */
    public boolean contains(T target);

    /**  
     * Returns true if this list contains no elements. 
     *
     * @return true if this list contains no elements
     */
    public boolean isEmpty();

    /**  
     * Returns the number of elements in this list. 
     *
     * @return the integer representation of number of elements in this list
     */
    public int size();

    /**  
     * Returns a string representation of this list. 
     *
     * @return a string representation of this list
     */
    public String toString();
}

Please find OrderedListADT.java below

/**
 * OrderedListADT defines the interface to an ordered list collection. Only
 * Comparable elements are stored, kept in the order determined by
 * the inherent relationship among the elements.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public interface OrderedListADT<T> extends ListADT<T>
{
    /**
     * Adds the specified element to this list at the proper location
     *
     * @param element the element to be added to this list
     */
    public void add(T element);
}

Answer 1

Driver.java

public class Driver {
    public static void main(String [] args) {
        DoubleOrderedList list = new DoubleOrderedList<>();
        //RA: These are _extremely_ simple tests - do not use them when doing
        //    your writeup.
      
        list.add(23);
        list.add(24);  
        list.add(16);
        list.add(3);  
        list.add(7);
        list.add(17);  
        list.add(9);  
        list.add(13);  
        list.add(14);  
        list.add(1);

        System.out.println(list);
      
        System.out.println(list.remove(7));
        System.out.println(list);
        System.out.println(list.removeFirst());
        System.out.println(list);
        System.out.println(list.remove(17));
        System.out.println(list);
        System.out.println(list.removeLast());
        System.out.println(list);
        System.out.println(list.remove(14));
        System.out.println(list);
        System.out.println( list.removeLast());
        System.out.println(list);
      
        System.out.println(list);
      
      
        /* Test Results:
            1 3 7 9 13 14 16 17 23 24
            3 9 13 16
        */
      
        // My Tests
      
        System.out.println("My tests:" );
        list = new DoubleOrderedList<>();
      
        list.add(1);
        System.out.println(list.removeFirst());
        list.add(2);
        System.out.println(list.removeLast());
      
        try {
           list.add(1);
           list.add(new DoubleOrderedList());
        }
        catch(NonComparableElementException e) {
           System.out.println(e);;
        }
  
        try {
           list.remove(2);
        }
        catch(ElementNotFoundException e) {
           System.out.println(e);
        }
      
        try {
           list.removeFirst();
           list.removeFirst();
        }
        catch(EmptyCollectionException e) {
           System.out.println(e);
        }
      
        try {
           System.out.println(list.first());
       } catch (Exception e) {
           // TODO Auto-generated catch block
           System.out.println(e);
       }
      
        try {
           System.out.println(list.last());
       } catch (Exception e) {
           // TODO Auto-generated catch block
           System.out.println(e);
       }
    }
}

DoubleOrderedList.java

public class DoubleOrderedList<T> extends DoubleList<T> implements OrderedListADT<T>{
  
   public DoubleOrderedList() {
       super();
   }
  
   @Override
   public void add(T element) throws NonComparableElementException {
       // TODO Auto-generated method stub
       if (!(element instanceof Comparable))
           throw new NonComparableElementException(getClass().getName());
      
       DoubleNode<T> temp = new DoubleNode<>(element);
      
       @SuppressWarnings("unchecked")
       Comparable<T> comp = (Comparable<T>)element;
      
      
       if(isEmpty())
           head = tail = temp;
       else if (comp.compareTo(first()) > 0) {
           tail.setNext(temp);
           temp.setPrev(tail);
           tail = temp;
          
       }
       else if (comp.compareTo(last()) < 0) {
           head.setPrev(temp);
           temp.setNext(head);
           head = temp;
       }
       else {
           boolean done = false;           
           DoubleNode<T> first = head;
           DoubleNode<T> second = head.getNext();
          
           while (second != null && !done) {
               if(comp.compareTo(second.getElement())<0)
                   done = true;
               else {
                   first = second;
                   second = second.getNext();
               }
           }
          
           temp.setNext(first.getNext());
           temp.setPrev(first);
           first.setNext(temp);
           first.getNext().setPrev(temp);
          
       }
      
       count++;
      
   }

}

DoubleNode.java

public class DoubleNode<T> {
   private T element;
   private DoubleNode<T> next;
   private DoubleNode<T> prev;
  
   public DoubleNode() {
       next = prev = null;
       element = null;
   }
  
   public DoubleNode(T element) {
       next = prev = null;
       this.element = element;
   }
  
   public DoubleNode<T> getNext() {
       return next;
   }
  
   public DoubleNode<T> getPrev() {
       return prev;
   }
  
   public void setNext(DoubleNode<T> node) {
       next = node;
   }
  
   public void setPrev(DoubleNode<T> node) {
       prev = node;
   }
  
   public void setElement(T element) {
       this.element = element;
   }
  
   public T getElement() {
       return element;
   }

}

ElementNotFoundException.java

public class ElementNotFoundException extends RuntimeException
{
    /**
     * Sets up this exception with an appropriate message.
     */
    public ElementNotFoundException (String collection)
    {
        super ("The target element is not in this " + collection);
    }
}

NonComparableElementException.java

public class NonComparableElementException extends RuntimeException
{
    /**
     * Sets up this exception with an appropriate message.
     *
     * @param collection the exception message to deliver
     */
    public NonComparableElementException (String collection)
    {
        super ("The " + collection + " requires comparable elements.");
    }
}

OrderedListADT.java

public interface OrderedListADT<T> extends ListADT<T>
{
    /**
     * Adds the specified element to this list at the proper location
     *
     * @param element the element to be added to this list
     */
    public void add(T element);
}

ListADT.java

public interface ListADT<T>
{
    /**
     * Removes and returns the first element from this list.
     *
     * @return the first element from this list
     */
    public T removeFirst();

    /**
     * Removes and returns the last element from this list.
     *
     * @return the last element from this list
     */
    public T removeLast();

    /**
     * Removes and returns the specified element from this list.
     *
     * @param element the element to be removed from the list
     */
    public T remove(T element);

    /**
     * Returns a reference to the first element in this list.
     *
     * @return a reference to the first element in this list
     */
    public T first();

    /**
     * Returns a reference to the last element in this list.
     *
     * @return a reference to the last element in this list
     */
    public T last();

    /**
     * Returns true if this list contains the specified target element.
     *
     * @param target the target that is being sought in the list
     * @return true if the list contains this element
     */
    public boolean contains(T target);

    /**
     * Returns true if this list contains no elements.
     *
     * @return true if this list contains no elements
     */
    public boolean isEmpty();

    /**
     * Returns the number of elements in this list.
     *
     * @return the integer representation of number of elements in this list
     */
    public int size();

    /**
     * Returns a string representation of this list.
     *
     * @return a string representation of this list
     */
    public String toString();
}

DoubleList.java

public class DoubleList<T> implements ListADT<T>{
   protected DoubleNode<T> head;
   protected DoubleNode<T> tail;
   protected int count;
  
   /**
   * Initializes the Doublelist.
   */
   public DoubleList() {
       head = tail = null;
       count = 0;
   }
  
   @Override
   public T removeFirst() throws EmptyCollectionException {
       // TODO Auto-generated method stub
       if(isEmpty())
           throw new EmptyCollectionException(getClass().getName());
       else if (head == tail) {
           DoubleNode<T> temp = tail;
           head = tail = null;
          
           count--;
          
           return temp.getElement();
       }
      
       else {
           DoubleNode<T> temp = tail;
          
           tail = tail.getPrev();
           tail.setNext(null);
           temp.setPrev(null);
          
           count--;
          
           return temp.getElement();
       }
   }

   @Override
   public T removeLast() throws EmptyCollectionException {
       // TODO Auto-generated method stub
       DoubleNode<T> temp;
       if(isEmpty())
           throw new EmptyCollectionException(getClass().getName());
       else if (head == tail) {
           temp = head;
           head = tail = null;
          
           count--;
          
           return temp.getElement();
       }
       else {
           temp = head;
          
          
           head = head.getNext();
           head.setPrev(null);
           temp.setNext(null);
          
           count--;
          
           return temp.getElement();
       }
   }

   @Override
   public T remove(T element) throws EmptyCollectionException, ElementNotFoundException {
       // TODO Auto-generated method stub
       if (isEmpty())
           throw new EmptyCollectionException(getClass().getName());
  
       DoubleNode<T> temp;
      
       DoubleNode<T> previous = null;
       DoubleNode<T> current = head;
       boolean found = false;
      
       while (current != null && !found) {
           if(element.equals(current.getElement()))
               found = true;
           else
           {
               previous = current;
               current = current.getNext();
           }
       }
      
       if(!found)
           throw new ElementNotFoundException(getClass().getName());
       if (size() == 1)
           head = tail = null;
       else if (current.equals(head)) {
           head.setPrev(current.getNext());
           head = current.getNext();
       }
       else if(current.equals(tail)) {
           tail = previous;
           tail.setPrev(previous);
           tail.setNext(null);
       }
       else
           previous.setNext(current.getNext());
      
       count--;
      
       return current.getElement();
      
   }

   @Override
   public T first() throws EmptyCollectionException {
       // TODO Auto-generated method stub
       if(isEmpty())
           throw new EmptyCollectionException(getClass().getName());
       else
           return tail.getElement();
   }

   @Override
   public T last() throws EmptyCollectionException {
       // TODO Auto-generated method stub
       if(isEmpty())
           throw new EmptyCollectionException(getClass().getName());
       else
           return head.getElement();
   }

   @Override
   public boolean contains(T target) {
       // TODO Auto-generated method stub
       DoubleNode<T> iterator = head;
      
       while(iterator != null && iterator.getElement().equals(target)) {
           if(iterator.getElement().equals(target))
               return true;
          
           iterator = iterator.getNext();
       }
       return false;
   }

   @Override
   public boolean isEmpty() {
       // TODO Auto-generated method stub
       return count == 0;
   }

   @Override
   public int size() {
       // TODO Auto-generated method stub
       return count;
   }
  
   @Override
   public String toString() {
       // TODO Auto-generated method stub
       if(isEmpty())
           return null;
       else {
           String result = "";
           DoubleNode<T> temp = head;
           while (temp != null) {
               result += temp.getElement() + " ";
               temp = temp.getNext();
           }
          
           return result;
       }
   }

}

EmptyCollectionException.java

public class EmptyCollectionException extends RuntimeException
{
    /**
     * Sets up this exception with an appropriate message.
     * @param collection the name of the collection
     */
    public EmptyCollectionException (String collection)
    {
        super ("The " + collection + " is empty.");
    }
}