|
The List Interface
A List is an ordered collection, in which it's possible to insert, retrieve, and delete elements at any position. There are several implementations of the List interface, but their performances are very different. This isn't because they are poorly implemented, but because they were intended to be used for different purposes.
This article looks at the Vector, ArrayList, and LinkedList classes, all of which implement the List interface.
The Map Interface
When using the Map Interface, you supply a key when storing or retrieving an object. If the keys have the same role, as an index for an array or List, it is possible to measure some of the functions listed above. The examples below use a HashMap.
Inserting Elements at the End of a List
|
Object type
|
Comments
|
|
array
|
using a fixed size array insert elements using an index from 0 to
N-1
|
|
List
|
use the add method N times
|
|
HashMap
|
use keys Integer(0) to Integer(N-1)
|
The test runs yielded the following results for N=100 000. All times measured were divided by the times measured for the array type (to ease comparisons of the times).
|
Object type
|
Relative time
|
|
array
|
1
|
|
Vector
|
2.4
|
|
ArrayList
|
2.6
|
|
ArrayList with correct size.
See note 1)
|
1.03
|
|
LinkedList
|
2.0
|
|
HashMap
See note 2)
|
8.6
|
Results:
- Since the ArrayList class internally uses an Object array for storing the elements, making the list bigger may require you to create a new, larger array and copy all the elements to your new array. But the ArrayList has a constructor in which you can set the initial capacity of the list. It's therefore not a big surprise that a properly-sized ArrayList uses the same computer time as an array.
- The HashMap's performance is actually surprisingly good.
Inserting Elements at the Beginning of a List
Here's the algorithm:
Repeat N times
Insert element at the beginning of the list
End Repeat
|
Object type
|
Comments
|
|
array
|
(not tested – use the ArrayList for such a situation, it’s much simpler to
use)
|
|
List
|
use the add(0, element) method N times
|
|
HashMap
|
(not applicable)
|
The test runs yielded the following results for N=10 000. Note that this number is much smaller than before in order to avoid long runs. All times measured were divided by the times measured for the LinkedList type.
|
Object type
|
Relative time
|
|
array
|
N/A
|
|
Vector
|
7.8
|
|
ArrayList
|
8.0
|
|
ArrayList with correct size.
See note 1)
|
8.1
|
|
LinkedList
See note 2)
|
1
|
|
HashMap
|
N/A
|
Results:
- There is no difference between using an ArrayList with or without the correct initial size. Inserting elements in the beginning of the underlying array takes time!
- The LinkedList is the real winner this time. It's obviously tuned for insertions in the beginning and the end.
New on the Java Boutique:
New Review:
Time Management Made Easy with the Quartz Enterprise Job Scheduler
Why not just use the Java timer API? This open source scheduling
API boasts simplicity, ease-of-integration, a well-rounded feature
set, and it's free!
New Applet:
Reverse Complement
Reverse Complement is a simple applet that converts DNA or RNA
sequences into three useful formats.
Elsewhere on internet.com:
WebDeveloper Java
Lots of Java information on webdeveloper.com
WDVL Java
Thorough Java resource at the Web Developer's Virtual Library.
ScriptSearch Java
Hundreds of free Java code files to download.
jGuru: Your View of the Java Universe
Customizable portal with online training, FAQs, regular news updates, and tutorials.
|
