For this assignment, you will create an implementation of the ArrayListADT interface (below). A 'list' is a sequence of values, which may include duplicates. The ordering of the items in the list is not specified but does matter and is in fact problem dependent. No insertion ever occurs at an arbitrary location. When an item is removed from the list, the ordering of the remaining elements in the list is unchanged. There may not be any empty or unused cells between the front and rear of the list.
Your implementation of the ArrayListADT offers a meaningful improvement over basic arrays for list-based operations. Inserting or removing an element at index [0] is a time-consuming operation for arrays. If you wish to insert an element at index [0] and the array is not empty, then you must shift all the existing elements out of the way before the insertion can occur. Similarly, if you remove the element at index [0] from a non-empty array, you must shift elements down to 'fill in the hole'. Your implementation must be able to insert or remove elements from either end of the array in constant time, with no shifting of elements necessary. A circular array strategy offers this capability. "Circular" is an abstraction; the underlying array doesn't form a circle but rather will be a standard linear array.
A solution to this problem can be found if you abandon the notion that the first element in the list must be at index [0]. Instead, you maintain a class level variables that hold the index of the 'front' and 'rear' of the list. The front and rear indices move independently, allowing insertion and deletion to happen without shifting anything. see image.
This list (in order) is: 4, 9, 12, 7, 8, 3, 6, 10. The 'front' and 'rear' indices simply wrap around when they run off the end.
We want to segregate our data structures and separate them from any application programs. Accordingly, you must place all data structures in a package named data_structures . Your ArrayLinearList class must implement the LinearListADT interface. Your project will consist of exactly the following two files, both of which must be in a data_structures/ package:
Both of the above files must go in package data_structures . Any driver/tester programs will go in the level above the data_structures subdirectory. Sample tester programs will be provided.
The LinearListADT interface:
package data_structures;
import java.util.Iterator;
import java.util.NoSuchElementException;
public interface LinearListADT< E> extends Iterable< E> {
public static final int DEFAULT_MAX_CAPACITY = 100;
/* Outputs “Front: indexFront Rear: indexRear”
*/
public void ends();
/* Adds the Object obj to the beginning of list and returns true if the list is not
* full.
* returns false and aborts the insertion if the list is full.
*/
public boolean addFirst(E obj);
/* Adds the Object obj to the end of list and returns true if the list is not full.
* returns false and aborts the insertion if the list is full.
*/
public boolean addLast(E obj);
/* Removes and returns the parameter object obj in first position in list if the list
* is not empty, null if the list is empty.
*/
public E removeFirst();
/* Removes and returns the parameter object obj in last position in list if the list
* is not empty, null if the list is empty.
*/
public E removeLast();
/* Removes and returns the parameter object obj from the list if the list contains
* it, null otherwise. The ordering of the list is preserved. The list may contain
* duplicate elements. This method removes and returns the first matching element
* found when traversing the list from first position.
* Note that you may have to shift elements to fill in the slot where the deleted
* element was located.
*/
public E remove(E obj);
/* Returns the first element in the list, null if the list is empty.
* The list is not modified.
*/
public E peekFirst();
/* Returns the last element in the list, null if the list is empty.
* The list is not modified.
*/
public E peekLast();
/* Returns true if the parameter object obj is in the list, false otherwise.
* The list is not modified.
*/
public boolean contains(E obj);
/* Returns the element matching obj if it is in the list, null otherwise.
* In the case of duplicates, this method returns the element closest to front.
* The list is not modified.
*/
public E find(E obj);
/* The list is returned to an empty state.
*/
public void clear();
/* Returns true if the list is empty, otherwise false
*/
public boolean isEmpty();
/* Returns true if the list is full, otherwise false
*/
public boolean isFull();
/* Returns the number of Objects currently in the list.
*/
public int size();
/* Returns an Iterator of the values in the list, presented in
* the same order as the underlying order of the list. (front first, rear last)
*/
public Iterator< E> iterator();
}