ArrayList與LinkedList都是線程不安全的喊儡，都沒有鎖的機制

線程安全解決辦法 ：

方法1： Collections.synchronizedList(new LinkedList<String>())

方法2: LinkedList和ArrayList換成線程安全的集合，如CopyOnWriteArrayList艘刚，ConcurrentLinkedQueue......

方法3：Vector(內(nèi)部主要使用synchronized關鍵字實現(xiàn)同步)

ArrayList

1.ArrayList是怎么實現(xiàn)可變長度的管宵，Capacity容量?

看看ArrayList的構造方法：

WechatIMG17.png

一般我們創(chuàng)建數(shù)組是用下面的方法創(chuàng)建一個空數(shù)組。那是怎么給ArrayList定義了一個常量為10的容量呢攀甚？
我們看ArrayList的add方法：
調(diào)用add方法時會調(diào)用ensureCapacityInternal這個方法：

WechatIMG18.png

image.png

最后按照新的數(shù)組長度copy一個新的數(shù)組賦值給elementData埠居，完成擴容查牌。

梳理一下流程就是：
創(chuàng)建一個容量為0的數(shù)組elementData,這個時候去添加add一條數(shù)據(jù)的時候，會minCapacity = Math.max(10, elementData.lenght+1);elementData.lenght為0 滥壕，所以得到minCapacity=10纸颜；
if (minCapacity - elementData.length > 0) grow(minCapacity); 此時滿足擴容條件去擴容，

private void grow(int minCapacity) {//minCapacity=10
        // overflow-conscious code
        int oldCapacity = elementData.length;//初始為0
        int newCapacity = oldCapacity + (oldCapacity >> 1);//按1.5倍擴容绎橘，新的也為0
        if (newCapacity - minCapacity < 0)//滿足這個條件
            newCapacity = minCapacity;//新容量為10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//copy一個容量為10的賦值給elementData胁孙，得到一個最新的長度為10的數(shù)組。此方法是耗時的
    }

同理称鳞，如果addAll了一個長度超過10的數(shù)據(jù)涮较，假設是15，則創(chuàng)建的elementData的長度就為addAll之后的長度15冈止。

因此：在使用ArrayList時狂票，如果你能預估大小，最好直接定義初始容量熙暴，這樣能節(jié)省頻繁的擴容帶來的額外開支闺属。

ArrayList插入數(shù)據(jù)：

//這個代碼功能就是該方法的作用是拷貝一份長度為length的臨時數(shù)組，將elementData數(shù)組中的index到size-1之間的數(shù)據(jù)拷貝到臨時數(shù)組中怨咪，放入index+1到size的里---->這里add(int index,E e)的用法是將index開始的元素全部后移空出一位屋剑，讓新元素加入進來
//換句話說就是拷貝一份臨時的空數(shù)組[]，然后再執(zhí)行后面的elementData[index] = element;把插入的數(shù)據(jù)賦值給index位置
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!! 判斷是否需要擴容
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//插入數(shù)據(jù)的核心代碼
        elementData[index] = element;
        size++;
    }

remove方法同理,將數(shù)組的后面4個依次向前移動一位诗眨，然后將數(shù)組最后一位置為null。

LinkedList

get()方法

判斷index值是否大于總數(shù)的一半
如果小于孕讳，則從first節(jié)點向后遍歷匠楚，直到找到index節(jié)點，然后返回該節(jié)點的值厂财。
如果大于芋簿，則從last節(jié)點向前遍歷，直到找到index節(jié)點璃饱，然后返回該節(jié)點的值与斤。

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    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;
        }
    }

add()方法

沒有指定添加的索引則默認添加在最后一個位置，將鏈表的first荚恶，next互相連接起來
指定索引時：

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

        if (index == size)
            linkLast(element);
        else //判斷要添加的索引不是最后一個位置時
            linkBefore(element, node(index)); //node(index)找到對應索引的值
    }

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev; //索引Node對應的前一個Node
        final Node<E> newNode = new Node<>(pred, e, succ);//插入數(shù)據(jù)的Node
        succ.prev = newNode;//把索引Node對應的賦值為插入的數(shù)據(jù)
        if (pred == null) //判斷索引Node對應的前一個Node為null,說明是第一個數(shù)據(jù)撩穿，插入數(shù)據(jù)時把插入的Node賦值給第一個數(shù)據(jù)
            first = newNode;
        else
            pred.next = newNode; //否則把索引Node對應的前一個Node的next賦值為newNode.
        size++;
        modCount++;
    }

remove()方法

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next; //拿到當前索引對應的前一個Node和后一個Node
        final Node<E> prev = x.prev;

        if (prev == null) {//如果前一個Node為null,說明索引是0，則把后一個Node賦值給first
            first = next;
        } else {
            prev.next = next;//否則谒撼，把前一個Node的next 賦值為后一個Node
            x.prev = null;
        }

        if (next == null) {//如果后一個Node為null,說明索引是最后一個數(shù)據(jù)食寡，則把前一個Node賦值給last
            last = prev;
        } else {
            next.prev = prev;//否則，把后一個Node的next 賦值為后一個Node
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

由于LinkedList是一個雙向鏈表廓潜，因此不需要擴容機制抵皱，直接在前后添加元素即可善榛。

對比
由上面的常用方法可以發(fā)現(xiàn)

1.ArrayList使用數(shù)組存儲元素，因此在查詢時速度較快呻畸，直接返回該位置的元素即可移盆，時間復雜度為O(1);而LinkedList使用雙向鏈表存儲元素，在查詢時需要從頭或者尾遍歷至查詢元素伤为，時間復雜度為O(n/2);

2.還是因為存儲方式的問題咒循，ArrayList在插入或者刪除時，需要移動插入位置之后的所有元素钮呀，因此速度較慢剑鞍，時間復雜度為O(n)。而LinkedList只需要找到該位置爽醋，移動”指針”即可,時間復雜度為O(1)蚁署。