In this lab you are going to create a linked implementation of a list, and compare its performance to the array implementation that we created in class.
The file List.java contains an interface that defines all of the methods for list classes. Look at the file and read through the comments for the methods to make sure that you understand all of them. The file ArrayList.java contains a class that implements the List interface by using an array to store data. Look at the file and notice how generics are used. For this lab you should create a class called LinkedList that implements the List interface using links.
A class that implements a linked collection does not contain an array to store its data. Instead it contains a pointer to the first element in the list. Each element in the list then in turn has a pointer to the element after it in the list. To do this you will need to create a class LinkedListNode that has two instance variables, an object for the data of the particular node, and a LinkedListNode for the next element. When an object is added to the the LinkedList it is added to the beginning of the list by creating a new LinkedListNode. The node data is set to the object being added, and the next node is set to the first node of the of the LinkedList. The first element of the LinkedList is then set to the node that was just added.
Remember to code in small pieces! Every time you write a method you should test it. The file ListTest.java contains a program that will test the two add methods of the LinkedList class. It also requires that the toString method be implemented so that it creates a string in the same format as the ArrayList class. You should add code to this class to test your remove, get, and size methods. Proceed only when you are sure that your class is functioning properly.
So, which implementation do you think performs more quickly? The file GraphListTime.java contains a program that will plot the time it takes to complete various operations on array and linked implementations of lists. Run this program to verify if your conclusions about the performance of these implementations are correct.
To submit your code: Tar the files in your lab8 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab8. Be sure to name the tar file with your names, not lab8.tgz.