～、結(jié)構(gòu)

ArrayList位數(shù)組結(jié)構(gòu)，LinkedList為雙向鏈表結(jié)構(gòu)。

～、空間

ArrayList有固定容量，超出容量后需要擴容，在數(shù)組尾部可能保存有占位的null元素

LinkedList無固定容量，但每個元素都放在節(jié)點中，每個節(jié)點都有2個額外的定位指針（prev 和 next），第一個和最后一個節(jié)點的prev和next都指向null

～、方法及效率對比

—：add

1、add()

ArrayList在數(shù)組的最后追加，額外操作僅僅是數(shù)組滿了的擴容

LinkedList在鏈表的最后追加同addLast()，每次創(chuàng)建一個新節(jié)點（新節(jié)點的prev指針指向之前的最后一個節(jié)點last），last的next指針指向新節(jié)點。每次都需給2個指針賦值。效率不如ArrayList

2、add(int index, E element)

ArrayList在數(shù)組的指定index位置添加元素element，每次都需調(diào)用System.arraycopy() 拷貝數(shù)組

LinkedList只是創(chuàng)建一個prev指針指向index前一個元素，next指針指向index元素的節(jié)點，并將index前節(jié)點的next指針和index節(jié)點的prev指針指向新節(jié)點。與前面的在最后添加差不多，此時效率要遠遠高于ArrayList

3、在結(jié)構(gòu)最前面添加，ArrayList只能用 add(0, e)。而LinkedList除add(0, e)外還可以用addFirst(e)。同樣LinkedList效率高于ArrayList

—：get

1、get(int index）

ArrayList直接取數(shù)組下標得到元素值

LinkedList需要遍歷鏈表取到index位置的節(jié)點，再得到節(jié)點的item值。效率受鏈表長度和index在鏈表位置的影響

2、get遍歷

for遍歷

ArrayList數(shù)組長度及循環(huán)次數(shù)，一個元素只循環(huán)一次。LinkedList每取一個數(shù)都重新遍歷鏈表，一個元素最多遍歷 鏈表長/2次。

foreach遍歷

先將集合轉(zhuǎn)Iterator，循環(huán)次數(shù)都為元素的個數(shù)。

ArrayList2種方式都可，LinkedList要求使用foreach

—：remove

1、remove(int index)

ArrayList刪除指定下標的元素，需調(diào)用System.arraycopy()函數(shù)，再將最后一個元素賦null

LinkedList刪除指定下標的節(jié)點，改變index節(jié)點的prev節(jié)點的next為index的next，index的next節(jié)點的prev為index的prev，再清理index節(jié)點的item為null。效率也比ArrayList好。

2、remove(Object o)

刪除數(shù)組或鏈表中第一次出現(xiàn)的與o相等的元素，先查找再刪除，刪除步驟同第一點。

3、remeve()，removeFirst()，removeLast()

3個方法都只是LinkedList所有。removeFirst()和remove()方法刪除第一個節(jié)點。removeLast()刪除最后一個節(jié)點。

—：set

1、set(int index, E element)

替換index位置的元素為element。

ArrayList直接取數(shù)組下標賦值。

LinkedList首先遍歷鏈表取到index位置的節(jié)點，再將節(jié)點的item賦值。如果鏈表比較大切index在鏈表中間位置會很浪費時間。