Java(TM) Boutique - Tutorial - How Do Java's Lists Measure Up? Comparing Arrays, Lists, and Maps

Tutorials : How Do Java's Lists Measure Up? Comparing Arrays, Lists, and Maps :

Inserting Elements at Random Positions in a List

Here's the algorithm:

 
Repeat N times
            Insert element at a random position in 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(index, element) method N times
HashMap	(not applicable)

The test runs yielded the following results for N=10 000. All times measured were divided by the times measured for the Vector type.

Object type

Relative time

array

(not tested)

Vector

1

ArrayList

1.05

LinkedList
See note 1)

14.1

HashMap

N/A

Results:

The LinkedList only gives good performance when you access the first or last element(s) in the list. LinkedList is a so-called "doubly-linked list". Each element has links to the element in front of it and the element after it. To access an element in the first half of the list, all elements in front of it must be passed. Similarly all elements from the end of the list must be passed to get to an element in the last half.

Reading Elements from Beginning to End

Here's the algorithm:


Repeat from position 0 to N-1:
            Read element a the given position    
End Repeat

Object type	Comments
array	loop through the array using an index from 0 to N-1
List	use the get(index) method N times
HashMap	use the keys Integer(0) to Integer(N-1)

The test runs yielded the following results for N=1 000 000:

Object type

Relative time

array

1

Vector

2.8

Vector using an Iterator

4.7

ArrayList

1.5

LinkedList

Not completed � see note 1)

HashMap

not completed � see note 2)

Results:

This used too much cpu time. If you construct a ListIterator over the elements in the list, things get much better: you get a relative time of 16.6 compared to the array. And the ListIterator can also read the list backwards!
The run ended with OutOfMemoryError. Setting N=500 000 resulted in a completed run with a factor 40 compared to the array. That's actually not bad, considering that several iterations are needed to find an element for a given key.

Home / Articles / How Do Java's Lists Measure Up? Comparing Arrays, Lists, and Maps / 1 / 2 / 3

Applet Index
(sorted alphabetically)
A B C D E F G H I J K
L M N O P Q R S T U
V W X Y Z #s

The Java Source
(applets w/source code)
A B C D E F G H I J K
L M N O P Q R S T U
V W X Y Z

How to Add Java Applets to Your Site

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.