CSC1020 Homework 6

Overview

This will be the first of several assignments where you will be comparing the time complexity of different data structures. To do this, we are going to create some very basic implementations of an ArrayList and Linked List class and count the number of times the elements of the List are accessed to accomplish the same set of tasks.

The goal is to compare these two implementations and understand how their structures affect particular operations rather than to reproduce the exact behavior of java.util.ArrayList and java.util.LinkedList.

SimpleList

The SimpleList interface defines the public methods used by the implementing classes. Both of your Lists should implement this interface.

SimpleArrayList

The SimpleArrayList class will have an additional instance variable accessCount, initialized to zero, that will keep track of the number of element accesses that have been performed. In addition to overriding the abstract methods inherited from the SimpleList interface, it will also have:

• a no-parameter constructor,
• a getAccessCount() method that returns the current value of accessCount,
• a resetAccessCount() method to reset the accessCount variable back to zero,
• a private reallocate() method to increase the size of the backing array when needed. You must implement reallocate() without using Arrays.copyOf or System.arraycopy, as you will need to keep track of all of the element accesses,
• a private validateIndex() method that will verify the index passed in by the user is valid. If it is not, an IndexOutOfBoundsException will be thrown.

SimpleLinkedList

The SimpleLinkedList class will, similar to SimpleArrayList, have:

• an accessCount instance variable,
• a no-parameter constructor,
• a getAccessCount() method that returns the current value of accessCount,
• a resetAccessCount() method,
• a private getNode() method that will find and return a Node from the list at a given index,
• a private validateIndex() method that will verify the index passed in by the user is valid. If it is not, an IndexOutOfBoundsException will be thrown,
• a private static nested class Node<E> that will be used by the List.

Note: This deliberately simple linked-list implementation stores only a reference to the head of the list. Therefore, appending an element requires traversing the list. More complete linked-list implementations may maintain a tail reference, changing the performance of add().

Access Count

In your SimpleList implementations, whenever an element from the List is accessed using an index or a reference, whether it is accessing an array (data[i]) or a Node reference (head, node.next, etc.), that List's accessCount variable should be incremented.

You should also count accesses to list-management fields, such as size, when those fields are read or modified as part of a list operation. For example, incrementing size requires both reading and updating its value.

The purpose of the counter is to reveal the relative growth in work performed by the two implementations. Small differences in exactly how individual accesses are counted are acceptable as long as your counting is consistent and produces proportionally similar results.

Do not count accesses performed by:

• constructors,
• toString(),
• getAccessCount(), or
• resetAccessCount().

toString()

The toString() methods in both Lists are merely meant to be a convenience method to help you test and troubleshoot your implementation. You do not need to include access count incrementing here.

Tests

A test driver, sample data, and unit tests are included to verify your implementation. Note that your actual values may differ slightly from the sample output, though they should be fairly close and proportionally similar.

The important comparison is not the exact access-count total, but how the counts change as the same operations are performed on the two data structures.

Example output from the supplied test driver may look similar to:

After add:  Array List: 60    Linked List: 465
After sort: Array List: 1015  Linked List: 17341

Analysis Questions

After running the supplied test driver, answer the following questions:

1. Why does the difference between the two lists become much larger during the sort than during an individual get() or set() operation?
2. What effect would adding a tail reference to SimpleLinkedList have on the cost of repeatedly calling add()?
3. Based on your results, what would you expect to happen to the access counts if the size of the input approximately doubled?

UML