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:

SimpleLinkedList

The SimpleLinkedList class will, similar to SimpleArrayList, have:

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 (head == null, node = node.next, etc), 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 may differ slightly from the sample output, though they should be fairly close and proportionally similar.

After add:
Array List: 60
Linked List: 465

After sort:
Array List: 1015
Linked List: 17341

UML

UML