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 :

Reading Elements from End to Beginning

Here's the algorithm:


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

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

The test running with N=1 000 000 gave almost identical results as when reading from start to end.

Updating Elements at Random Positions on a List

Here's the algorithm:


Repeat N times
            Replace element at a random position in the list    
End Repeat

Object type	Comments
array	use array[random index] = value
List	use the set(random index, element) method N times
HashMap	use Integer(random index) as key

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

Object type

Relative time

array

1

Vector

1.1

ArrayList

1.1

LinkedList
See note 1)

not completed

HashMap

7.3

Results:

This uses up too much cpu time.
The Vector and ArrayList use almost the same time as the array. The reason for this, of course, is that the size of the underlying arrays is fixed. The HashMap still has a fine performance.

Situational Ethics

The measured times show that for random operations within a list, it's preferable to use the array or the ArrayList. There's no real difference in performance between the array and the ArrayList, so if you need the extra features of an ArrayList, then it's the obvious choice. You should only consider using LinkedList when your operations work on the ends of the list. Another option to consider might be the new Queue class-- when only the top element of a list is of interest.

When the index or key to the list is not an integer, HashMap is the only choice, and as you've seen, its performance is quite good.

Happy coding!

Resources

Click here to download the source code.

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

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.