ArrayList是如何插入、刪除數(shù)據(jù)的？

image.png

1.當(dāng)插入一個(gè)data的時(shí)候會(huì)先檢查數(shù)組是否需要擴(kuò)容。

擴(kuò)容的機(jī)制并不是說我需要添加N個(gè)數(shù)據(jù) 我就擴(kuò)N個(gè)位置，而是有默認(rèn)大小10個(gè)長(zhǎng)度，當(dāng)位置不夠時(shí)通過位運(yùn)算擴(kuò)大1.5倍。因此當(dāng)存放大量數(shù)據(jù)時(shí)，每次擴(kuò)容都會(huì)消耗很多資源。
具體請(qǐng)參考（https://www.cnblogs.com/baichunyu/p/12965241.html）

擴(kuò)容代碼.png

2.數(shù)據(jù)復(fù)制與賦值

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

將data后面的數(shù)據(jù)G、H、I進(jìn)行復(fù)制并賦值到后面一位并將data賦值到指定位置

image.png

這樣就完成了一次add，當(dāng)我們插入的數(shù)據(jù)后面數(shù)據(jù)越多就會(huì)越消耗性能，越慢。刪除也是同理。

LinkedList是如何插入、刪除數(shù)據(jù)的？

LinkedList是典型的鏈表設(shè)計(jì)（雙向鏈表）

鏈表設(shè)計(jì)圖.png

每個(gè)數(shù)據(jù)都包含了本數(shù)據(jù)和上一個(gè)數(shù)據(jù)的指針與下一個(gè)數(shù)據(jù)的指針。

• LinkedList.Node.class

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

當(dāng)你需要添加數(shù)據(jù)時(shí)，只需要將數(shù)據(jù)填入鏈表，并修改對(duì)應(yīng)數(shù)據(jù)的指針既可以實(shí)現(xiàn)。

總結(jié)

由此可見，當(dāng)需要插入數(shù)據(jù)時(shí)，LinkedList的性能是優(yōu)于ArrayList的。
相反，當(dāng)你需要查詢數(shù)據(jù)的時(shí)候，ArrayList是更快的，因?yàn)锳rrayList是數(shù)組，直接通過下標(biāo)就可以訪問到，而鏈表需要你循環(huán)找到位置。