Implementing Data Structures

Objectives

  • Gain a deeper understanding of ArrayList and LinkedList data structures.

  • Practice method and constructor chaining so that you do not repeat code and effort.

  • Create test cases to verify method correctness.

Getting Started

Create a new Java project called P6 and import Lists-starter.jar.

Your directory should look like this:

P6/
└── src
    ├── Debug.java
    ├── IArrayList.java
    ├── ILinkedList.java
    ├── IList.java
    ├── MyArrayList.java
    ├── MyLinkedList.java
    ├── TestProgram
    └── TrainCar

The TestProgram class creates and tests either an ArrayList or LinkedList, depending on the command line parameter. Both are lists of TrainCar objects.

The Debug class is included to help you debug this assignment, and is used to implement the printDebug methods in both data structures. The other files are interface files that implement the inheritance hierarchy shown in the following UML diagram:

UML
Implementing an ArrayList

Use the javadoc to implement all of the methods inherited from IList and IArrayList in the MyArrayList class. Test using the supplied (but incomplete) test program and your own test code. Some automated grading will also be supplied.

Tip
 When calling remove() the index must be between 0 and listSize-1. However, when calling add(), the allowable range for the index is between 0 and listSize, since the caller may be trying to add a new entry to the end of the ArrayList. When the index is out of range throw an IndexOutOfBoundsException.
Implementing a LinkedList

The underlying data structure for a LinkedList uses the inner class Node:

  • The Node class consists of an element of type E, and a reference to the next Node for a singly-linked list

    • The Node class can also hold a second reference to the previous Node for doubly-linked list.

  • A constructor that takes the element and makes a Node with a null reference is useful.

    • Because you had the opportunity to implement a singly-linked list is lab, we encourage you to make a doubly-linked list. Either one will work, but the extra credit depends on a doubly-linked list data structure.

A number of corner cases exist with LinkedList. These are the most important:

  • Adding an element to an empty list.

  • Removing an element from a list with one element

  • Iterating through the LinkedList when the LinkedList is empty.

Use the javadoc to implement all of the methods inherited from ListInterface and LinkedListInterface in the MyLinkedList class. Some automated grading will also be supplied. Test using the supplied (but incomplete) test program and your own test code. Your code should behave exactly like Java’s implementation of a LinkedList.

In order to return a ListIterator, you must implement the hasNext(), next(), nextIndex(), hasPrevious(), previous(), and previousIndex() methods. This is extra credit, and while not required, encouraged. We have provided a visual aid to help you gain a better understanding of the problem.

Documentation

Our documentation matches the Oracle documentation with a few additional hints. The only difference is that your code only needs to generate the IndexOutOfBoundsException, and no others. The Oracle documentation for ArrayList and LinkedList the ListIterator interface are linked below:

Specifications

Your program must meet the following specifications:

  • Work on your own, as always.

  • You must submit P6.jar which includes MyArrayList.java and MyLinkedList.java.

  • Assignments should be implemented using Java 1.8.

  • Make sure your code runs on machines in the COMCS120 lab.

  • Submit your program to the Checkin tab.

  • Read the syllabus for the late policy.

  • We will be checking programs for plagiarism, so please don’t copy from anyone else.

Grading Criteria

  • 100 points for perfect submission.

  • 0 points for no submission, will not compile, submitted class file, etc.

  • Preliminary Tests:

    • arrayTestSanity: sanity test of adding and removing elements to MyArrayList. (5 points)

    • arrayTestReallocation: verifies simple reallocation when the MyArrayList exceeds capacity. (6 points)

    • linkedTestSanity: sanity test of adding and removing elements to MyLinkedList. (5 points)

    • linkedTestIterator: verifies your implementation of ListIterator in MyLinkedList. (10 points)

  • Final Tests:

    • arrayTestAdd: verifies add(E e) method and add(int index, E e) method to insert elements in the list. (4 points)

    • arrayTestRemove: verifies remove(Object o) method and remove(int index) method to delete elements from the list. (4 points)

    • arrayTestRemoveRange: verifies removeRange(int fromIndex, int toIndex) method to delete elements from a range (3 points)

    • arrayTestGet: verifies get(int index) method to retrieve elements from the list. (5 points)

    • arrayTestSet: verifies set(int index, E e) method to replace elements in the list. (5 points)

    • arrayTestContains: verifies contains(Object o) method returns whether an element belongs to the list. (5 points)

    • arrayTestIndexOf0: verifies indexOf(Object o) which returns the first index of the object in the list. (4 points)

    • arrayTestIndexOf1: verifies lastIndexOf(Object o) which returns the last index of the object in the list. (4 points)

    • arrayTestSizeAndEmpty: verifies size() method which returns the size of the list and the isEmpty() method which tests whether the list is empty. (3 points)

    • arrayTestExceptions: Verifies IndexOutOfBounds exception. (5 points)

    • linkedTestAdd: verifies add(E e) method and add(int index, E e) method to insert elements in the list. (4 points)

    • linkedTestRemove: verifies remove(Object o) method and remove(int index) method to delete elements from the list. (4 points)

    • linkedTestRemoveRange: arrayRemoveRange: verifies removeRange(int fromIndex, int toIndex) method to delete elements from a range (3 points)

    • linkedTestGet: verifies get(int index) method to retrieve elements from the list. (5 points)

    • linkedTestSet: verifies set(int index, E e) method to replace elements in the list. (5 points)

    • linkedTestContains: verifies contains(Object o) method returns whether an element belongs to the list. (5 points)

    • linkedTestIndexOf0: verifies indexOf(Object o) which returns the first index of the object in the list. (4 points)

    • linkedTestIndexOf1: verifies lastIndexOf(Object o) which returns the last index of the object in the list. (4 points)

    • linkedTestSizeAndEmpty: verifies size() method which returns the size of the list and the isEmpty() method which tests whether the list is empty. (3 points)

    • linkedTestExceptions: verifies IndexOutOfBounds exception. (5 points)

Important
 Submit P6.jar to Checkin