LinkedList和ArrayList的區別、Vector和ArrayList的區別

　　LinkedList和ArrayList的區別

　　繼承類和實現接口上來講

　　他們都實現了List接口下的方法，他們都允許重復，允許null，并且有序的集合。

　　LinkedList實現了Deque接口。

　　底層實現上來講

　　ArrayList底層用數組來實現，LinkedList底層用雙鏈表來實現。

　　那么ArrayList的和LinkedList的對比就會退化為數組和鏈表的區別。

　　數組隨機訪問一個元素的時間復雜度是O(1)。

　　鏈表的隨機訪問一個元素的時間復雜度是O(n)。

　　因為數組的訪問只需要給定下標，就可以立馬訪問，而鏈表需要遍歷，遍歷的次數即為下標值。

　　ArrayList 的 get() ,set()方法相對于LinkedList效率要高，ArrayList的查詢以及獲取元素，效率更高

　　數組隨機添加/刪除一個元素的時間復雜度是O(n)。

　　鏈表隨機添加/刪除一個元素的時間復雜度是O(1)。

　　因為數組隨機添加一個元素，指定下標的元素以及后面的所有元素，都需要向后移動，開銷很大，而鏈表只需要將指定位置下標的上一個的節點確定，改變引用即可，開銷很小。

　　(tips：在指定位置添加和刪除的時候，最壞情況是O(1/2 size)，因為底層調用node()方法查詢的時候，先判斷索引和 1/2 size誰打誰小，如果索引小，那么從前向后查詢，如果1/2size小，那么從后向前查詢)

　　LinkedList的add(),remove()方法，相對于ArrayList效率要高很多，LinkedList的刪除和添加元素，效率更高

　　使用上來講

　　當我們要使用集合來存儲的時候，我們應該考慮清楚，如果我們需要不斷的向集合中添加和刪除，那么就使用LinkedList 鄭州人流手術多少錢 http://mobile.chnk120.com/

　　如果更多的是不斷的獲取元素，那么就使用ArrayList。

　　Vector和ArrayList的區別

　　簡單介紹一下Vector集合。

　　Vector 繼承 自AbstractList，實現了List、Random、Colneable、java.io.Serializable接口，用數組來實現。

　　我們會發現Vector的繼承類和實現接口和ArrayList是一模一樣的。

　　構造方法：

　　無參構造器：Vector(){}，初始化數組，默認大小為10。

　　雙參： Vector(int initialCapacity, int capacityIncrement)

　　這兩個參數分別是，初始化大小和，增量，也就是指定了擴容方式。

　　單參： Vector(int initialCapacity)

　　底層調用雙參構造器，增量默認為0。

　　Vector(Collection c) ，將集合添加到Vector中。

　　擴容：grow()方法，如果需要增量沒有設置，默認兩倍擴容，如果設置了增量，那么每一次擴容一個增量的大小。

　　增刪改查的實現結構，與ArrayList沒有區別，但是方法都用了Synchronized 來修飾。也就是說Vector是線程安全的，當多線程訪問Vector時，不會引起各種各樣的錯誤。

　　所以Vector和ArrayList的區別就是：

　　Vector和ArrayList的底層實現一摸一樣，都是允許null，允許重復，有序的集合。

　　Vector在構造器可以給定增量，也就是擴容的大小，如果不給定增量，那么就2倍擴容，ArrayList默認1.5倍擴容。

　　Vector線程安全，ArrayList非線程安全