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.

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 static int 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 resetCountAccess() 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, 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 IndexOutOfBoundsExeption will be thrown.

SimpleLinkedList

The SimpleLinkedList class will, similar to SimpleArrayList, have:

an accessCount variable,
a no-parameter constructor,
a resetCountAccess() method.
It will also have 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 IndexOutOfBoundsExeption will be thrown.
There will also be a private inner class Node<E> that will be used by the List.

Access Count

In your SimpleList implementations, whenever an element or field from the List is accessed, whether it is accessing an array (data[i]) or a Node (head == null, node = node.next, etc) or the size field, that Lists accessCount variable should be incremented. Do not count constructors or toString()

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 will differ slightly from the sample output, though they should be fairly close and proportionally similar.

After add:
Array List: 121
Linked List: 583

After sort:
Array List: 1973
Linked List: 19140