$24
Assignment 3 Solution
Objectives
Practice implementing an interface in Java
Practice with a Node class and references
Practice reading and understanding specification
Exposure to more complete testing
Introduction
This assignment introduces the idea of a Container – a data structure that is used to store a collection of items. For simplicity, our containers will only store integers. Later in the course we will encounter a mechanism that Java supports to store items of an arbitrary type: generics.
Your task is to implement the interface described in the file IntegerList.java using a doubly-linked list in the file IntegerLinkedList.java.
Quick Start:
Download a3tester.java, IntegerLinkedList.java, IntegerList.java, IntegerNode.java and IntegerArrayList.java
Read IntegerList.java carefully
Compile and run the test program a3tester.java
If no errors reported by test program, see the Grading section of this document
Implement one of the methods in IntegerLinkedList.java
goto 3
1 of 5
CSC 115
Understanding the test program: a3tester.java
You've been given a program that will test your implementation of the IntegerList interface.
One of the first things you should do after downloading the source code files is to run the test program.
Compile the test program by typing:
javac a3tester.java
Run the test program by typing:
java a3tester
You should see the following output:
Basic testing of size, addFront, addBack, get Failed test: 0 at line 55
The tester is reporting that your implementation is failing the very first test. This is hardly surprising, since you haven't written any code yet!
The tester is written to be able to test both an array implementation (provided to you in the file IntegerArrayList.java) and the linked list implementation that you are required to implement
in IntegerLinkedList.java
To see the result of testing your instructor's array-based solution, type:
java a3tester array
You will see there are 36 test cases (numbered 0 to 35), and the array based solution passes them all.
Your goal is to make your linked list based implementation pass all 36 test cases.
Bonus:
I will give out a chocolate bar for the first student to report:
a bug that is found in IntegerArrayList.java
an ambiguity in IntegerList.java
To claim your chocolate bar, send an email to jcorless@uvic.ca with the bug (include a test case that demonstrates the bug) or the ambiguity (include a fix to the specification).
2 of 5
CSC 115
Linked Lists
Your implementation must be a doubly-linked list that maintains both a head and a tail reference.
You've also been provided with a node class (IntegerNode.java) that includes a prev and next references.
If your implementation is correct, the in-memory picture of list1 containing {1,2,3} will be:
list1
IntegerLinkedList
IntegerNode
IntegerNode
IntegerNode
head
1
2
3
count: 3
tail
3 of 5
CSC 115
What to do
All the coding you have to do in this assignment will be contained in the file named IntegerLinkedList.java. This code already compiles and runs, it just doesn't do anything useful without your additional code.
You should be sure that you understand the idea of a linked list and the purpose of the node class before you start writing code. There will be examples and code regarding linked lists in the labs and lectures this week to help your understanding.
It is very helpful to draw pictures of what a list looks like before and after an operation (such as addFront). This will assist you in understanding what your intended code (i.e., what you are writing) is trying to accomplish in modifying the structure of some existing list.
You must do your development incrementally, that is, implement one method and then re-run the test program.
In order to pass the first set of test cases, you will have to implement the methods: size, addFront, addBack, and get.
Once you've completed those methods, move on to toString and clear.
Then implement addAt and removeAt. These will be the most difficult to complete.
Finally, implement remove.
4 of 5
CSC 115
Submission
Submit your IntegerLinkedList.java using Connex. When doing this, please be sure you complete the last “confirm your submission” step; do not just save a draft assignment submission.
We remind you that it is OK to talk about your assignment with your classmates, and you are encouraged to design solutions together. However, each student must implement their own solution. Sharing of code is not permitted. (We will use code-similarity software tools on submitted assignments.)
Grading
If you submit something that does not compile, you will receive a grade of 0 for the assignment. It is your responsibility to make sure you submit the correct files.
You must implement doubly-linked lists with a head and tail reference. Your implementation of addFront and addBack must be O(1).
Requirement
Marks
You submit something that compiles
1
Your code passes the first set of test cases:
3
“Basic testing of size, addFront, addBack, get” (tests 0 to 6, inclusive)
Your code passes the second set of test cases:
2
“Testing toString() and clear” (tests 7 to 11, inclusive)
Your code passes all the remaining test cases (tests 12 to 35, inclusive)
6
Total
12
And to emphasize a point about the above guidelines – in order to obtain a passing grade on the assignment, you must at least satisfy the first three requirements by passing all of their test cases.
