测试遍历

首先还是先上源码

  1. package collection;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.LinkedList;
  6. import java.util.List;
  8. public class ArrayListAndLinkedList {
  10.     public static void main(String[] args) {
  12.         List<String> arrayList = new ArrayList<String>();
  13.         List<String> linkedList = new LinkedList<String>();
  15.         for(long i=0; i<100000; i++){
  16.             arrayList.add(""+i);
  17.             linkedList.add(""+i);
  18.         }
  20.         /** 测试foreach循环 */
  21.         long ayyaybefore = System.currentTimeMillis();
  22.         for(String ii : arrayList){
  23.         }
  24.         long ayyayafter = System.currentTimeMillis();
  25.         System.out.println("arraylist使用foreach遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  27.         ayyaybefore = System.currentTimeMillis();
  28.         for(String ii : linkedList){
  29.         }
  30.         ayyayafter = System.currentTimeMillis();
  31.         System.out.println("linkedlist使用foreach遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  33.         /** 测试 iterator 循环 */
  34.         Iterator aiterator = arrayList.iterator();
  35.         ayyaybefore = System.currentTimeMillis();
  36.         while (aiterator.hasNext()){
  37.             aiterator.next();
  38.         }
  39.         ayyayafter = System.currentTimeMillis();
  40.         System.out.println("arraylist使用iterator遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  42.         Iterator literator = linkedList.iterator();
  43.         ayyaybefore = System.currentTimeMillis();
  44.         while (literator.hasNext()){
  45.             literator.next();
  46.         }
  47.         ayyayafter = System.currentTimeMillis();
  48.         System.out.println("linkedList使用iterator遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  50.         /** 测试for循环 */
  51.         ayyaybefore = System.currentTimeMillis();
  52.         for(int ii=0; ii<arrayList.size(); ii++){
  53.             arrayList.get(ii);
  54.         }
  55.         ayyayafter = System.currentTimeMillis();
  56.         System.out.println("arrayList使用for遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  58.         ayyaybefore = System.currentTimeMillis();
  59.         for(int ii=0; ii<linkedList.size(); ii++){
  60.             linkedList.get(ii);
  61.         }
  62.         ayyayafter = System.currentTimeMillis();
  63.         System.out.println("linkedlist使用for遍历的时间是:"+(ayyayafter-ayyaybefore)+"ms");
  64.     }
  65. }

image.png
10万条记录。很明显，不管是foreach，还是迭代器迭代，速度都差别不大，
但是对于用for循环的时，linkedlist的for循环遍历有86s之久，是arrayList的43380倍。非常恐怖。

原因分析

为什么LinkedList的for循环迭代这么慢呢？我们来分析一下原因。其实这已经与Java没啥关系了，主要是与数据结构有关了。

我们先来看看LinkedList的get(int i)做了什么：

  1. Node<E> node(int index) {
  2.     if (index < (size >> 1)) {
  3.         Node<E> x = first;
  4.         for (int i = 0; i < index; i++)
  5.             x = x.next;
  6.         return x;
  7.     } else {
  8.         Node<E> x = last;
  9.         for (int i = size - 1; i > index; i--)
  10.             x = x.prev;
  11.         return x;
  12.     }
  13. }

LinkedList的遍历，因为它是双向链表，只是说index在前一半和后一半，
分别采用正序遍历和倒序遍历以加快LinkedList的遍历速度

以前者为例：
1、get(0)，直接拿到0位的Node0的地址，拿到Node0里面的数据
2、get(1)，直接拿到0位的Node0的地址，从0位的Node0中找到下一个1位的Node1的地址，找到Node1，拿到Node1里面的数据
3、get(2)，直接拿到0位的Node0的地址，从0位的Node0中找到下一个1位的Node1的地址，找到Node1，从1位的Node1中找到下一个2位的Node2的地址，找到Node2，拿到Node2里面的数据。

后面的以此类推。也就是说，LinkedList在get任何一个位置的数据的时候，都会把前面的数据走一遍。
假如我有10个数据要遍历，那么将要查询1+2+3+4+5+5+4+3+2+1=30次数据，
相比ArrayList，却只需要查询10次数据就行了(每次都是O(1))，随着LinkedList的容量越大，差距会越拉越大。

根据以上的分析，切记一定不要使用普通for循环去遍历LinkedList。
使用迭代器或者foreach循环（foreach循环的原理就是迭代器）去遍历LinkedList即可，
这种方式是直接按照地址去找数据的，将会大大提升遍历LinkedList的效率。