Description

Corrections/Amplification/Clarifications

•  You may use the array index [0] or not, as you wish.
•  I will not add null values to your list during testing. We would expect

A NullPointerException if we attempt to compare null to some array

element.

•  The array should not be made smaller in the clear() method. It should only

be resized to a smaller size from a delete method.

•  All of the remove methods should remove and return the indicated

element if it is in the list and return null if the element is not in the list.

The Project

For this assignment, you will write the ArrayLinearList class, an array-based

implementation of the LinearListADT interface (given below). A 'list' is a

sequence of values. 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.

Your implementation will be array-based. But the Linear List is unbounded. An

insertion should never fail as long a memory remains available on the computer.

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 LinearListADTinterface. Your project will consist of exactly the following

two files, both of which must be in a data_structures/ package:

 LinearListADT.java The linear list interface (provided below)

 ArrayLinearList.java Your implementation of this interface

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.

] IMPORTANT: The package organization is of critical importance. If your

project fails to compile during the grading process due to package errors,

your grade for this project will be zero.

The LinearListADT interface:

/* Your name

Your classic account number

*/

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;

// Adds the Object obj to the end of list.

public void addLast(E obj);

// Adds the Object obj to the beginning of list.

public void addFirst(E obj);

// Inserts the Object obj at the position indicated.

If there is an element at

// that location, all elements from that location to

the end of the list is

// shifted down to make room for the new insertion.

The location is based.

// If the location > size()+1 then a RuntimeException

is thrown. List elements

// must be contiguous.

public void insert(E obj, int location);

// Removes and returns the object located at the

parameter location (one-based).

// Throws a RuntimeException if the location does not

map to a valid position within the list.

public E remove(int location);

// 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 the first position.

public E remove(E obj);

// Removes and returns the parameter object obj in

the first position in the list if the list is not empty,

// null if the list is empty. The ordering of the list

is preserved.

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. The ordering of the list

is preserved.

public E removeLast();

// Returns the parameter object located at the

parameter location position (one based).

// Throws a RuntimeException if the location does not

map to a valid position within the list.

public E get(int location);

// Returns true if the parameter object obj is in the

list, false otherwise.

public boolean contains(E obj);

// Returns the one based location of the parameter

object obj if it is in the list, -1 otherwise.

// In the case of duplicates, this method returns the

element closest to position #1.

public int locate(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 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.

(position #1 first)

public Iterator<E> iterator();