Data Structures and Algorithms
Assignment
The objectives of this assignment are to:
1. Further enhance your knowledge and skill in Java.
2. Gain an understanding and experience with doubly linked lists.
3. Gain an understanding and experience using generics.
- Gain further experience in using Javadoc documentation.
5. Continue to practice good programming techniques.
Part I:
Create a doubly linked list class named LinkedItemList that implements the following interface:
/**
* An ordered list of items.
*/
public interface ItemList {
/**
* Append an item to the end of the list
*
* @param item - item to be appended
*/
public voidappendItem(E item);
/**
* Insert an item at a specified index position
*
* @param item - item to be inserted
* @param index - index position where to insert the item
* @throwIllegalArgumentException if index is < 0 or > no of items
*/
public void insertItemAt(E item, int index);
/**
* Remove all items from the list
*/
public void clear();
/**
* Return an item at a specified index
*
* @param index - index of the item to return
* @return the item at the specified index
* @throwIllegalArgumentExceptionif index is < 0 or >= no of items
*/
public E getItem(int index);
/**
* Return the index of the first occurrence of an item in the list.
*
* @return index of the first occurrence in the list, -1 if not found
*/
public intindexOf(Eitem);
/**
* Get an ItemIterator to iterate over items in the list.
*
* @return an ItemIterator to iterate over items in the list
*/
public ItemIteratoriterator();
/**
* Remove an item at a specified index
*
* @param index - index of the item to be removed
* @return the removed item
* @throw IllegalArgumentExceptionif index is < 0 or >= no of items
*/
public E removeItemAt(int index);
/**
* Remove the first occurrence of an item in the list.
*
* @item - item to be removed
* @return true if an occurrence of the item was found and removed,
* otherwise false
*/
public booleanremoveItem(Eitem);
/**
* Return the number of items currently in the list
*
* @return the number of items in the list
*/
public intgetNoItems();
}
/**
* An iterator over an ItemList
*/
public interface ItemIterator {
/**
* Return true if the iteration has more items
*
* @return true if the iteration has more items, otherwise false
*/
public booleanhasNextItem();
/**
* Return next item from iteration
*
* @return next item from iteration
* @throw NoSuchElementException if the iteration has no more items
*/
public E nextItem();
/**
* Remove last item from returned iteration
*
* @throw NoSuchElementException if no item has been returned or if
* the item has previously been deleted
*/
public voidremoveItem();
}
You will need the appropriate constructors. In addition, you may also implement other methods that may be useful for the assignment (where possible define code in just one place).
Part II:
Write a program to thoroughly test all of the methods of your LinkedItemList class. Once you are confident is it working correctly, proceed to part III.
Part III:
On the tomcat drive in cosc310 you will find an eclipse project called assmt2. On importing this project you will find a program CompanyReport which is similar to the Company and Bank projects. That is they use arrays for 1 to N relationships between business objects. Make the following modifications to CompanyReport to use ItemList and LinkedItemList.
1) Change the Company class to use LinkedItemList for your list of departments (instead of using an array). Define the type of the departments variable to be a ItemList. You will need to modify for loop accordingly.
2) Change Department to use LinkedItemList for the list of employees (instead of an array). Define the employees variable as a ItemList of Employees.
3) Remove the methodgetEmployee(int index) from Department. Instead add an ItemIteratorgetEmployees() method. It just calls the iterator method on the employees variable and returns its ItemIterator. Modify Department where needed to use getEmployees to iterate over the list of employees.
Additional Requirements:
1. Place ItemList and LinkedItemList into package edu.iup.cosc310.util
2. Provide a fast implementation for appendItem(), e.g., does not need to walk the list to get to the end.
3. Provide a fast implementation for getNoItems(), e.g., does not need to walk the list to count the number of items.