1.ArrayList

1.1.ArrayList集合特點

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

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ù)組，因此擴容的空間復(fù)雜度為O(n),時間復(fù)雜度為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集合特點

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

3.LinkedList

3.1.LinkedList集合特點

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

4.ArrayList、Vector、LinkedList對比

• 這三種類型的集合都是有序集合，即遍歷時輸出順序和保存順序一致。在功能上表現(xiàn)也很相似，都提供了根據(jù)角標(biāo)進行查詢、刪除、插入元素操作，都提供迭代器進行遍歷等。但是由于底層設(shè)計的區(qū)別，在性能、線程安全方面存在差異
• Vector是線程安全的，ArrayList和LinkedList都是線程不安全的。Vector的線程安全是通過在方法上添加syncronized關(guān)鍵字來實現(xiàn)的，如果不是一定要保證線程安全，不推薦使用。
• LinkedList 底部使用鏈表實現(xiàn)，它不需要像ArrayList、Vector一樣需要去動態(tài)調(diào)整容量
• Vector和ArrayList的擴容機制略有不同：Vector初始大小為10，當(dāng)保存元素數(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ù)組慢。