The Assignment

For this assignment, you will implement the interface from program #1 (LinearListADT) but with a doubly linked list rather than an array. Your implementation must be named LinearList. Additionally, you will write a Stack and a Queue, which you will build with your LinearList class via composition.

We want to segregate our data structures and separate them from any application programs. Accordingly, for development of your program, you must place all data structures in a subdirectory (package) named data_structures. Your LinearList class must implement the LinearListADT interface. Your project will consist of exactly the following four files, all of which must use package data_structures;

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

• LinearList.java Your implementation of the interface

• Stack.java Your stack implementation that uses LinearList.

• Queue.java Your queue implementation that uses LinearList.

Submitting Your Assignment

Since this is programming assignment #2, your source code must go in handin/p2. Before submitting your files, verify that your program runs correctly on edoras by using a “sandbox” area to build and test your work.

Before the due date, place your LinearList.java, Stack.java, Queue.java source code files into your handin/p2 subdirectory. Do not put the LinearListADT.java interface in handin/p2. I will use my copy of the interface to compile your program.

IMPORTANT: Do not create any data_structures folder anywhere within handin/; your source code files go directly in the handin/p2 folder. After the due date and you have submitted the assignment, do NOT edit the file as this will modify the file timestamp. If the file is in the wrong directory, an “mv” (move) command can be used to put it where it should be without changing the timestamp.

 

The LinearListADT interface

IMPORTANT: The signature of the interface is not the same as with the first program. You

MUST use this interface, not the one you used for the first assignment.

 

 

/* Your name

Your cssc account number

*/

package data_structures; import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.ConcurrentModificationException;

 

public interface LinearListADT> extends Iterable {

 

public static final int DEFAULT_MAX_CAPACITY = 100;

 

/* 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 iterator();

 

}

 

 

Required methods for your Queue class are:

/*inserts the object obj into the queue

*/

public void enqueue(E obj)

 

/* removes and returns the object at the front of the queue

*/

public E dequeue()

 

/* returns the number of objects currently in the queue

*/

public int size()

 

 

/* returns true if the queue is empty, otherwise false

*/

public boolean isEmpty()

 

/* returns but does not remove the object at the front of the queue

*/

public E peek()

 

/* returns true if the Object obj is in the queue

*/

public boolean contains(E obj)

 

/* returns the queue to an empty state

*/

public void makeEmpty()

 

/* removes the Object obj if it is in the queue and

* returns true, otherwise returns false.

*/

public boolean remove(E obj)

 

/* returns an iterator of the elements in the queue. The elements

* must be in the same sequence as dequeue would return them.

*/

public Iterator iterator()

 

 

 

 

Required methods for your Stack class are:

 

/* inserts the object obj into the stack

*/

public void push(E obj)

 

/* pops and returns the element on the top of the stack

*/

public E pop()

 

/* returns the number of elements currently in the stack

*/

public int size()

 

/* return true if the stack is empty, otherwise false

*/

public boolean isEmpty()

 

/* returns but does not remove the element on the top of the stack

*/

public E peek()

 

/* returns true if the object obj is in the stack,

* otherwise false

 

*/

public boolean contains(E obj)

 

/* returns the stack to an empty state

*/

public void makeEmpty()

 

/* removes the Object obj if it is in the stack and

* returns true, otherwise returns false.

*/

public boolean remove(E obj)

 

/* returns a iterator of the elements in the stack. The elements

* must be in the same sequence as pop() would return them.

*/

public Iterator iterator()

 

 

Additional Details

The behavior of your LinearList must be identical to the ArrayLinearList from program #1.

As with program #1, the addFirst/addLast/removeFirst/removeLast methods must be O(1), which means a doubly linked list is required.

Your LinearList class will have only a no-argument constructor, since linked lists are never 'full'.

You may import only classes needed for the Iterators. You may use any class in java.lang (the default package). You may not use any data structure or class in java.util other than those specified. You will need:

• java.util.Iterator

• java.util.NoSuchElementException

• java.util.ConcurrentModificationException

Every class file must begin with your name and edoras class account number.

Each method should be as efficient as possible. For example, your size() method should not loop down the linked list and count the elements.

Your project must compile and run on edoras to receive credit for the assignment. For grading, your file will be copied from your handin/p2 folder to my account. The project layout will be recreated, and then compiled and run. Watch your package structure! Any project that fails to compile will receive a zero.

Here is an example of the directory structure for this program

[cssc0000@edoras ~]$ ls handin/p2 LinearList.java Queue.java Stack.java

This assignment has been answered 3 times in private sessions.