Programming Assignment: Ordered Collection of Things using Linked List

Goal: To represent an ordered collection using a linked list

Problem Description

You will be creating an ordered collection class. You will be storing your things in a linked list.

$$ You may NOT use the Java library classes ArrayList or Vector or LinkedList or any other java collection class.

$$ You must implement your own linked list as explained below.

$$ No method in the collection class should print anything!!!!

$$ The name of your collection class should include the name of your Thing. For example, if your Thing is called Book, then your collection class should be called BookCollection. Alternatively, if your collection class has a natural group name, please use that. This will help with $$thinking$$ in objects. For example, a collection of books can be called a library.

$$ Differentiate this class from the array implemented class by adding Linked in the class name.

ThingNode Class

Implement a node class for your linked list. Name it after your Thing $($for example: McDonaldsNode$).$ Your node class should include the following:

$1.$ Two private instance variables:

$-$data of type $$Thing$.$ Do NOT use a generic node.

$-$link of type $$ThingNode$.$

$2.$ A constructor that takes two input parameters and uses them to initialize the two instance variables.

$3.$ Getters and Setters for the instance variables.

LinkedCollection Class

Implement a collection class of your things using a linked list. Your collection class must have the following characteristics:

$1.$ Include exactly one instance variable:

$-$head of type ThingNode

$2.$ Implement a no$-$argument constructor for your collection class.

$3.$ void insert$($Thing$)$: a method that takes one input parameter matching the type of your Thing and then inserts it in the collection class IN DESCENDING ORDER according to the search key instance variable. Simply add any duplicate Things. Do NOT attempt to sort the list or use a sorting algorithm. You must maintain the list in order by inserting the new element in the proper position.

$4.$ void delete$($Thing$)$: this method takes one input parameter of your type of Thing. The method then searches the collection for the first object that equals the input object and deletes its occurrence if found. After the item has been deleted, the list must still be maintained IN ORDER.

$5.$ int size$()$: a method that returns the number of objects in the collection.

$6.$ boolean isEmpty$()$ : a method that returns true if there are no objects in the collection, false otherwise.

$7.$ int indexOf$($Thing$)$: a method that returns the index of the first instance of Thing found in the collection. Returns $-1$ if not found. Recall that numbering starts at one for linked lists.

$8.$ int lastIndexOf$($Thing$)$: a method that returns the index of the last instance of Thing found in the collection. Returns $-1$ if not found.

$9.$ Thing grab$($int$)$: a method that returns the Thing located at the specified position in the list or null if position is not valid. Recall that the first element in the list is at position $1.$ This method does not remove the element from the list.

$10.$ boolean contains$($Thing$)$: this method takes one input parameter matching the type of your Thing. The method returns true or false based on whether the collection contains at least one Thing that is equal to the input parameter. Use the equals$()$method from your Thing class to determine if two objects are equal.

$11.$ String toString$()$: a method that returns a String representation of the collection that includes all elements that are stored in the collection. The output string must be nicely formatted in a tabular format, one Thing per line. toString$()$ will not print but rather will return a String. For example, a String representing a list of students $($in reverse order by name$)$ could be formatted as follows:

Name Age Registered

$-----------------------------------$

Reem $27$ true

Mohammed $25$ false

Maria $20$ true

Hanna $30$ true

$12.$ int countOccurrences$($Thing$)$: this method returns a count of the number of Things in the collection that are equal to the input parameter.

Driver Class

Create a driver class:

$$ Create an instance of your collection class

$$ Add $510$Things$$ to your collection class

$$ Verify that all methods work as expected