This program contains a workload that
it executes on both a LinkedList and an ArrayList, and outputs the
time taken by the workload in each case. Run the program and record
the times. Then run the program again after replacing the 100000 in the
two for-loops by 200000, and record the times. Explain the differences
in the time taken by ArrayList and LinkedList in terms of running
time analysis (the number of primitive steps). Your observed times
and explanation can be added as a comment to the program.
Now create a workload for which ArrayList fares much better than
LinkedList. This code can be added to the same program.
The goal here is to modify the ArrayListIterator class in this
implementation of ArrayList
(a version of the implementation in Section 3.4)
so that the class provides for the methods:
Currently, the class provides only for the first three methods, and this
part of the homework asks us to implement all five. I am assuming that
the functionality to be implemented by these methods is clear to you --we
have been talking about iterators for some time now, and ArrayListIterator
is just designed to construct an iterator object for the HWArrayList object.
Implementing the five methods will involve rewriting the first three
as well. This is because the remove method is supposed to remove the
object last seen by the iterator, and the last object may have been
seen during either a next() or previous() call.
Feel free to add more data fields to the ArrayListIterator class.
- public boolean hasNext()
- public AnyType next()
- public void remove()
- public boolean hasPrevious()
- public AnyType previous()