一、ArrayList和LinkedList区别

一、先来看看ArrayList和LinkedList在JDK中的位置

image.png

从图中可以看出，ArrayList和LinkedList都是List接口的实现类，而List接口继承了Collection接口，Collection接口又继承了Iterable接口，因此可以得出 List同时拥有了Collection与Iterable接口的特性

• ArrayList是实现了基于动态（线性表）数组的数据结构，LinkedList基于链表的数据结构。
• 对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。
• 对于新增和删除操作add和remove，LinkedList是优于ArrayList,因为ArrayList要移动数据。

二、ArrayList介绍

定义ArrayList是需要指定长度的，如果不指定它默认长度是10

    /**
    * Default initial capacity.
    */
   private static final int DEFAULT_CAPACITY = 10;

而且支持动态扩容，源码中调用的就是 ensureCapacityInternal(size+1) >>> ensureExplicitCapacity(minCapacity) >>> grow(minCapacity)中

   // overflow-conscious code
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);

通过这个方法进行动态扩容新增加的容量大小为原容量大小的50%（扩大一倍）

源码的角度来看一下如何实现add、remove、get等操作

    public boolean add(E e) {
        // 检查是否需要增容
        ensureCapacityInternal(size + 1);  
        //size++ 将新增元素存入elementData数组中
        elementData[size++] = e;
        return true;
    }

    /**
    * 将元素插入指定位置，后面的元素往右移动
    **/
    public void add(int index, E element) {
        if (index > size || index < 0)
            //Exception：数组越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        // 检查是否需要增容
        ensureCapacityInternal(size + 1);  
        //核心代码
        //源数组，要复制的启始位置是 index
        //源数组的元素 复制到目标数组 并且从 index+1（+1腾出我们要插入元素的位置） 的位置启始 长度是 size-index
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //将新元素赋值到elementData[index]
        elementData[index] = element;
        size++;
    }

    public E get(int index) {
        if (index >= size)
            //Exception：数组越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //直接通过参数index从element中取出元素
        return (E) elementData[index];
    }
    
    public E remove(int index) {
        if (index >= size)
            //Exception：数组越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];
        //假如elementData现有10个元素，index要移除的是 7 
        //numMoved = 10 - 7 - 1 = 2
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //ed, 7+1 , ed, 7 , 2
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
             //Object src : 源数组
             //int srcPos : 源数组要复制的起始位置
　　         //Object dest : 目标数组
　　         //int destPos : 目标数组的开始起始位置
　　         //int length  : 要复制的数组的长度
            
        //上面这段代码就是
        //源数组，7+1为复制的启始位置（+1去掉了我们要remove的元素下标）
        //源数组要复制的元素 复制到目标数组 并且从 7 的位置启始 长度是 2

        //将最后一个元素赋值为null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

三、LinkedList介绍

LinkedList是双向链表数据结构，通过内部Node first和last两个变量来实现

未完待续....

----------- 还有List接口下的Vector和Vector下的Stack -----------

参考链接 Vector和Stack(已过时，不建议使用)

四、总结

ArrayList

• 优点：读取速度快
• 缺点：添加元素慢（一方面在array中插入元素，需要右移）元素；另一方面，长度容量不够时，需要增容

LinkedList

• 优点：添加值很快（在array中插入元素，只需要改指针）长度不固定
• 缺点：读取速度慢（需要移动指针寻找元素）

---

如有误点，多多指教 喜欢呦~