目录
前言
正文
ArrayList和linkList的区别
添加
查询
ArrayList和Vector区别
前言
前面几章我们研究了，ArrayList、linkList、Vector和Stack的源码，下面我们对相关的几个List进行对比和总结
正文
ArrayList和linkList的区别
平常总能听到同学们说，ArrayList与linkList相比查询快，插入慢，我们下面就用代码验证下
添加
- 尾部添加
//1000
ArrayList arrayList1 = new ArrayList<>(0);
linkedList linkedList1 = new linkedList<>();
long arrayStartTime = System.currentTimeMillis();
for(int i = 0; i < 1000; i++) {
arrayList1.add(i);
}
System.out.println("ArrayList add Time difference: " + (System.currentTimeMillis() - arrayStartTime));
long linkStartTime1 = System.currentTimeMillis();
for(int i = 0; i < 1000; i++) {
arrayList1.add(i);
}
System.out.println("ArrayList add Time difference: " + (System.currentTimeMillis() - linkStartTime1));
//输出
/ArrayList last add Time difference: 0 //linkedList last add Time difference: 0】 //没有区别， 把循环值增大10倍 //10000 ArrayList last add Time difference: 2 linkedList last add Time difference: 1 //差了1， 又运行了几次，出现相同的次数机率也很大， 和系统运行有关系，继续把循环值增大10倍 //100000 ArrayList last add Time difference: 8 linkedList last add Time difference: 4 //差了4，多运行了几次，得到的结果都是 ArrayList的时间大于linkList
结论: 尾部添加的时候，ArrayList的速度慢于linkList （是在一定量的基础上），这是因为ArrList尾部插入时候需要扩容，而，linkList只需要在last节点后添加一个新节点就可以了
- 中间插入
for(int i = 0; i < 1000; i++) {
long arrayListMidAddStartTime = System.currentTimeMillis();
arrayList1.add(i, i);
System.out.println("ArrayList Mid add " + i + " Time difference: " + (System.currentTimeMillis() - arrayListMidAddStartTime));
long linkListMidAddStartTime = System.currentTimeMillis();
linkedList1.add(i, i);
System.out.println("linkedList Mid add " + i + " Time difference: " + (System.currentTimeMillis() - linkListMidAddStartTime));
}
//输出
ArrayList Mid add 0 Time difference: 0 linkedList Mid add 0 Time difference: 0 ArrayList Mid add 1 Time difference: 0 linkedList Mid add 1 Time difference: 0 ArrayList Mid add 2 Time difference: 0 linkedList Mid add 2 Time difference: 0 。。。。 linkedList Mid add 997 Time difference: 0 ArrayList Mid add 998 Time difference: 1 linkedList Mid add 998 Time difference: 0 ArrayList Mid add 999 Time difference: 0 linkedList Mid add 999 Time difference: 0 //基本没有区别， 把循环值增大10 //10000 ArrayList Mid add 0 Time difference: 1 linkedList Mid add 0 Time difference: 0 ArrayList Mid add 1 Time difference: 1 linkedList Mid add 1 Time difference: 0 ArrayList Mid add 2 Time difference: 0 linkedList Mid add 2 Time difference: 0 。。。。 linkedList Mid add 9997 Time difference: 0 ArrayList Mid add 9998 Time difference: 0 linkedList Mid add 9998 Time difference: 1 ArrayList Mid add 9999 Time difference: 0 linkedList Mid add 9999 Time difference: 0 //基本没有区别， 把循环值增大10 .... ArrayList Mid add 87948 Time difference: 0 linkedList Mid add 87948 Time difference: 2 ArrayList Mid add 87949 Time difference: 0 linkedList Mid add 87949 Time difference: 3 ArrayList Mid add 87950 Time difference: 0 linkedList Mid add 87950 Time difference: 3 ArrayList Mid add 87951 Time difference: 0 linkedList Mid add 87951 Time difference: 5 ArrayList Mid add 87952 Time difference: 0 linkedList Mid add 87952 Time difference: 4 ArrayList Mid add 87953 Time difference: 0 linkedList Mid add 87953 Time difference: 4 .... ArrayList Mid add 99991 Time difference: 0 linkedList Mid add 99991 Time difference: 5 ArrayList Mid add 99992 Time difference: 0 linkedList Mid add 99992 Time difference: 6 ArrayList Mid add 99993 Time difference: 0 linkedList Mid add 99993 Time difference: 8 ArrayList Mid add 99994 Time difference: 0 linkedList Mid add 99994 Time difference: 5 ArrayList Mid add 99995 Time difference: 0 linkedList Mid add 99995 Time difference: 6 ArrayList Mid add 99996 Time difference: 0 linkedList Mid add 99996 Time difference: 5 ArrayList Mid add 99997 Time difference: 0 linkedList Mid add 99997 Time difference: 6 ArrayList Mid add 99998 Time difference: 0 linkedList Mid add 99998 Time difference: 6 ArrayList Mid add 99999 Time difference: 0 linkedList Mid add 99999 Time difference: 1 //开始有明显的差别了
80000时候 ArrayList的时间明显小于linkList
这个是因为，ArrayList插入的时候可以直接找到下标进行插入， 而linkList需要从头遍历，然后找到对应值，
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) //这是为啥当是99999的时候和ArrayList时间几乎没区别了
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
有人可能问，ArrayList需要扩容呢，为什么linkList的时间会更大呢。
所以猜测，应该是有一个界限，因为ArrayList 只有等size大于length的时候才需要扩容，所以”index“大于一定的数量后，向较于linkList的遍历，ArrayList的扩容所需要的时间可以是忽略不计的。
所以中间插入所需要的时间应该是这样的
这个界限值应该根据不同的硬件性能应该是不同的，
linkedList Mid add 24993 Time difference: 1 ArrayList Mid add 24994 Time difference: 0 linkedList Mid add 24994 Time difference: 0 ArrayList Mid add 24995 Time difference: 0 linkedList Mid add 24995 Time difference: 0 ArrayList Mid add 24996 Time difference: 0 linkedList Mid add 24996 Time difference: 0 ArrayList Mid add 24997 Time difference: 0 linkedList Mid add 24997 Time difference: 1 ArrayList Mid add 24998 Time difference: 0 linkedList Mid add 24998 Time difference: 0 ArrayList Mid add 24999 Time difference: 0 linkedList Mid add 24999 Time difference: 0 ... linkedList Mid add 39991 Time difference: 1 ArrayList Mid add 39992 Time difference: 0 linkedList Mid add 39992 Time difference: 0 ArrayList Mid add 39993 Time difference: 0 linkedList Mid add 39993 Time difference: 1 ArrayList Mid add 39994 Time difference: 0 linkedList Mid add 39994 Time difference: 1 ArrayList Mid add 39995 Time difference: 0 linkedList Mid add 39995 Time difference: 1 ArrayList Mid add 39996 Time difference: 0 linkedList Mid add 39996 Time difference: 2 ArrayList Mid add 39997 Time difference: 0 linkedList Mid add 39997 Time difference: 0 ArrayList Mid add 39998 Time difference: 0 linkedList Mid add 39998 Time difference: 1 ArrayList Mid add 39999 Time difference: 0 linkedList Mid add 39999 Time difference: 1
我的电脑上在25000到40000的时候出现了具体的差别
查询
for(int i = 0; i < 1000; i++) {
long arrayListGetStartTime = System.currentTimeMillis();
arrayList1.get(i);
System.out.println("ArrayList get " + i + " Time difference: " + (System.currentTimeMillis() - arrayListGetStartTime));
long linkListGetStartTime = System.currentTimeMillis();
linkedList1.get(i);
System.out.println("linkedList get " + i + " Time difference: " + (System.currentTimeMillis() - linkListGetStartTime));
}
输出
//1000 ArrayList get 992 Time difference: 0 linkedList get 992 Time difference: 0 ArrayList get 993 Time difference: 0 linkedList get 993 Time difference: 0 ArrayList get 994 Time difference: 0 linkedList get 994 Time difference: 0 ArrayList get 995 Time difference: 0 linkedList get 995 Time difference: 0 ArrayList get 996 Time difference: 0 linkedList get 996 Time difference: 0 ArrayList get 997 Time difference: 0 linkedList get 997 Time difference: 0 ArrayList get 998 Time difference: 0 linkedList get 998 Time difference: 0 ArrayList get 999 Time difference: 0 linkedList get 999 Time difference: 0 //没有区别，将循环值增大10倍 ArrayList get 9992 Time difference: 0 linkedList get 9992 Time difference: 0 ArrayList get 9993 Time difference: 0 linkedList get 9993 Time difference: 0 ArrayList get 9994 Time difference: 0 linkedList get 9994 Time difference: 0 ArrayList get 9995 Time difference: 0 linkedList get 9995 Time difference: 0 ArrayList get 9996 Time difference: 0 linkedList get 9996 Time difference: 0 ArrayList get 9997 Time difference: 0 linkedList get 9997 Time difference: 0 ArrayList get 9998 Time difference: 0 linkedList get 9998 Time difference: 0 ArrayList get 9999 Time difference: 0 linkedList get 9999 Time difference: 0 //任然没有区别， 增大到50000，因为linkListget的时候是先用中间值比较，然后选择从头遍历，还是 //从尾遍历, 具体代码请看linkList那章或则看下源码 ArrayList get 49993 Time difference: 0 linkedList get 49993 Time difference: 0 ArrayList get 49994 Time difference: 0 linkedList get 49994 Time difference: 0 ArrayList get 49995 Time difference: 0 linkedList get 49995 Time difference: 0 ArrayList get 49996 Time difference: 0 linkedList get 49996 Time difference: 0 ArrayList get 49997 Time difference: 0 linkedList get 49997 Time difference: 0 ArrayList get 49998 Time difference: 0 linkedList get 49998 Time difference: 0 ArrayList get 49999 Time difference: 0 linkedList get 49999 Time difference: 1 //区别仍然不大， 把上面的添加元素增大10倍，然后查找的循环在增大10倍 linkedList get 499990 Time difference: 4 ArrayList get 499991 Time difference: 0 linkedList get 499991 Time difference: 4 ArrayList get 499992 Time difference: 0 linkedList get 499992 Time difference: 5 ArrayList get 499993 Time difference: 0 linkedList get 499993 Time difference: 5 ArrayList get 499994 Time difference: 0 linkedList get 499994 Time difference: 5 ArrayList get 499995 Time difference: 0 linkedList get 499995 Time difference: 4 ArrayList get 499996 Time difference: 0 linkedList get 499996 Time difference: 4 ArrayList get 499997 Time difference: 0 linkedList get 499997 Time difference: 5 ArrayList get 499998 Time difference: 0 linkedList get 499998 Time difference: 4 ArrayList get 499999 Time difference: 0 linkedList get 499999 Time difference: 4 //有明显的区别了
有差别的原因是因为ArrayList数据结构是数组，可以通过下标直接找打，而linkList是链表是需要遍历链表找到位置，所需时间请看下图
有兴趣的小伙伴可以，自己用代码运行下
ArrayList和Vector区别
相同处： 数据结构上都是使用了数组，所以相关操作原理是一样的， 扩容操作都是使用的，新定义一个数组，然后通过System.copyOf进行复制
不同点：
Vector相关的方法上都使用的了 synchronized 关键字做了修饰，所以他是线程安全的，相对的性能就不如ArrayList
然后还有一些小细节区别，比如ArrayList的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和
EMPTY_ELEMENTDATA
Vector的扩容向量和扩容向量为0时，是扩容一倍，而ArrayList是1.5等等，这些在前面两章研究过了，就不做过多的叙述了
下一章开始研究另一个集合Set
上一章 下一章
