1.ArrayList

1.1.ArrayList集合特點

• [可容納類型] ：只能容納引用對象（基本類型需要轉換為封裝類）
• [線程安全] ：線程不安全
• [底層實現(xiàn)] ：底層使用數(shù)組實現(xiàn)顶籽，基于其實現(xiàn)方式低缩，有以下特點：初始化時需要聲明長度吧雹，超出長度需要擴容闲坎，不適合頻繁的移動魏身、刪除元素，搜索元素快
• [元素可重復] ：可重復

1.2 ArrayList排序

• 自定義排序：list.sort(new Comparator(){自定義排序規(guī)則})
• 快速排序 韩脑，使用Collections.sort(list)

1.3 ArrayList擴容

• ArrayList內(nèi)部使用Arrays.copyOf(elementData, newCapacity)進行擴容谆奥，此方法每次都會創(chuàng)建一個新的newCapacity長度的數(shù)組，因此擴容的空間復雜度為O(n),時間復雜度為O(n)

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        // oldCapacity 是舊容量菇肃，newCapacity 是新容量
        int oldCapacity = elementData.length;
        //這里進行了擴容地粪，通過位運算，將舊容量擴大為原來的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //檢查新容量是否小于最小需要容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再次檢查新容量是否大于最大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

1.4 ArrayList序列化

• ArrayList底層是由數(shù)組實現(xiàn)巷送，并且可以動態(tài)擴容驶忌，因此，保存元素的數(shù)組不一定全部會使用，也就不需要全部進行序列化
• ArrayList中提供了writeObject()和readObject來序列化或反序列化數(shù)組中有保存元素的那一部分付魔，具體使用如下

//序列化
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);

//反序列化
ArrayList list = new ArrayList();
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(file));
ois.readObject(list);

2.Vector

2.1.Vector集合特點

• [可容納類型] ：只能容納引用對象（基本類型需要轉換為封裝類）
• [線程安全] ：線程安全（通過方法上添加syncronized關鍵字保證）
• [底層實現(xiàn)] ：底層使用數(shù)組實現(xiàn)聊品，與ArrayList一樣，有以下特點：初始化時需要聲明長度几苍，超出長度需要擴容翻屈，不適合頻繁的移動、刪除元素妻坝，搜索元素快
• [元素可重復] ：可重復

3.LinkedList

3.1.LinkedList集合特點

• [可容納類型] ：只能容納引用對象（基本類型需要轉換為封裝類）
• [線程安全] ：線程不安全
• [底層實現(xiàn)] ：底層使用鏈表實現(xiàn)伸眶，有以下特點：不用聲明長度，搜索元素慢刽宪，但是插入厘贼、刪除速度快。
• [元素可重復] ：可重復

4.ArrayList圣拄、Vector嘴秸、LinkedList對比

• 這三種類型的集合都是有序集合，即遍歷時輸出順序和保存順序一致庇谆。在功能上表現(xiàn)也很相似岳掐，都提供了根據(jù)角標進行查詢、刪除饭耳、插入元素操作串述，都提供迭代器進行遍歷等。但是由于底層設計的區(qū)別寞肖，在性能纲酗、線程安全方面存在差異
• Vector是線程安全的，ArrayList和LinkedList都是線程不安全的逝淹。Vector的線程安全是通過在方法上添加syncronized關鍵字來實現(xiàn)的耕姊，如果不是一定要保證線程安全，不推薦使用栅葡。
• LinkedList 底部使用鏈表實現(xiàn)茉兰，它不需要像ArrayList、Vector一樣需要去動態(tài)調(diào)整容量
• Vector和ArrayList的擴容機制略有不同：Vector初始大小為10欣簇，當保存元素數(shù)組大小不夠時规脸，會根據(jù)capacityIncrement進行區(qū)分，如果capacityIncrement大于0熊咽，則將數(shù)組大小擴充為現(xiàn)有的size+capacityIncrement莫鸭，如果capacityIncrement小于0，則擴容為size*2

5.list的使用場景分析

• Vector和ArrayList底層使用動態(tài)數(shù)組實現(xiàn)横殴，天然適合隨機查詢和迭代遍歷操作被因，但是在刪除卿拴、添加元素時，性能較差梨与。
• LinkedList 進行節(jié)點插入堕花、刪除卻要高效得多，但是隨機訪問性能則要比動態(tài)數(shù)組慢粥鞋。