Hands On Java Lab 12 Exercise Lab 12: Lists and Performance Introduction We have seen that an array provides one means of storing a sequence of values. Java provides a more abstract set of methods for interacting with a container implemented in an interface named List. An interface specifies the prototypes for a set of methods but not the implementation. While no instances can be made of an interface (it has no state information or method implementations) we can use it as a type name. For example, we can declare any variable to be of the type List and set that variable to an instance of any class that implements the List interface. Some of the methods that the List interface requires of a class are: public int size() public boolean isEmpty() public boolean contains(Object o) public boolean add(Object o) public boolean remove(Object o) public void clear() public boolean equals(Object o) public Object get(int index) public Object set(int index, Object element) public void add(int index, Object element) public Object remove(int index) public int indexOf(Object o) public int lastIndexOf(Object o) Java 1.2 provides three classes that implement the List interface. The ArrayList is an implementation that stores the elements in an array. If there are more elements than can fit into the array, a larger array will be allocated and the elements will copied into the new array. The LinkedList is an implementation that uses a linked list to store the elements. A linked list is implemented using nodes that contain links to next node in the list. The Vector is a collection class that has been in Java since version 1.0. It is similar to the ArrayList in its implementation in that it uses an array. In its original version, it used methods with different names from those in the List implementation. In version 1.2, Vector retains those methods as well as implementing the ones in the List interface. Today's exercise is to explore the differences between the ArrayList and LinkedList containers, to understand how they differ, and to identify the circumstances under which each should be used. To explore the differences, we have designed four timing experiments, in which we will: compare the time needed to append one value to the end of a ArrayList of length n against the time to append one value to the end of LinkedList of length n. compare the time needed to append n values to the end of an initially empty ArrayList against the time to append n values to the end of an initially empty LinkedList. compare the time needed to prepend n values to the beginning of an initially empty ArrayList against the time to prepend n values to the beginning of an initially empty LinkedList. compare the time needed to prepend one value to the beginning of a ArrayList of length n against the time to prepend one value to the beginning of LinkedList of length n. In each case, the value n will be entered from the keyboard. The Timer Class To measure the elapsed time in each experiment, we will use the Timer class which is in the package ann.util. This class computes time in seconds akin to a stopwatch timer, and can be manipulated via the following operations:
Timer aTimer = new aTimer() // construct aTimer as a Timer object
aTimer.start(); // start aTimer running
aTimer.stop(); // stop aTimer from running
aTimer.reset(); // reset aTimer to zero
aTimer.getTime() // return the number of seconds
The Timer class is built using the System.currentTimeMillis() function in the System class. The system clock will update every millisecond. If we happen to start the timer just before the clock tick and stop it just after, the timer will register a time of 0.001 even though the actual time was less. Similarly, if we start the timer just after a clock tick; have a clock tick; and then stop the timer just before the next clock tick. The timer will register a time of 0.001 even though the actual time was nearly 0.002. Keep this in mind when reviewing our timing results. Getting Started Begin by creating a new project in which to store your work for this exercise. Copy the ann package into your project and then continue. Comparing ArrayList and LinkedList The statement
ArrayList anArrayList = new ArrayList(3);
defines anArrayList as an object capable of storing three int values, and initializes each element to null. We can visualize such an object as follows: In this case, the size is zero and the capacity of anArrayList is 3. One key point to understand about an anArrayList is that the elements of an anArrayList are allocated in adjacent memory locations. That is, the element in anArrayList indexed by 0 is physically next to the element in anArrayList indexed by 1, which is physically next to the element in anArrayList indexed by 2, and so on. By contrast, a statement:
LinkedList aLinkedList = new LinkedList();
will not preallocate any storage for the elements in the list. It starts out with just the size and two references that will point to the first and last elements in the list. Each element will be held in a node. These nodes can be anywhere in a program's free store of memory. After adding three elements we will have a list that looks like: These nodes are connected together using references that can store the physical address of an object. We have already been using references with out knowing it. Every variable that is declared to hold some kind of Object actually holds a reference to that kind of Object. Every node contains two such references: one pointing to the next-node in the sequence, and one pointing to the previous-node in the sequence. The key thing to understand is this: since they are connected using references, the nodes in a LinkedList need not be in adjacent memory locations -- they can be anywhere in a program's free store of memory. That is, from aLinkedList, we can get to the first node, from its next-node attribute we can get to the second node, from the next-node attribute of the second node we can get to the third node, and so on. This means that a LinkedList's nodes can be scattered throughout memory and the sequencing of values is determined solely by the next-node and previous-node attributes of the nodes. By contrast, an ArrayList's elements must be in physically adjacent memory locations -- any value whose position is i must be physically adjacent to the values whose positions are i-1 and i+1. This difference in adjacent storage vs. nonadjacent storage is the primary difference between the ArrayList and the LinkedList, and affects the performance of the operations that they implement. For example, because the elements of an ArrayList are stored in adjacent memory locations, the get operation can be performed efficiently for a ArrayList. An expression
anArrayList.get(i)
requires a simple arithmetic computation to find the element. By contrast, trying to access the element of a LinkedList whose index is i would require that we start at the first node, follow its pointer to the second node, follow its pointer to the third node, and so on until we reach the ith node, an operation that would take time proportional to the size of the LinkedList. This is time-consuming compared to the ArrayList. The Experiments Each of the following experiments uses the Timer class to determine the time to perform a given operation on an ArrayList and on a LinkedList. Experiment 1: Appending n Values to an Empty Container Experiment 2: Appending 1 Value to a Container of Size n Experiment 3: Prepending n Values to an Empty Container Experiment 4: Prepending 1 Value to a Container of Size n Phrases you should now understand: ArrayList, LinkedList, Reference, Constant Time, Linear Time, Quadratic Time. Submit: The graphs you create during this exercise, plus a short essay in which you explain the circumstances under which it is appropriate to store a sequence of values in an ArrayList, as opposed to those in which one should choose a LinkedList. Back to This Lab's Table of Contents Back to the Prelab Questions Forward to the Homework Projects Back to the Table of Contents Back to the Introduction Copyright 2000 by Prentice Hall. All rights reserved.
