After completing this assignment the student should be able to,
For this assignment you are given the following Java source code files:
CSE205_Assignment02.java (This file is complete – you will make no changes to this file)
MyListIterator.java (This file is complete – you will make no changes to this file)
MyList.java (This file is complete – you will make no changes to this file)
MyArrayList.java (you must complete this file)
MyLinkedList.java (you must complete this file)
The specifications for the files are given below (including the UML diagram on the following page).
Special requirements:
All MyList Concrete Classes
1. add method
a. Appends new item to end of list. For example: given the list {1, 2, 3} and an instruction to add( 99), the result would be this {1, 2, 3, 99}.
2. insertAt method
a. Makes a place at the specified index by moving all items at this index and beyond to the next larger index. For example: given the list {1, 2, 3} and an instruction to insertAt(1, 99), the result would be this {1, 99, 2, 3}.
b. Throws a NoSuchElementException if the specified index is less than 0 or greater than or equal to size.
3. removeAt method
a. Removes the element at the specified index and moves all elements beyond that index to the next lower index. For example: given the list {1, 2, 3} and an instruction to removeAt(1), the result would be this {1, 3}.
b. Throws a NoSuchElementException if the specified index is less than 0 or greater than or equal to size.
4. at method
a. Returns the item at the specified index. For example: given the list {1, 2, 3} and an instruction to at(1), the return value would be 2.
b. Throws a NoSuchElementException if the specified index is less than 0 or greater than or equal to size.
5. size method
a. Returns the number of elements currently stored in the list
6. getIterator method
a. returns a MyListIterator object for this list initialized to the start of this list
MyArrayList
1. This concrete class will store its elements in an array of Objects. The initial capacity of this array will be 16 elements. Since an array is a fixed size structure, you may need to allocate a new array with increased capacity in order to accommodate adding new elements. For this purpose you must implement the ensure capacity method.
2. ensureCapacity method
a. This method will take an int minCapacity as an argument.
b. If minCapacity is less than current size, then simply return without taking any action.
c. If minCapacity is less than 16 then the new capacity should be 16.
d. This method will allocate a new array of Objects with the new capacity
i. Then copy over all elements from the old array to the new array
ii. Then store the new array in the private array variable for this instance
3. add method
a. If the current size is equal to the current capacity, then this method will call the ensureCapacity method with the argument (capacity * 2) before adding the new element.
MyLinkedList
1. This concrete class will store its elements in Node objects. Each Node object has a data variable that stores the element and a next variable that stores a reference to the next Node object in the list. Each instance has a Node variable called head. When size is 0 then head is null. When size is not 0 then head is a reference to the first Node object. For each Node object in the list, if this Nodes next is null then this is the last node in the list.
2. add and insertAt methods
a. these methods will construct a new Node object whos data is the element to be added, and place this node appropriately into the list.
UML Class Diagram see image.