USING ARRAYLIST AND LINKEDLIST

daizhe

ArrayList and LinkedList are two
Collections classes used for storing lists of object references. For
example, you could have an ArrayList of Strings, or a LinkedList of
Integers. This tip compares the performance of ArrayList and
LinkedList, and offers some suggestions about which of these classes is
the right choice in a given situation.
The first key point is
that an ArrayList is backed by a primitive Object array. Because of
that, an ArrayList is much faster than a LinkedList for random access,
that is, when accessing arbitrary list elements using the get method.
Note that the get method is implemented for LinkedLists, but it
requires a sequential scan from the front or back of the list. This
scan is very slow. For a LinkedList, there's no fast way to access the
Nth element of the list.
Consider the following example.
Suppose you have a large list of sorted elements, either an ArrayList
or a LinkedList. Suppose too that you do a binary search on the list.
The standard binary search algorithm starts by checking the search key
against the value in the middle of the list. If the middle value is too
high, then the upper half of the list is eliminated. However, if the
middle value is too low, then the lower half of the list is ignored.
This process continues until the key is found in the list, or until the
lower bound of the search becomes greater than the upper bound.
Here's a program that does a binary search on all the elements in an ArrayList or a LinkedList:
import java.util.*;
public class ListDemo1 {
static final int N = 10000;
static List values;
// make List of increasing Integer values
static {
Integer vals[] = new Integer[N];
Random rn = new Random();
for (int i = 0, currval = 0; i
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/21344/showart_474947.html