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:
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:
In each case, the value n will be entered from the keyboard.
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.
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.
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.
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
ArrayList, LinkedList, Reference, Constant Time, Linear Time, Quadratic Time.
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
Forward to the Homework Projects