MyList.java

 

import java.util.Iterator;

public interface MyList {
   /**
    * Returns the number of elements in this list.
    * @return the number of elements in this list
    */
   int size();

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

   /**
    * Appends the specified element to the end of this list.
    * @param element  element to be appended to this list
    * @return true
    */
   boolean add(E element);

   /**
    * Returns the element at the specified position in this list.
    * @param index  index of the element to return
    * @return       the element at the specified position in this list
    * @throws       IndexOutOfBoundsException - if the index is out of range
    *               (index < 0 || index >= size())
    */
   E get(int index);

   /**
    * Replaces the element at the specified position in this list with the
    * specified element.
    * @param index    index of the element to return
    * @param element  element to be stored at the specified position
    * @return  the element at the specified position in this list
    * @throws  IndexOutOfBoundsException - if the index is out of range
    *          (index < 0 || index >= size())
    */
   E set(int index, E element);

   /**
    * Removes all of the elements from this list.
    */
   void clear();

   /**
    * Returns an iterator over the elements in this list in proper sequence.
    * @return an iterator over the elements in this list in proper sequence
    */
   Iterator iterator();

   /***************************************************************************
    * Signatures below this line are for homework. Implement the methods in
    * both MyArrayList and MyLinkedList.
    **************************************************************************/

   /**
    * Returns a string representation of the list. The string will begin with
    * a '[' and end with a ']'. Inside the square brackets will be a comma-
    * separated list of values, such as [Brian, Susan, Jamie].
    * @return a string representation of the list
    */
   @Override
   String toString();

   /**
    * Inserts the specified element at the specified position in this list.
    * Shifts the element currently at that position (if any) and any subsequent
    * elements to the right (adds one to their indices).
    * @param index    index at which the specified element is to be inserted
    * @param element  element to be inserted
    * @throws IndexOutOfBoundsException if the index is out of range
    *         (index < 0 || index > size())
    * The exception message must be:
    * "Index: " + index + ", list size: " + size
    */
   void add(int index, E element);

   /**
    * Removes the element at the specified position in this list.
    * @param index  the index of the element to be removed
    * @return the element that was removed from the list
    * @throws IndexOutOfBoundsException if the index is out of range
    *         (index < 0 || index >= size())
    * The exception message must be:
    * "Index: " + index + ", list size: " + size
    */
   E remove(int index);

   /**
    * Returns the index of the first occurrence of the specified element in
    * this list, or -1 if this list does not contain the element. More
    * formally, returns the lowest index i such that Objects.equals(o, get(i)),
    * or -1 if there is no such index.
    * @param element element to search for
    * @return the index of the first occurrence of the specified element in
    * this list, or -1 if this list does not contain the element
    */
   int indexOf(E element);

   /**
    * Returns an array of indexes of each occurrence of the specified element
    * in this list, in ascending order. If the specified element is not found,
    * a non-null empty array (not null) is returned.
    * @param element element to search for
    * @return an array of each occurrence of the specified element in this
    * list
    */
   int[] indexesOf(E element);

   /**
    * Reverses the data in the list.
    * For MyArrayList, the data inside the underlying array is moved. For
    * MyLinkedList, the tail must become the head, and all the pointers are
    * reversed. Both implementations must run in Theta(n).
    */
   void reverse();
}
 

 

MyArrayList.java

 

import java.util.Iterator;

public class MyArrayList implements MyList {
   /**
    * Default initial capacity.
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * The size of the ArrayList (the number of elements it contains).
    */
   private int size;

   /**
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer.
    */
   Object[] elementData; // non-private to simplify nested class access

   /**
    * Constructs an empty list with the specified initial capacity.
    * @param  initialCapacity  the initial capacity of the list
    * @throws IllegalArgumentException if the specified initial capacity
    *         is negative
    */
   public MyArrayList(int initialCapacity) {
       if (initialCapacity < 0) {
           throw new IllegalArgumentException("Illegal Capacity: " +
                   initialCapacity);
       }
       this.elementData = new Object[initialCapacity];
   }

   /**
    * Constructs an empty list with an initial capacity of ten.
    */
   public MyArrayList() {
       this.elementData = new Object[DEFAULT_CAPACITY];
   }

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

   /**
    * Returns true if this list contains no elements.
    * @return true if this list contains no elements
    */
   public boolean isEmpty() {
       return size == 0;
   }

   /**
    * Appends the specified element to the end of this list.
    * @param element  element to be appended to this list
    * @return true
    */
   public boolean add(E element) {
       if (size + 1 > elementData.length) {
           Object[] newData = new Object[size * 2 + 1];
           for (int i = 0; i < size; i++) {
               newData[i] = elementData[i];
           }
           elementData = newData;
       }
       elementData[size++] = element;
       return true;
   }

   /**
    * Returns the element at the specified position in this list.
    * @param index  index of the element to return
    * @return       the element at the specified position in this list
    * @throws       IndexOutOfBoundsException - if the index is out of range
    *               (index < 0 || index >= size())
    */
   public E get(int index) {
       if (index < 0 || index >= size) {
           throw new IndexOutOfBoundsException(
                   "Index: " + index + ", list size: " + size);
       }
       return (E)elementData[index];
   }

   /**
    * Replaces the element at the specified position in this list with the
    * specified element.
    * @param index    index of the element to return
    * @param element  element to be stored at the specified position
    * @return  the element at the specified position in this list
    * @throws  IndexOutOfBoundsException - if the index is out of range
    *          (index < 0 || index >= size())
    */
   public E set(int index, E element) {
       if (index < 0 || index >= size) {
           throw new IndexOutOfBoundsException(
                   "Index: " + index + ", list size: " + size);
       }
       E oldValue = (E)elementData[index];
       elementData[index] = element;
       return oldValue;
   }

   /**
    * Removes all of the elements from this list.
    */
   public void clear() {
       // clear to let GC do its work
       for (int i = 0; i < size; i++) {
           elementData[i] = null;
       }
       size = 0;
   }

   /**
    * Returns an iterator over the elements in this list (in proper
    * sequence).
    *
    * The returned list iterator is fail-fast -- modification of the elements
    * is not permitted during iteration.
    */
   public Iterator iterator() {
       return new ListItr();
   }

   private class ListItr implements Iterator {
       private int current;

       ListItr() {
           current = 0;
       }

       @Override
       public boolean hasNext() {
           return current < size;
       }

       @Override
       public E next() {
           return (E)elementData[current++];
       }

       @Override
       public void remove() {
           throw new UnsupportedOperationException();
       }
   }
}
 

MyLinkedList.java

import java.util.Iterator;

public class MyLinkedList implements MyList {
   private Node head, tail;
   private int size;

   /**
    * Constructs an empty list.
    */
   public MyLinkedList() {
       head = tail = null;
       size = 0;
   }

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

   /**
    * Returns true if this list contains no elements.
    * @return true if this list contains no elements
    */
   public boolean isEmpty() {
       return size == 0;
   }

   /**
    * Replaces the element at the specified position in this list with the
    * specified element.
    * @param index    index of the element to return
    * @param element  element to be stored at the specified position
    * @return  the element at the specified position in this list
    * @throws  IndexOutOfBoundsException - if the index is out of range
    *          (index < 0 || index >= size())
    */
   public E set(int index, E element) {
       if (index < 0 || index >= size) {
           throw new IndexOutOfBoundsException(
                   "Index: " + index + ", list size: " + size);
       }
       Node p = head;
       for (int i = 0; i < index; i++, p = p.next);
       E oldElement = p.element;
       p.element = element;
       return oldElement;
   }

   /**
    * Returns the element at the specified position in this list.
    * @param index  index of the element to return
    * @return       the element at the specified position in this list
    * @throws       IndexOutOfBoundsException - if the index is out of range
    *               (index < 0 || index >= size())
    */
   public E get(int index) {
       if (index < 0 || index >= size) {
           throw new IndexOutOfBoundsException(
                   "Index: " + index + ", list size: " + size);
       }
       Node p = head;
       for (int i = 0; i < index; i++, p = p.next);
       return p.element;
   }

   /**
    * Appends the specified element to the end of this list.
    * @param element  element to be appended to this list
    * @return true
    */
   public boolean add(E element) {
       Node n = new Node(element);
       if (head == null) {
           head = tail = n;
       } else {
           tail.next = n;
           tail = n;
       }
       size++;
       return true;
   }

   /**
    * Removes all of the elements from this list.
    */
   public void clear() {
       head = tail = null;
       size = 0;
   }

   public Iterator iterator() {
       return new ListItr();
   }

   private class ListItr implements Iterator {
       private Node current;

       ListItr() {
           current = head;
       }

       @Override
       public boolean hasNext() {
           return current != null;
       }

       @Override
       public E next() {
           E element = current.element;
           current = current.next;
           return element;
       }

       @Override
       public void remove() {
           throw new UnsupportedOperationException();
       }
   }

   private class Node {
       Node next;
       E element;

       public Node(E element) {
           this.element = element;
       }
   }
}
 

 

Please use MyList interface as the basis for the MyArrayList and MyLinkedList implementations.

There are 6 new methods in the MyList interface. You need to implement them in MyArrayList.java and MyLinkedList.java. /** * * Returns a string representation of the list. The string will begin with a'' and end with a ']'. Inside the square brackets will be a separated list of values, such as [Brian, Susan, Jamie]. comma- * @return a string representation of the list. @Override String toString(); /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any subsequent * elements to the right (adds one to their indices). * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException if the index is out of range (index < 0 || index > size() ) * The exception message must be: * */ " " "Index: + index + ", list size: + size void add (int index, E element); /** * Removes the element at the specified position in this list. * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException if the index is out of range * (index < 0 || index >= size()) * The exception message must be: * "Index: " + index + " * 1 E remove (int index); /** list size: " + size * * Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More * formally, returns the lowest index i such that Objects.equals (o, get(i)), * or -1 if there is no such index. * @param element element to search for * @return the index of the first occurrence of the specified element in