Programming Assignment #2
75 points
Due Date/Time
Your program is due in your edoras cssc40xx account Thursday, March 11th at 11:59 p.m.
When your program is ready for grading, put the assignment files into the ~/handin/p2 directory as
illustrated here:
~/handin/p2/
[Link] [Link] [Link]
No late assignments accepted. Early submissions receive extra credit.
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;
• [Link] The linear list interface (provided below)
• [Link] Your implementation of the interface
• [Link] Your stack implementation that uses LinearList.
• [Link] 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 [Link], [Link], [Link] source code files into
your handin/p2 subdirectory. Do not put the [Link] 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 [Link];
import [Link];
import [Link];
public interface LinearListADT<E extends Comparable<E>> extends Iterable<E> {
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<E> 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<E> 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<E> 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 [Link] (the default
package). You may not use any data structure or class in [Link] other than those specified. You will
need:
• [Link]
• [Link]
• [Link]
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
[Link] [Link] [Link]
Early Programs:
Early programs will be accepted with a bonus of 5 points per day for up to two days before the due date.
The submission date will be determined by the timestamp of your file on edoras. This program is due
Thursday by midnight. If your program timestamp is any time on or before, March 9th, your will receive
a 10 point bonus, and if your program timestamp is any time Wednesday, February10yh, your will
receive a 5 point bonus.
Cheating Policy:
There is a zero-tolerance policy on cheating in this course. You are expected to complete all
programming assignments on your own. Collaboration with other students in the course is not permitted.
You may discuss ideas or solutions in general terms with other students, but you must not exchange
code. Nor may you copy code from former CS310 students, nor the Internet. You must be able to
produce code on your own--otherwise no one will ever hire you. Remember that you can get help from
the ISAs or from me. This is not cheating but is in fact encouraged.
I will examine your code carefully. Anyone caught cheating on a programming assignment or on an
exam will receive an "F" in the course, and a referral to Judicial Procedures.
Checking that everything works on edoras
Use a sandbox directory, like this:
~/sandbox/p2/
[Link]
~/sandbox/p2/data_structures
[Link]
[Link]
[Link]
[Link]
Compile from ~/sandbox/p2 directory:
[cssc0000@edoras p2]$ javac [Link]
[cssc0000@edoras p2]$ java Driver
When ready, copy your three files into the handin/p2 folder. Assuming you execute these commands
from ~/sandbox/p2, to copy using commands:
Go to the sandbox:
[cssc0000@edoras ~]$ cd ~/sandbox/p2
Create the destination folder if you haven’t already:
[cssc0000@edoras p2]$ mkdir ~/handin/p2
Now copy all data structure files from ~/sandbox/p2/data_structures/ directory to ~/handin/p2:
[cssc0000@edoras p2]$ cp data_structures/*.java ~/handin/p2/
Now remove the unneeded interface file from ~/handin/p2:
[cssc0000@edoras p2]$ rm ~/handin/p2/[Link]
Verify the correct files are in ~/handin/p2:
[cssc0000@edoras p2]$ ls ~/handin/p2/
[Link] [Link] [Link]