Description
This assignment will give you an opportunity to explore encapsulation, abstraction, containment, and parametric polymorphism in Java. In CS 5002, we identified a List as an abstract data type and implemented two versions that stored string data: a LinkedList backed by a ListNode, and an an ArrayList backed by a linear array. In this assignment, you will implement these as generic classes and interfaces. The following sections provide details of each.
List interface
Create a generic List interface that extends the Iterable interface to enable iteration over this list. The type parameter T represents the type of the list element. Here are the methods of the List interface.
Method name Return Type Parameters Description
add boolean T Appends the specified element to the end of this list. Returns true if the element was added.
add boolean int index, T element Inserts the specified element at the specified position in this list. Returns true if the element was added.
clear none none Removes all of the elements from this list.
get T int index Returns the element at the specified position in this list or null if index out of bounds.
indexOf int T element Returns the first index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
isEmpty boolean none Returns true if this list contains no elements.
lastIndexOf int T element Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
listIterator ListIterator none Returns a list iterator over the elements in this list. (See description below.)
remove T int index Removes the element at the specified position in this list. Returns the element removed or null if index is out of bounds.
set T int index, T element Replaces the element at the specified position in this list with the specified element. Returns the previous value or null if index is out of bounds.
size int none Returns the size of the list.
In addition to the iterator() method specified by the Iterable interface that returns an Iteratator for the list, the List interface also includes a listIterator() method that returns a ListIterator for the List.
The java.util.ListIterator interface extends the Iterator interface to provide additional iterator methods for a List, including previous() and hasPevious() for backward iteration, and nextIndex() and previousIndex() methods that return the index of the next and previous list element that would be returned. It also provides optional remove(), set() and add() methods for removing, and setting the current element and adding an element at the current location. See the java.util.ListIterator documentation for details
ArrayList and ArrayListIterator classes
Create a generic ArrayList class that implements List and uses an array as a backing store. The array should be extensible to ensure that there is always room to add another element. You are welcome to leverage the C array list and array list iterator code from the CS 5002.
Implement the ArrayListIterator class as a private nested class of ArrayList that implements the Java ListIterator interface. It is private because the class is not needed outside of ArrayList. You may, if you wish, implement the optional methods to add(), remove(), and set() list items based on the current iterator position in the list. Since ListIterator extends Iterator, both the iterator() and the listIterator() methods can return an instance of ArrayListIterator.
LinkedList, LinkedNode, and LinkedListIterator classes
Create a generic LinkedList class that implements List and uses an LinkedNode chain as a backing store. You are welcome to leverage the C doubly linked list, linked node, and linked list iterator code from the CS 5002.
Implement LinkedNode as a private static inner class of LinkedList to represent the linked node. This inner class is static because nodes do not require access to a LinkedList instance. It is private because the class is not needed outside of LinkedList.
Implement the LikedListIterator class as a private inner class of LinkedList that implements the Java ListIterator interface. It is private because the class is not needed outside of LinkedList. You may, if you wish, implement the optional methods to add(), remove(), and set() list items based on the current iterator position in the list. Since ListIterator extends Iterator, both the iterator() and the listIterator() methods can return an instance of LinkedListIterator.
Unit tests
Create JUnit unit test classes “ArrayListTest.java” and “LinkedListTest.java” that contain unit tests functions for the classes in this assignment.
