欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

集合中ArrayList和LinkedList比较

程序员文章站 2022-07-12 19:28:08
...

ArrayList和LinkedList比较
从尾部添加效率比较
public void TestArrayAndLinkedListAdd(){
 List<Integer> list1 = new ArrayList<Integer>();
 List<Integer> list2 = new LinkedList<Integer>();

 long lss2 = System.currentTimeMillis();
 for(int i = 0; i < 1000000; i ++){
  list2.add(i);
 }
 long lse2 = System.currentTimeMillis();
 long li2 = lse2 - lss2;
 System.out.println("LinkedList:---" + li2);

 long lss1 = System.currentTimeMillis();
 for(int i = 0; i < 1000000; i ++){
  list1.add(i);
 }
 long lse1 = System.currentTimeMillis();
 long li1 = lse1 - lss1;
 System.out.println("ArrayList:---" + li1);
 
}
LinkedList:---619
ArrayList:---179
可以看出ArrayList效率高于LinkedList,分析源码
ArrayList中add方法
public boolean add(E e) {
 ensureCapacityInternal(size + 1);  // Increments modCount!!
 elementData[size++] = e;
 return true;
}
//检查容量
private void ensureCapacityInternal(int minCapacity) {
 if (elementData == EMPTY_ELEMENTDATA) {
  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }

 ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
 modCount++;

 // 如果容量大于数组长度,扩容
 if (minCapacity - elementData.length > 0)
  grow(minCapacity);
}
private void grow(int minCapacity) {
 // overflow-conscious code
 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity + (oldCapacity >> 1); //新的容量为原容量的1.5倍
 if (newCapacity - minCapacity < 0)  //新的容量小于最小的容量
  newCapacity = minCapacity; //新容量等于最小的容量
 if (newCapacity - MAX_ARRAY_SIZE > 0) //新容量大于(2的31次方-8)
  newCapacity = hugeCapacity(minCapacity);
 // minCapacity is usually close to size, so this is a win:
 //将当前数组copy指定长度的新数组中 Arrays.copyOf底层调用的是System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
 elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
 //假如minCapacity大于Integer的最大数限制,加一时则变成负数,minCapacity为负数,抛出栈溢出错误
 if (minCapacity < 0) // overflow
  throw new OutOfMemoryError();
 //如果没有返回Integer最大值或者最大值-8
 return (minCapacity > MAX_ARRAY_SIZE) ?
 Integer.MAX_VALUE :
 MAX_ARRAY_SIZE;
}

LinkedList中的add方法
public boolean add(E e) {
 linkLast(e);
 return true; //不需要去掉重复,默认每次添加都是成功的
}
//将元素添加在链表的后面
void linkLast(E e) {
 final Node<E> l = last;
 final Node<E> newNode = new Node<>(l, e, null); //新建一个Node对象
 last = newNode;
 if (l == null)
  first = newNode;
 else
  l.next = newNode;
 size++;
 modCount++;
}
结论:从尾部直接添加,虽然ArrayList每次添加时都会检查容量,并且扩容,但是LinkedList每次添加都会新建一个Node对象,所以速度慢于ArrayList

从在中间添加添加效率比较
public void TestArrayAndLinkedList(){
 List<Integer> list1 = new ArrayList<Integer>();
 List<Integer> list2 = new LinkedList<Integer>();
 for(int i = 0; i < 100000; i ++){
  list1.add(i);
  list2.add(i);
 }
 int random1 = (int)(Math.random()*1000);//300;
 int random2 = (int)(Math.random()*10000);//9000;
 long lss1 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  //list1.remove((Integer)i);
  list1.add(i, i);
 }
 long lse1 = System.currentTimeMillis();
 long li1 = lse1 - lss1;
 System.out.println("ArrayList:---" + li1);
 long lss2 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  //list2.remove((Integer)i);
  list2.add(i, i);
 }
 long lse2 = System.currentTimeMillis();
 long li2 = lse2 - lss2;
 System.out.println("LinkedList:---" + li2);
 
}
ArrayList:---91
LinkedList:---6
试验LinkedList效率高于ArrayList
查看源码:
ArrayList中
public void add(int index, E element) {
 rangeCheckForAdd(index);
 //检查并且扩容
 ensureCapacityInternal(size + 1);  // Increments modCount!!
 //将elementData中index后的元素copy到elementData的index+1,就是index后的所有元素后移一位
 System.arraycopy(elementData, index, elementData, index + 1,
   size - index);
 elementData[index] = element;
 size++;
}
LinkedList中
public void add(int index, E element) {
 checkPositionIndex(index);

 if (index == size)
  linkLast(element);
 else
  linkBefore(element, node(index)); //node(index) 查询该位置的元素,将element添加到index位置元素的前面
}
结论:实际上上诉示例中修改集合的容量大小和添加的次数,会发现在50000个容量且插入次数为1000次以上的操作LinkedList的速度才会大于ArrayList,
但是在这个数量级之下ArrayList的速度是大于LinkedList的

get效率比较
public void TestArrayAndLinkedList(){
 List<Integer> list1 = new ArrayList<Integer>();
 List<Integer> list2 = new LinkedList<Integer>();
 for(int i = 0; i < 100000; i ++){
  list1.add(i);
  list2.add(i);
 }
 int random1 = (int)(Math.random()*1000);//300;
 int random2 = (int)(Math.random()*10000);//9000;
 long lss1 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  //list1.remove((Integer)i);
  list1.get(i);
 }
 long lse1 = System.currentTimeMillis();
 long li1 = lse1 - lss1;
 System.out.println("arrayList:---" + li1);
 long lss2 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  //list2.remove((Integer)i);
  list2.get(i);
 }
 long lse2 = System.currentTimeMillis();
 long li2 = lse2 - lss2;
 System.out.println("LinkedList:---" + li2);
 
}
ArrayList:---1
LinkedList:---159
可以看出ArrayList效率高于LinkedList,分析源码
ArrayList中get(int index)方法
public E get(int index) {
 rangeCheck(index); //检查下标是否超出范围

 return elementData(index);//通过下标获取
}
LinkedList中get(int index)方法
public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
}
Node<E> node(int index) {
 // assert isElementIndex(index);

 if (index < (size >> 1)) { //如果坐标小于当前集合大小的一半 从头开始循环查询直到index
  Node<E> x = first;
  for (int i = 0; i < index; i++)
   x = x.next;
  return x;
 } else {
  Node<E> x = last; //如果坐标大于当前集合大小的一半 从尾部开始循环查询直到index
  for (int i = size - 1; i > index; i--)
   x = x.prev;
  return x;
 }
}
结论:上述是通过下标获取元素,很明显ArrayList优势远高于LinkedList

remove(Object o)直接删除元素效率比较
public void TestArrayAndLinkedList(){
 List<Integer> list1 = new ArrayList<Integer>();
 List<Integer> list2 = new LinkedList<Integer>();
 for(int i = 0; i < 1000; i ++){
  list1.add(i);
  list2.add(i);
 }
 int random1 = 0;//(int)(Math.random()*1000);//300;
 int random2 = 200;//(int)(Math.random()*10000);//9000;
 
 long lss1 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  list1.remove((Integer)i);
  //list1.add(i, i);
 }
 long lse1 = System.currentTimeMillis();
 long li1 = lse1 - lss1;
 System.out.println("ArrayList:---" + li1);
 
 long lss2 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  list2.remove((Integer)i);
  //list2.add(i, i);
 }
 long lse2 = System.currentTimeMillis();
 long li2 = lse2 - lss2;
 System.out.println("LinkedList:---" + li2);
 
}
改变集合容量和删除次数,发现数量级在1000以下,删除次数在50左右,效率的差不多的,但是LinkedList的效率还是优于ArrayList
查看源码:
ArrayList的remove(Object o)
//以元素作为参数时,ArrayList会查找元素,然后删除,且从头查找只删除一次,所以不能一次删除重复元素
public boolean remove(Object o) {
 if (o == null) {
  for (int index = 0; index < size; index++)
   if (elementData[index] == null) {
    fastRemove(index);
    return true;
   }
 } else {
   for (int index = 0; index < size; index++)
   if (o.equals(elementData[index])) {
    fastRemove(index);
    return true;
   }
 }
 return false;
}
private void fastRemove(int index) {
 modCount++;
 int numMoved = size - index - 1; //总共需要移动这么多元素
 if (numMoved > 0)
  //将index+1到size的元素移到index到size-1下标上
  System.arraycopy(elementData, index+1, elementData, index,
       numMoved);
 //将数组最后一个元素置为null,等待GC回收 size减一
 elementData[--size] = null; // clear to let GC do its work
}

LinkedList的remove(Object o)
//从第一个查找,找到后执行删除(unlink)
public boolean remove(Object o) {
 if (o == null) {
  for (Node<E> x = first; x != null; x = x.next) {
   if (x.item == null) {
    unlink(x);
    return true;
   }
  }
 } else {
  for (Node<E> x = first; x != null; x = x.next) {
   if (o.equals(x.item)) {
    unlink(x);
    return true;
   }
  }
 }
 return false;
}
//将该元素的上一个元素的下一个指向该元素的下一个元素,该元素的下一个元素的上一个指向该元素的上一个元素
E unlink(Node<E> x) {
 // assert x != null;
 final E element = x.item;
 final Node<E> next = x.next;
 final Node<E> prev = x.prev;

 if (prev == null) {
  first = next;
 } else {
  prev.next = next;
  x.prev = null;
 }

 if (next == null) {
  last = prev;
 } else {
  next.prev = prev;
  x.next = null;
 }

 x.item = null; //该元素中的所有属性置为null
 size--; //size减一 记录集合元素的数量
 modCount++; //modCount是AbstractList中定义的成员变量,是记录list在结构上修改的次数???不知道解释的对不对
 return element;
}
结论:根据元素删除,LinkedList的效率优于ArrayList,因为ArrayList需要循环查找和位移,而linkedList只在查找上消耗时间

remove(int index)根据下标删除元素效率比较
public void TestArrayAndLinkedList(){
 List<Integer> list1 = new ArrayList<Integer>();
 List<Integer> list2 = new LinkedList<Integer>();
 for(int i = 0; i < 100000; i ++){
  list1.add(i);
  list2.add(i);
 }
 int random1 = 2000;//(int)(Math.random()*1000);//300;
 int random2 = 9000;//(int)(Math.random()*10000);//9000;
 
 long lss1 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  list1.remove(i);
  //list1.add(i, i);
 }
 long lse1 = System.currentTimeMillis();
 long li1 = lse1 - lss1;
 System.out.println("ArrayList:---" + li1);
 
 long lss2 = System.currentTimeMillis();
 for(int i = random1; i < random2; i ++){
  list2.remove(i);
  //list2.add(i, i);
 }
 long lse2 = System.currentTimeMillis();
 long li2 = lse2 - lss2;
 System.out.println("LinkedList:---" + li2);
 
}
根据坐标删除,ArrayList的速度要快于linkedList
源码分析:
ArrayList的remove(int index)
//源码中直接根据坐标进行位移
public E remove(int index) {
 rangeCheck(index);

 modCount++;
 E oldValue = elementData(index);

 int numMoved = size - index - 1;
 if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
 elementData[--size] = null; // clear to let GC do its work

 return oldValue;
}

linkedList的remove(int index)
public E remove(int index) {
 checkElementIndex(index); //判断index是否存在集合的正常范围,超过报IndexOutOfBoundsException,调用下面的isElementIndex方法
 return unlink(node(index)); //node(index)根据index查询元素,上面有说明
}
private boolean isElementIndex(int index) {
 return index >= 0 && index < size;
}

结论:根据下标删除ArrayList的速度要快于linkedList,linkedList涉及到元素的循环查找