当前位置： 移动技术网 > IT编程>开发语言>Java > List集合总结，对比分析ArrayList，Vector，LinkedList

List集合总结，对比分析ArrayList，Vector，LinkedList

2019年06月30日  | 移动技术网IT编程  | 我要评论

太极无敌,面具娇娃,乐嘉承认有儿女

前面已经写了三篇关于java集合的文章，包括：

java集合 arraylist原理及使用

再说java集合，sublist之于arraylist

java集合 linkedlist的原理及使用

关于vector，它的实现和arraylist非常类似，就不再单开一个章节来讲了，现在我们来对java集合做一个归纳总结。

一. list框架图

首先上面的框架图可以表明顺序的关联关系，但并不全面，如arraylist在继承了abstractlist抽象类的同时还实现了list接口。

  1. list是一个接口，继承了collection，同时collection继承了iterable，表明list的实现类都是可用迭代遍历的；
  2. abstractlist是一个抽象类，实现了list接口，同时继承了abstractcollection，针对一些常用方法，如add()，set()，remove()，给了默认实现，当然在具体的实现类中基本都重写了，该类中没有get()，size()方法。
  3. abstractsequentiallist是一个抽象类，继承了abstractlist抽象类，实现了很多双向链表中根据索引操作的方法。
  4. arraylist、vector、linkedlist、stack都是具体的实现类。

二. arraylist、vector对比分析

类型 线程安全 内部结构 扩容规则 执行效率 序列化
arraylist 否 数组object[] 10 数组足够最小长度*1.5 高 是
vector 是 数组object[] 10 默认数组足够最小长度*2，可自定义每次扩容数量 低 是

vertor扩容方法：

private void grow(int mincapacity) {
    // overflow-conscious code
    int oldcapacity = elementdata.length;
    //capacityincrement参数可通过构造函数传递进来，若没传递该参数，则数组大小设置为elementdata.length * 2
    int newcapacity = oldcapacity + ((capacityincrement > 0) ?
                                     capacityincrement : oldcapacity);
    if (newcapacity - mincapacity < 0)
        newcapacity = mincapacity;
    //扩容有上限
    if (newcapacity - max_array_size > 0)
        newcapacity = hugecapacity(mincapacity);
    elementdata = arrays.copyof(elementdata, newcapacity);
}

三. arraylist、linkedlist对比分析

类型 内部结构 插入效率(正常情况) 删除效率(正常情况) 顺序遍历效率 随机遍历效率 占用内存 序列化
arraylist 数组object[] 低 低 高 高 低 是
linkedlist 双向链表node 高 高 高 低 高 是

上述的对比都是基于大数据量的情况下，如果只是几个元素或几十个元素，它们之间并没有多大区别。

问：插入效率为何说正常情况下arraylist低，linkedlist高呢？

答：我们清楚arraylist之所以插入效率低，有两个原因会造成时间的消耗。

​ 第一，当底层数组空间不足时需要扩容，扩容后需进行数组拷贝

​ 第二，当不在数组末尾插入数据，那么就需要移动数组元素

​ 知道了其插入效率低的原因后，那么很明显，数据扩容及拷贝只有在数组空间不足时才发生，如果我们正确使用，就像《阿里巴巴java开发手册》中提到我们在创建集合对象时，就传递参数预先设置好数组大小，那么插入效率是非常高的；而90%的情况下我们在添加元素时都调用的是add(e e)，直接在末尾添加元素，很少调用add(int index, e e)在数组中部添加元素，这样其实移动数组元素就很少发生，因此插入效率也很高。

问：删除效率为何说正常情况下arraylist低，linkedlist高呢？

答：因为删除效率高、低不是绝对的。其实删除操作可以分为两部分。

​ 第一：找到要删除的元素，这个通过索引找，arraylist的执行效率要远高于linkedlist的执行效率；通过equals找则需要遍历整个集合，arraylist和linkedlist执行效率基本一致。

​ 第二：删除元素及后续操作，这个如果删除是最后一个元素，执行效率基本一致；如果是删除的中间元素，那么arraylist需进行数组元素移动，而linkedlist只需搭建起该元素的上一个节点和下一个节点的关系即可，linkedlist执行效率高于arraylist。

​ 因此，需根据实际情况才可判断实际的执行效率。

问：遍历效率这个问题怎么说？

答：arraylist通过数组实现，天然可以通过数组下标读取数据，顺序遍历、随机遍历效率都非常高；linkedlist通过双向链表实现，顺序遍历时，可直接通过本节点.next()直接找到相关联的下一个节点，效率很高，而如果linkedlist随机遍历时，首先需判断（传递的索引值与集合长度/2）的大小，来确定接下来是应该从第一个节点开始找还是最后节点开始找，越是靠近集合中部、集合越大，随机遍历执行效率越低。

​

四. 总结

本文对list集合进行了总结，包括类结构图，arraylist和vector对比分析，arraylist和linkedlist的对比分析，若有不对之处，请批评指正，望共同进步，谢谢！

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网