對(duì)于ArrayList & LinkedList插入效率的問(wèn)題，以前的理解是 ArrayList需要將插入點(diǎn)后邊的全部數(shù)組位置改變，而LinkedList是由鏈表實(shí)現(xiàn)，因此隨機(jī)位置插入只需要斷開(kāi)node前后的指向，所以LinkedList的效率應(yīng)該是快的，可實(shí)踐的情況卻略有偏差。
上圖 代碼如下：
四種情況的運(yùn)行結(jié)果如下：
前段插入
ArrayList :342ms
LinkedList:20ms
尾部插入
ArrayList :27ms
LinkedList:43ms
中間插入
ArrayList :200ms
LinkedList:8784ms
隨機(jī)插入
ArrayList :229ms
LinkedList:6687ms
從現(xiàn)象上看，ArrayList自己的操作而言前段比尾段慢，應(yīng)該是由于每次copy數(shù)組的長(zhǎng)度不同導(dǎo)致的開(kāi)銷(xiāo)，可以理解?？墒荓inkedList在兩端的操作很快，中間非常非常慢，又是為何？
從源碼中獲的了一些猜想
LinkedList首先要找到位置為index的那個(gè)node然后把要插入的element放在它的前邊，在尋找node的過(guò)程先判斷index是在前半段還是后半段，在前半段的話從first往后找，在后半段的話從last往前找。那么如果index在中間位置的話，查找速度必然最慢。那么再回頭看看數(shù)據(jù)里的兩端快，中部慢現(xiàn)象。所以查找node節(jié)點(diǎn)的過(guò)程應(yīng)該造成了更多的開(kāi)銷(xiāo)。
