![](https://csdnimg.cn/release/download_crawler_static/86381880/bg1.jpg)
一般大家都知道 ArrayList 和 LinkedList 的大致区别:
1.ArrayList 是实现了基于动态数组的数据结构,LinkedList 基于链表的数据结构。
2.对于随机访问 get 和 set,ArrayList 觉得优于 LinkedList,因为 LinkedList 要移动指针。
3.对于新增和删除操作 add 和 remove,LinedList 比较占优势,因为 ArrayList 要移动数据。
ArrayList 和 LinkedList 是两个集合类,用于存储一系列的对象引用(references)。例如我们可以
用 ArrayList 来存储一系列的 String 或者 Integer。那么 ArrayList 和 LinkedList 在性能上有什么
差别呢?什么时候应该用 ArrayList 什么时候又该用 LinkedList 呢?
一.时间复杂度
首先一点关键的是,ArrayList 的内部实现是基于基础的对象数组的,因此,它使用 get 方法访问
列表中的任意一个元素时(random access),它的速度要比 LinkedList 快。LinkedList 中的 get 方
法是按照顺序从列表的一端开始检查,直到另外一端。对 LinkedList 而言,访问列表中的某个指
定元素没有更快的方法了。
假设我们有一个很大的列表,它里面的元素已经排好序了,这个列表可能是 ArrayList 类型的也
可能是 LinkedList 类型的,现在我们对这个列表来进行二分查找(binary search),比较列表是
ArrayList 和 LinkedList 时的查询速度,看下面的程序:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package com.mangocity.test;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class TestList ...{
public static final int N=50000;
public static List values;
static...{
Integer vals[]=new Integer[N];
Random r=new Random();
for(int i=0,currval=0;i<N;i++)...{
vals=new Integer(currval);
currval+=r.nextInt(100)+1;
}
values=Arrays.asList(vals);
}