这些类有许多不同的功能可以进行测试。LinkedList应用比较频繁，因为人们认为它在随机插入和删除操作时具有较好的性能。所以，下面我分析的重点将是插入操作的性能，即，构造集合。我测试并比较了LinkedList和ArrayList，因为这两者都是非同步的。
插入操作的速度主要由集合的大小和元素插入的位置决定。当插入点的位置在集合的两端和中间时，最差的插入性能和最好的插入性能都有机会出现。因此，我选择了三个插入位置（集合的开头、末尾和中间），三种典型的集合大小：中等（100个元素），大型（10,000个元素），超大型（1,000,000个元素）。
在本文的测试中，我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外，我还用HOTSPOT JVM 2.0进行了测试，这个版本可以在1.3.0 SDK找到。在下面的表格中，各个测量得到的时间都以其中一次SDK 1.2 VM上的测试时间（表格中显示为100%的单元）为基准显示。测试期间使用了默认的JVM配置，即启用了JIT编译，因此对于所有JVM，堆空间都必须进行扩展，以避免内存溢出错误。表格中记录的时间是多次测试的平均时间。为了避免垃圾收集的影响，在各次测试之间我强制进行了完全的内存清理（参见测试源代码了解详情）。磁盘监测确保磁盘分页不会在测试过程中出现（任何测试，如果它显示出严重的磁盘分页操作，则被丢弃）。所有显示出数秒应答时间的速度太慢的测试都重复进行，直至记录到一个明显合理的时间。
|
表1：构造一个中等大小的集合（100个元素）。括号中的数字针对预先确定大小的集合。 | |||
|
|
1.2 JVM |
1.3 JVM |
HotSpot 2.0 JVM |
|
总是插入到ArrayList的开头 |
100% (48.0%) |
184.9% (152.0%) |
108.0% (66.7%) |
|
总是插入到LinkedList的开头 |
135.5% |
109.1% |
85.3% |
|
总是插入到ArrayList的中间 |
130.0% (40.6%) |
187.4% (158.0%) |
84.7% (46.0%) |
|
总是插入到LinkedList的中间 |
174.0% |
135.0% |
102.3% |
|
总是插入到ArrayList的末尾 |
63.3% (20.7%) |
65.9% (25.0%) |
60.3% (29.3%) |
|
总是插入到LinkedList的末尾 |
106.7% |
86.3% |
80.3% |
对于规模较小的集合，ArrayList和LinkedList的性能很接近。当元素插入到集合的末尾时，即追加元素时，ArrayList的性能出现了突变。然而，追加元素是ArrayList特别为其优化的一个操作：如果你只想要一个固定大小的静态集合，Java数组（例如Object[]）比任何集合对象都具有更好的性能。除了追加操作，测量得到的时间数据差别不是很大，它们反映了各个JVM的优化程度，而不是其他什么东西。
例如，对于把元素插入到集合的开始位置来说（表1的前两行），HotSpot 2.0 JVM加LinkedList具有最好的性能（85.3%），处于第二位的是 1.2 JVM加ArrayList（100%）。这两个结果显示出，1.2中简单的JIT编译器在执行迭代和复制数组等简单的操作时具有很高的效率。在HotSpot中复杂的JVM加上优化的编译器能够改进复杂操作的性能，比如对象创建（创建LinkedList节点），并能够利用代码内嵌（code-inlining）的优势。1.3 JVM的结果似乎显示出，在简单操作方面它的性能有着很大的不足，这一点很可能在以后的JVM版本中得到改进。
在这里我特别进行测试的是ArrayList相对于LinkedList的另一个优点，即预先确定集合大小的能力。具体地说，创建ArrayList的时候允许指定一个具体的大小（例如，在测试中ArrayList可以创建为拥有100个元素的容量），从而避免所有随着元素增多而增加集合规模的开销。表1括号中的数字显示了预先确定集合大小时性能的提高程度。LinkedList（直到 SDK 1.3）不能预先确定大小。
此外，ArrayList只生成少量的需要进行垃圾收集的对象，即，用来保存元素的内部数组对象，以及每次ArrayList容量不足需要进行扩展时创建的附加内部数组对象。LinkedList不管可能出现的任何删除操作，都为每一个插入操作生成一个节点对象。因此，LinkedList会给垃圾收集器带来相当多的工作。考虑到这些因素，对于任何中小规模的集合，我会选择使用ArrayList而不是LinkedList。
|
表2：构造一个大型集合（10,000个元素） | |||
|
|
1.2 JVM |
1.3 JVM |
HotSpot 2.0 JVM |
|
总是插入到ArrayList的开头 |
7773% |
7537% |
7500% |
|
总是插入到LinkedList的开头 |
100% |
90.34% |
65.6% |
|
总是插入到ArrayList的中间 |
3318% |
3412% |
3121% |
|
总是插入到LinkedList的中间 |
26264% |
14315% |
14209% |
|
总是插入到ArrayList的末尾 |
41.4% |
41.2% |
37.5% |
|
总是插入到LinkedList的末尾 |
66.4% |
73.9% |
61.7% |
表2显示了大规模集合的测试结果。可以看到，在出现大规模插入操作的时候，我们开始遭遇严厉的性能惩罚。正如我们前面分析类的实现所得到的结果，对于LinkedList来说最差的情形出现在把元素插入到集合中间时。另外我们还可以看到，与使用ArrayList时把元素插入到集合开头的最差性能相比，使用LinkedList时把元素插入到集合中间的性能更差一些。和这两种性能最差的情况相比，把元素插入到ArrayList中间的性能显然要好得多。
总地看来，ArrayList再一次在大多数情形下表现出更好的性能，包括根据索引把元素插入到随机位置的情形。如果你总是要把元素插入到集合中靠前的位置，LinkedList具有更好的性能；然而，此时你可以利用一个反向的ArrayList得到更好的性能，即，使用一个专用的实现，或者通过[size -index]映射翻转索引在集合中的位置。
|
表3：构造一个超大集合（1,000,000个元素） | |||
|
|
1.2 JVM |
1.3 JVM |
HotSpot 2.0 JVM |
|
总是插入到ArrayList的开头 |
太长 |
太长 |
太长 |
|
总是插入到LinkedList的开头 |
100% |
179.5% |
144.1% |
|
总是插入到ArrayList的中间 |
太长 |
太长 |
太长 |
|
总是插入到LinkedList的中间 |
太长 |
太长 |
太长 |
|
总是插入到ArrayList的末尾 |
38.3% |
47.7% |
42.9% |
|
总是插入到LinkedList的末尾 |
65.1% |
161.5% |
139.9% |
表3显示了超大集合的测试结果，从该表可以得出的结论与表2非常相似。然而，表3强调的是，超大集合要求数据、集合类型、数据处理算法之间的恰到好处的配合；否则，你将得到事实上不可接受的性能表现。至于性能优化，你可以构造一个针对该问题的专用集合类。对于超大集合来说，为了获得可接受的性能，构造专用集合类往往是很有必要的。
