Programming Assignment 1
I have provided a edu.gmu.cs.list.List<E>
interface that outlines basic functionality
of a list data structure. Your task is to develop a singly-linked list as a generic class that
uses the provided List
interface.
Some basic unit tests are provided to help check your implementation; however, passing these tests does not mean an implementation is correct. There are edge cases not checked by the provided unit tests and this assignment includes requirements not unit-testable.
I've provided a skeleton project for you to use as a starting point.
The assignment requires you to implement all the methods in
edu.gmu.cs.list.LinkedList<E>
.
Table of Contents
Download
The skeleton project may be downloaded here.
Due date
Your project, including all source code, must be submitted by midnight on October 4th to avoid late penalty. Late submissions will lose 10 points per day late.
Submissions are accepted over email.
Requirements
Required max running times | |
---|---|
both add methods | O(n) |
insert | O(n) |
remove | O(n) |
get | O(n) |
length | O(1) |
contains | O(n) |
findFirst | O(n) |
reverse | O(n) |
- Implement all methods from the
edu.gmu.cs.list.List<E>
interface - Check for bad parameters and throw
IndexOutOfBoundsException
exceptions in:insert(E item, int pos)
remove(int pos)
get(int pos)
- Throw
NoSuchElementException
incontains(E target)
if no element is in the list - Make sure to use
.equals
when testingE
objects - The
reverse
method should reverse the singly linked list in place- In place means that a second list does not need to be constructed
- Temporary variables can be used
Suggestions
- Use your own private methods to help you traverse the list or for other utility purposes
- Write your own unit tests to check your implementation
- Write a test application that uses your
LinkedList<E>
Project layout
The project has the following directory layout:
- LinkedList/
- src/
- all program source code
- build/ or out/
- all program class files
- lib/
- all project library dependencies
- dist/
- lib/
- classes packaged in JAR file
- lib/
- test/
- all test classes
- build.xml
- src/
Building and testing
The build.xml file is an ant build file. Ant is a Java build tool that can be used to simplify the process of building, testing, deploying, and running Java programs.
Ant may not already be installed on your computer but can be obtained from here. Some IDEs, such as Eclipse, may include ant. Please feel free to use whatever development tools and IDEs you prefer.
You will also need the JDK installed to compile your code. The JDK can be obtained from here.
To build all source files and create the JAR file:
ant dist
The dist
task is the default for our build file, so you may also run:
ant
If you would like to clean all compiled classes run:
ant clean
To run the unit tests:
ant test