1，两个list简单概括。

ArrayList数据结构就是数组（更确切的说是动态数组）

LinkedList数据结构是双向链表。

其他信息各位自行了解，随便在哪都能搜到。这篇文章注重对性能对比。

2，添加元素

(建议大家实测)

（1）从第一个位置添加

ArrayList<Integer> arrayList=new ArrayList<>();
        LinkedList<Integer> linkedList=new LinkedList<>();
        int times=100000;
        long t1=System.nanoTime();
        for (int i = 0; i < times; i++) {
            arrayList.add(0,i);
        }
        long t2=System.nanoTime();
        for (int i=0;i<times;i++){
            linkedList.addFirst(i);
        }
        long t3=System.nanoTime();

        System.out.println("arrayList:"+(t2-t1)/1000+"    linkedlist:"+(t3-t2)/1000);

结果

截屏2020-04-11下午5.42.05.png

很明显，arraylist和linkedlist相比，在第一个位置添加元素 linkedlist要快很多。
分析：
linkedlist在头部添加最终是执行的这块代码

private void linkFirst(E e) {
       final Node<E> f = first;
       final Node<E> newNode = new Node<>(null, e, f);
       first = newNode;
       if (f == null)
           last = newNode;
       else
           f.prev = newNode;
       size++;
       modCount++;
   }

由于Linked维护了头结点（first），代码内容无非就是改变引用的指向实现插入节点。插入一个元素时间复杂度为O（1）。
而arrayList在头部添加代码实现：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

方法内第一行代码是检查index位置是否合法，第三行则是检查是否要扩容。第四行代码是通过arrayCopy方法实现插入位置及插入位置之后的的元素后移一位。第五行代码则是插入元素。由于第四行代码源码我找不到，不过既然要后移一位，插入一个时间复杂度是O（n）。
由此便可知原因。

（2），在中间随机添加元素。

测试代码：

System.out.println("随机插入测试");
        //testNanoTime();
        //testMillinsTime();
//        ArrayList<Integer> arrayList=new ArrayList<>();
//        LinkedList<Integer> linkedList=new LinkedList<>();
        //先填充五个元素
        for (int i = 0; i < 5; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        //次数
        int times=150000;

        //开始进行中间插入测试
        long t1=System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            arrayList.add(arrayList.size()/2,i);
        }
        long t2=System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            linkedList.add(linkedList.size()/2,i);
        }
        long t3=System.currentTimeMillis();

        System.out.println("arraylist:"+(t2-t1)+"  linkedlist:"+(t3-t2)+"  两者倍数："+(t3-t2)/((t2-t1)*1.0));

结果

截屏2020-04-15上午12.59.22.png

分析：
(如果你自己尝试的话你会惊奇的发现当插入的数量越大时，耗时倍数越趋近于40倍)
很明显arraylist在中间插入相同数量的元素反而比linkedlist快，很奇怪是吗？当我们学数据结构的时候常识告诉我们链表插入比数组快。但是注意，数据结构中的插入是单纯的考虑插入这个动作，而linkedlist，执行remove，要通过这个方法：

截屏2020-04-15上午1.04.08.png

而这个方法的源码是：

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

if判断条件是根据index与长度的二分之一比较，以此根据使用头结点或者尾结点来定位元素位置。以此来尽可能提高效率。这个过程每定位一个元素，时间复杂度为O(n).
而arraylist依然是通过arrayCopy进行移位，然后插入。对于每次操作时间复杂度依然为O(n)。虽然时间复杂度差不多，但是，arrayCopy方法的性能比linkedList中的定位过程效率高，如果你细心测试，你会发现插入的节点越多两者耗时倍数越接近40倍。以此得出结论，在中间插入arraylist比Linkedlist效率高。

（3）, 在尾结点进行插入。

贴上测试代码：

public static void endAddtest(){
        System.out.println("尾部插入测试");
        testNanoTime();
        testMillinsTime();
        ArrayList<Integer> arrayList=new ArrayList<>();
        LinkedList<Integer> linkedList=new LinkedList<>();
        int times=10000000;
        long t1=System.nanoTime();
        for (int i = 0; i < times; i++) {
            arrayList.add(i);
        }
        long t2=System.nanoTime();
        for (int i=0;i<times;i++){
            linkedList.addLast(i);
        }
        long t3=System.nanoTime();

        System.out.println("arrayList:"+(t2-t1)/1000+"    linkedlist:"+(t3-t2)/1000);
    }

截屏2020-04-15上午1.23.53.png

两者差距不大（通过多次尝试依然是arraylist较快），具体原因通过以上分析很容易理解。
arraylist，里面首先判断是否扩容，然后进行插入。linkedlist直接在尾结点插入。
贴上源码，不做过多赘述。
arraylist:

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

linkedlist:

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

总结：arraylist在尾结点插入比linkedlist速度略快。

3,删除节点。

删除节点与添加节点一样。不做过多赘述。
删除第一个节点，arraylist比linekdlist慢
删除中间节点和在中间添加节点结论一样，arraylist比linkedlist快。
删除最后一个节点时间复杂度时间复杂度虽然一样，但是arraylist比linkedlist略快。

4，遍历

实测，结论，
arraylist中的遍历方式耗时比较：
fori<foreach<itreator，注意，这里foreach位置不一定，有时快有时慢，与环境和list长度有关。

linkedlist遍历耗时：
fori>foreach>iterator,注意foreach同上，耗时不稳定。

（网上有种说话：foreach底层也是用迭代器。对此我没有深入研究，先且相信这个结论）

最后贴上总结论：

image.png