York U: Redefine the Possible HOME | Current Students | Faculty & Staff | Research link: Future Students, Alumni & Visitors
Search »  
Department of Computer Science and Engineering
Home
Announcements
Course Calendar
Course Forum


Y graphic
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:

  1. 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.

  2. Include appropriate comments and Javadoc comments in your source code.

  3. You should test your implementation using the a7.java program.

  4. Submit your classes electronically before the deadline using the submit command:
    submit 1030 a7 LinkedListOfData.java LinkedListOfDataIterator.java



Some notes:

  1. 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.

  2. 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.

  3. Your source code should be well organised and documented.

  4. 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!)

  5. 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!

  6. 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.

  7. Do not use the Type package, nor its earlier incarnation, the york package.

  8. Your programs must compile and run on the Prism computers.

  9. 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).

  10. Have FUN!






graphic rule