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.java
    └── TrainCar.java

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:

Using The TestProgram

First, I would highly recommend creating a main method in each class and incrementally developing. Here is an example for the MyArrayList class:

MyArrayList

This gives you more control over your code and will cut down the time you have to spend debugging.

When you are ready to try the testing we will be running for preliminary testing, run the main method provided in the TestProgram.

You will see the following output:

Usage: java TestProgram testNumber {-arraylist | -linkedlist}

This message shows you what to use for your Program Arguments in Eclipse or what to use on the command line. We have chosen to conform to the standards specified by Oracle.

For example: 0 -linkedlist will call the first test for MyLinkedList. Read the code to figure out what other arguments are valid.

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