Java ArrayList與LinkedList數據結構和特點

1. ArrayList

數據結構：

1. ArrayList低層是實現的是一個Object類型的數組（空間連續，類型相同）
2. 當我們調用ArrayList無參構造方法，將會創建一個Object類型的**空**數組
3. 當我們第一次添加元素的時候，數組的長度會被修改為10
4. 后續添加元素，如果數組長度不夠則擴容，擴容為原數組的1.5倍

特點：有序，可重復，允許元素為null

1. 查詢，修改快：可以通過下標一次查詢定位元素，所以效率高
2. 增加，刪除慢：數組的空間是連續的，移動某個元素時，其余大部分數組也會移動，所以效率低
3. 線程不安全

2.LinkedList

數據結構：

1. LinkedList低層是雙向鏈表，鏈表中的每一個元素稱呼為一個Node（節點），每個Node包含三部分:上個元素的引用、下一個元素的引用、當前元素本身

特點：有序，空間不連續，允許元素為null，允許重復，線程不安全

1. 增加，刪除快：不需要移動元素（改變引用指向），也不需要擴容（改變引用指向），因此效率較高
2. 查詢，修改慢：因為鏈表不能直接定位到某個元素，必須找到相鄰的元素，所以查詢效率低，同理修改效率也低

注意：get(int index)方法中，對下標查詢做了優化，如果是大于等于長度，則從后往前找，否則從前往后找，以提高查詢效率，但是依然很慢