集合中ArrayList和LinkedList比较

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涉及到元素的循环查找