|
CSE 1030 - Assignment #7 - Linked-Lists in Java - Implementing the LinkedListOfData Collection
SC/CSE 1030 - Fall 2012 - Assignment #7
Linked-Lists in Java - Implementing the LinkedListOfData Collection
Linked-Lists are the most primitive of the tree-based data structures.
In this assignment you will implement a linked-List
of Data objects. An implementation for the Data class has been provided
(here: Data.java,
and the API is available here:
Data API).
For this assignment you will need to create two classes:
- LinkedListOfData.java
-
This class implements a collection of Data objects. The Data objects are
to be stored in a linked-list of your own implementation.
You may not use the Java API Collections to store the Data objects
(so no LinkedList<Data>, no List<Data>, etc.)
you have to implement your own linked list data structure to store the Data objects.
The API that you must implement is available here:
LinkedListOfData
Some notes:
-
The Data objects that are added to the LinkedListOfData class (in
LinkedListOfData.add(Data datum)) must be added to the head of
the list.
-
Additionally, you will also have to keep track of the number of Data objects being
held in the LinkedListOfData. The count of the number of nodes in the Linked-List
is made available to the user via the
LinkedListOfData.getDataObjectCount() function.
-
Your implementation must allow the user to store 'null' objects in the LinkedListOfData collection.
- LinkedListOfDataIterator.java
-
This class must implement the Iterator interface that has been provided
(the source code for the interface is here: Iterator.java,
and the API is available here:
Iterator API).
The API that you must impelement is available here:
LinkedListOfDataIterator
Some notes:
-
The LinkedListOfDataIterator must implement the provided Iterator interface.
-
When the LinkedListOfDataIterator object is created, it is given a pointer to the Node
at the head of the Linked-List, by the LinkedListOfData
object (see the constructor for the LinkedListOfDataIterator class).
The LinkedListOfDataIterator uses this pointer to return one Data object at a time through the
LinkedListOfDataIterator.next() function. To accomplish this, the
LinkedListOfDataIterator object will have to move the pointer along the nodes in the
linked-list each time that the user calls .next().
-
The LinkedListOfDataIterator.hasNext() function can figure-out whether
there are more nodes to return by checking whether the pointer points to a node, or to
null (it will only point to null once it has hit the end of the list.
To complete this assignment, you must do these things:
Implement the required two classes, matching the
details in the APIs:
LinkedListOfData
LinkedListOfDataIterator
You are responsible for defining and managing the data
members of these classes that you will need, and
for implementing the functions described in the API.
Include appropriate comments and Javadoc comments in your source code.
You should test your implementation using the a7.java program.
Submit your classes electronically before the deadline
using the submit command:
submit 1030 a7 LinkedListOfData.java LinkedListOfDataIterator.java
Some notes:
The source code for the Data class and Iterator interface have been provided for
you here:
Data.java,
Data API
Iterator.java,
Iterator API.
Note that you should not need to change this class and interface to complete this assignment.
You will find the following class useful for testing your code:
a7.java.
This program provides a simple command-line interface to
several tests to help you test your code.
Your source code should be well organised and documented.
Remember the Course's, Department's, and the University's
policies on academic honesty - do your own assignment yourself.
(Besides, doing it yourself is the only way to learn!)
This assignment is due on Friday November 16, at noon. Late
assignments will not be accepted.
Start Early - Don't leave your assignment to the last minute!
Remember that you can use the submit command more
than once - subsequent submissions will replace previous
submissions. So if you make a mistake, don't panic,
just fix it, and resubmit it (before the deadline).
Note that you do not need to submit both of the classes at once, you
can use the submit command to submit each Java file seperately, if
that is more convenient for you.
Additional information regarding the submit command can be
found by typing man submit at the command line.
Do not use the Type package, nor its earlier
incarnation, the york package.
Your programs must compile and run on the Prism computers.
Your grade will be a number from 0 to 10 - approximately one mark each for passing the tests in the a7.java program.
The breakdown is:
1 mark for creating an LinkedListOfData class that we can instantiate.
1 mark if we can insert some Data objects into the LinkedListOfData object.
1 mark if the LinkedListOfDataIterator handles the case where the LinkedListOfData object is empty.
1 mark for a working LinkedListOfDataIterator.
1 mark if the LinkedListOfData.add() function inserts new objects at the head of the list, and allows duplicates.
1 mark if the LinkedListOfData.removeHead() function works properly.
1 mark if the LinkedListOfData and LinkedListOfDataIterator objects properly handle a large amount of data.
1 mark if the LinkedListOfData and LinkedListOfDataIterator objects properly handle 'null' objects.
2 marks for coding style (nicely organised code with comments).
Have FUN!
|
|