千锋教育-做有情怀、有良心、有品质的IT职业教育机构

400-811-9990
当前位置:千锋视频教程 > Java视频教程  >  java技术学习之ArrayList与LinkedList分析

java技术学习之ArrayList与LinkedList分析

时间:2018-04-12 11:27:45     来源:千锋视频教程 作者:教学部

  1.ArrayList与LinekedList的相同点

  集合和数据类似,主要用于存储数据,但是集合比数组的使用更灵活,主要体现在,集合可以的数据长度可变,且集合中的元素只要是对象即可,可以是不同的对象,但是我们会发现集合中可以直接存储基本类型,例如整数,那是因为自动转为包装类的原因;

  在这里我们主要研究下List集合的存储,首先,List集合的存储特点为:存储的数据有序且可重复,我们通过查看源代码可以发现,List为集合接口,所以接口的实现需要交给实现类,在List中有两个很重要的实现类分别是ArrayList和LinkedList,既然是实现类都需要遵循List接口的标准去实现功能,操作如下:

  //List list = new ArrayList(); //ArrayList实现List标准去操作

  List list = new LinkedList(); //LinkedList实现List标准去操作

  list.add(1); //添加对象

  list.add(3);

  list.add(1);

  list.add(2);

  最终不论是ArrayList还是LinkedList实例化的对象,打印的结果都为: 1、3、1,2

  通过结论可以发现,ArrayList和LinkedList都实现了List集合的存储特点,也就是存储的数据有序,且可重复,那么这两个类是如何是如何实现存储特点的呢?

  ArrayList是通过数组扩容的方式实现对数据的存储

  LinkedList是通过双向链表的方式实现对数据的存储,具体的存储方式,下面我们通过对两个实现类的源代码进行分析

  2.ArrayList的存储源代码分析

  分析ArrayList的存储的源代码,也就是add方法,在ArrayList中增加元素到队列尾端的代码如下:

  public boolean add(E e){

  ensureCapacity(size+1);//确保内部数组有足够的空间

  elementData[size++]=e;//将元素加入到数组的末尾,完成添加

  return true;

  }

  ArrayList中add()方法的性能决定于ensureCapacity()方法。ensureCapacity()的实现如下:

  public vod ensureCapacity(int minCapacity){

  modCount++;

  int oldCapacity=elementData.length;

  if(minCapacity>oldCapacity){ //如果数组容量不足,进行扩容

  Object[] oldData=elementData;

  int newCapacity=(oldCapacity*3)/2+1; //扩容到原始容量的1.5倍

  if(newCapacitty

  //需要的容量大小

  newCapacity=minCapacity ; //进行扩容的数组复制

  elementData=Arrays.copyof(elementData,newCapacity);

  }

  }

  可以看到,只要ArrayList的当前容量足够大,add()操作的效率非常高的。只有当ArrayList对容量的需求超出当前数组大小时,才需要进行扩容。扩容的过程中,会进行大量的数组复制操作。而数组复制时,最终将调用System.arraycopy()方法,因此add()操作的效率还是相当高的。

  3. LinkedList的存储源代码分析

  LinkedList 的add()操作实现如下,它也将任意元素增加到队列的尾端:

  public boolean add(E e){

  addBefore(e,header);//将元素增加到header的前面

  return true;

  }

  其中addBefore()的方法实现如下:

  private Entry addBefore(E e,Entry entry){

  Entry newEntry = new Entry(e,entry,entry.previous);

  newEntry.provious.next=newEntry;

  newEntry.next.previous=newEntry;

  size++;

  modCount++;

  return newEntry;

  }

  可见,LinkeList由于使用了链表的结构,因此不需要维护容量的大小。从这点上说,它比ArrayList有一定的性能优势,然而,每次的元素增加都需要新建一个Entry对象,并进行更多的赋值操作。在频繁的系统调用中,对性能会产生一定的影响。

  4. 两者删除任意位置元素的分析

  对于元素的删除,List接口提供了在任意位置删除元素的方法:

  public E remove(int index);

  对ArrayList来说,remove()方法和add()方法是雷同的。在任意位置移除元素后,都要进行数组的重组。ArrayList的实现如下:

  public E remove(int index){

  RangeCheck(index);

  modCount++;

  E oldValue=(E) elementData[index];

  int numMoved=size-index-1;

  if(numMoved>0)

  System.arraycopy(elementData,index+1,elementData,index,numMoved);

  elementData[--size]=null;

  return oldValue;

  }

  可以看到,在ArrayList的每一次有效的元素删除操作后,都要进行数组的重组。并且删除的位置越靠前,数组重组时的开销越大。

  public E remove(int index){

  return remove(entry(index));

  }private Entry entry(int index){

  if(index<0 || index>=size)

  throw new IndexOutBoundsException("Index:"+index+",size:"+size);

  Entry e= header;

  if(index<(size>>1)){//要删除的元素位于前半段

  for(int i=0;i<=index;i++)

  e=e.next;

  }else{

  for(int i=size;i>index;i--)

  e=e.previous;

  }

  return e;

  }

  在LinkedList的实现中,首先要通过循环找到要删除的元素。如果要删除的位置处于List的前半段,则从前往后找;若其位置处于后半段,则从后往前找。因此无论要删除较为靠前或者靠后的元素都是非常高效的;但要移除List中间的元素却几乎要遍历完半个List,在List拥有大量元素的情况下,效率很低。

  5. 两者遍历列表的分析

  遍历列表操作是最常用的列表操作之一,在JDK1.5之后,至少有3中常用的列表遍历方式:forEach操作,迭代器和for循环。

  String tmp;long start=System.currentTimeMills(); //ForEach for(String s:list){

  tmp=s;

  }

  System.out.println("foreach spend:"+(System.currentTimeMills()-start));

  start = System.currentTimeMills();for(Iterator it=list.iterator();it.hasNext();){

  tmp=it.next();

  }

  System.out.println("Iterator spend;"+(System.currentTimeMills()-start));

  start=System.currentTimeMills();int size=;list.size();for(int i=0;i

  tmp=list.get(i);

  }

  System.out.println("for spend;"+(System.currentTimeMills()-start));

  构造一个拥有100万数据的ArrayList和等价的LinkedList,使用以上代码进行测试,测试结果的相对耗时如下表所示:

1.jpg

  可以看到,最简便的ForEach循环并没有很好的性能表现,综合性能不如普通的迭代器,而是用for循环通过随机访问遍历列表时,ArrayList表项很好,但是LinkedList的表现却无法让人接受,甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时,总会进行一次列表的遍历操作。性能非常差,应避免使用。

  综上所述: 往往我们使用更多的实现类位ArrayList,因为我们更多的操作为向后追加和定位元素,而追加和定位ArrayList会比LinkedList更有优势。

  • 北京天丰利校区(总部):北京市海淀区宝盛北里西区28号天丰利商城4层
    北京沙河校区:北京市昌平区沙阳路18号北京科技职业技术学院广场服务楼2层、南区服务楼2层
    咨询电话:400-186-9990 010-82790226-801
    面授课程:全栈HTML5+培训、UI交互设计培训、PHP培训、JavaEE+云数据培训、大数据开发培训、VR/AR混合
    现实培训、Python培训、Linux云计算培训、软件测试培训、Android培训、iOS培训、好程序员
  • 深圳西部硅谷校区地址:深圳市宝安区宝安大道5010号深圳西部硅谷B座A区605-619
    深圳大学城校区地址:深圳市南山区留仙大道1201号大学城创客小镇16栋2楼、3楼
    咨询电话:0755-33582485-801(硅谷校区)0755-86660670-801(大学城校区)
    面授课程:全栈HTML5+培训、UI交互设计培训、PHP培训、JavaEE+云数据培训、Android培训、iOS培训
  • 上海校区地址:上海市宝山区同济支路199号智慧七立方3号楼2-4层
    咨询电话:400-627-7899 021-56166283/56166279
    面授课程:全栈HTML5+培训、UI交互设计培训、JavaEE+云数据培训、Android课程培训、iOS课程培训、好程序员
  • 郑州校区地址:郑州市金水区纬五路21号河南教育学院综合楼(经纬中学楼)7/8层
    咨询电话:0371-55191750 400-186-9990
    面授课程:全栈HTML5+培训、UI交互设计培训、PHP培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 广州校区地址:广州市天河区元岗路310号智汇park创意园E座5层
    咨询电话:020-22119207 400-186-9990
    面授课程:全栈HTML5+培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 大连校区地址:辽宁省大连市甘井子区软件园路2号东软信息学院B5座一楼
    咨询电话:0411-39026086 400-186-9990
    面授课程:全栈HTML5+培训、JavaEE+云数据培训、UI交互设计培训、Android课程培训、iOS课程培训
  • 武汉校区地址:武汉市光谷大道61号智慧园21号楼2层
    咨询电话:027-65523826
    面授课程:全栈HTML5+培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 成都校区地址:成都市武侯区科华北路62号力宝大厦N(北楼)18楼
    咨询电话:028-83178771
    面授课程:全栈HTML5+培训、UI交互设计培训、PHP培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 西安校区地址:西安市雁塔区高新六路52号立人科技C座西区4楼
    咨询电话:029-85260160
    面授课程:全栈HTML5+培训、JavaEE+云数据培训、Android课程培训
  • 杭州校区地址:浙江省杭州市江干区九堡旺田书画城A座4层
    咨询电话:0571-86893632 010-82790226-801
    面授课程:全栈HTML5+培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 青岛校区地址:青岛市市南区金坛路17号青岛职业技术学院南校区实训楼A4层
    咨询电话:0532-80910752/3 010-82790226-801
    面授课程:全栈HTML5+培训、UI交互设计培训、JavaEE+云数据培训、Android课程培训、iOS课程培训
  • 重庆校区地址:重庆市高新区科园一路2号大西洋国际12-1
    咨询电话:023-68883009
    面授课程:JavaEE+云数据课程培训
  • 长沙校区地址:湖南省长沙市岳麓区麓谷企业广场A2栋三单元306号
    咨询电话:0731-85513010/85513210
    面授课程:JavaEE+云数据课程培训
  • 哈尔滨校区地址:哈尔滨市松北区创新一路699号科技创新城19号楼五楼
    咨询电话:15663846969
    面授课程:全栈HTML5+培训
  • 千锋教育服务号

    了解千锋动态
    关注千锋教育服务号

  • 千锋互联服务号

    扫码匿名提建议
    直达CEO信箱