|
How Do Java's Lists Measure Up? Comparing Arrays, Lists, and Maps
by Keld H. Hansen
In one of my last Java projects, I had to store a large number of ordered objects for display in a Web application. Sometimes the number of elements was quite large, maybe many thousands, and displaying them would, of course, involve a scrolling mechanism in the GUI.
Because the list of objects would be of a fixed size, the obvious solution was use an array, as this would ensure good performance when storing and retrieving elements from the array. But if the size is not fixed and elements need to be inserted, updated, or deleted at random spots in the list?
Java offers several solutions for storing objects in an ordered list: arrays, Lists, and Maps—to mention the best known. This article analyzes the performance benefits and drawbacks of these lists using several examples.
What Will Be Measured
In order to decide which solution is the most appropriate for a given situation, you'll need to consider what your application will need to do:
- Insert elements at the end of a list
- Insert elements in the beginning of a list
- Insert elements at random positions in a list
- Access elements from the first to the last
- Access elements from the last to the first
- Access elements in random order
- Update elements in random order
In the accompanying examples, you'll be testing the simple array, the List Interface, and the Map Interface. The test runs were repeated several times to ensure stable results. To avoid interference from garbage collection or other side effects, the various functions were tested in separate program executions on each data structure. Indexes used in the random order functions were generated before the performance clock was started. The newest JRE (1.5.0_09) was used in all runs.
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.
|
