fail-fast機(jī)制：Iterator的concurrentModifiedException

• 在迭代器生成后一邊讀取一邊修改就會(huì)出現(xiàn)這個(gè)問題

        Map<Integer, Integer> maps = new HashMap<>();
        maps.put(1, 2);
        maps.put(3, 1);
        Iterator<Integer> keys = maps.keySet().iterator();
        while (keys.hasNext()) {
            int tmp = keys.next();
            System.out.println(tmp);
            maps.put(tmp + 1, tmp + 1);
        }
//拋出concurrentModifiedException異常

ArrayList

• 數(shù)組做為內(nèi)部存儲(chǔ)結(jié)構(gòu)
• 尋址操作的時(shí)間復(fù)雜度為O(1)
• 為什么ArrayList實(shí)現(xiàn)了RandomAccess并且RandomAccess是空的？因?yàn)镽andomAccess是標(biāo)記函數(shù)，標(biāo)記函數(shù)就是jvm中標(biāo)記這個(gè)接口可以實(shí)現(xiàn)但沒有提供任何的實(shí)現(xiàn)。
• 查找時(shí)間復(fù)雜度：O(1)；插入和刪除時(shí)間復(fù)雜度：O(n)
• 擴(kuò)容是如何實(shí)現(xiàn)的：內(nèi)部自動(dòng)實(shí)現(xiàn)的，把容量擴(kuò)充為之前的1.5倍，然后拷貝Arrays.copyOf方法。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

LinkedList

• 雙向鏈表作為內(nèi)部的存儲(chǔ)結(jié)構(gòu)
• 查找 + 插入/刪除的時(shí)間復(fù)雜度：O(n)
• 頭尾插入或者刪除的時(shí)間復(fù)雜度：O(1)

LinkedList和ArrayList的區(qū)別

1、底層數(shù)據(jù)結(jié)構(gòu)不同；一個(gè)是數(shù)組，一個(gè)是鏈表；
2、適用場(chǎng)景 不同，ArrayList適合用于尋址操作，LinkedList適用于頭尾刪除。