1.ArrayList和LinkedList區別

說⼀下ArrayList和LinkedList區別

1. 具體區別　　

1.1. ⾸先，他們的底層數據結構不同，ArrayList底層是基於數組實現的，LinkedList底層是基於鏈表實現的
1.2. 由於底層數據結構不同，他們所適⽤的場景也不同，ArrayList更適合隨機查找，
        LinkedList更適合刪除和添加，查詢、添加、刪除的時間複雜度不同
1.3. 另外ArrayList和LinkedList都實現了List接⼝，但是LinkedList還額外實現了Deque接⼝，所以
        LinkedList還可以當做隊列來使⽤

　　2.類結構

 2.1.ArrayList實現了List介面
        public class ArrayList<E> extends AbstractList<E> implements List<E>{...}
   
 2.2.LinkedList實現了List和Deque介面，所以LinkedList可以當做雙端隊列來進行使用：因為Deque介面中有addFirst/addLast/getFirst/getLast等操作
        public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>{...}

 　　3.效率問題

　　　　3.1 查詢：arrayList的速率會更快，因為arrayList底層是基於數組，所以獲取是通過數組下標進行獲取！

        但是linkedList.getFirst()/getLast()速率也是很快的，因為linkedList會有兩個屬性專門標註第一個元素和最後一個元素

1.arrayList.get(1);
     底層代碼：基於下標獲取
             public E get(int index) {
                rangeCheck(index);
                return elementData(index);
             }
2.linkedList.get(1);
     底層代碼:基於鏈表的操作，所以獲取在底層是進行迴圈獲取的！  
             public E get(int index) {
                ...
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
                ...
            } 

　　3.2 添加操作

1.arrayList的添加
    1.1添加元素：需要考慮底層數組的擴容，效率較慢
          arrayList.add(1);
    1.2：在指定的位置1，添加元素1：底層涉及到數組的移動，因為1位置後的數據都得往後移動，效率較慢
          arrayList.add(1,1);
2.linkedList的添加
     2.1添加元素：在末尾添加元素，因為底層是鏈表，所以添加速度較快
            linkedList.add(1);
     2.2：在指定的位置1，添加元素1:因為底層是鏈表，需要先迴圈找到要添加的位置，
如果下標數字過大，等於迴圈次數越多，效率就會越慢
下標數字小，迴圈次數小，效率快！所以此處的效率是決定於插入位置的數字大小
         linkedList.add(1,1);

總結：

 1.arrayList：查詢速率較快，但是增刪效率一般！

 2.linkedList：查詢速率較慢，但是增刪效率比arrayList快！