ArrayList是利用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)。由于是動(dòng)態(tài)數(shù)組，在add或者remove的時(shí)候，會需要將數(shù)組的i+1到size()的所有元素往后移一位，要是遇到了數(shù)組長度不夠的情況下還會創(chuàng)建一個(gè)新數(shù)組是舊數(shù)組的長度的兩倍，耗費(fèi)的代價(jià)是巨大的，但是在操作get和set的時(shí)候時(shí)間復(fù)雜度是O(1)。

而LinkedList是通過雙向鏈表去實(shí)現(xiàn)，在java中并沒有指針，于是使用了node的對象，儲存date和下一個(gè)的node對象和上一個(gè)的node對象。在進(jìn)行add或者remove操作時(shí)，通過對指定元素的上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的指向就能簡單的實(shí)現(xiàn)，但是在這之前需要找出對應(yīng)的節(jié)點(diǎn)，需要進(jìn)行一次O(N/2)代價(jià)的操作。