Java 基礎知識 — Collection 類知識點整理與總結

文章目錄

• 一、繼承結構圖
• 二、List 和 Set
• • 2.1 List
  • 2.2 Set
  • 2.3 驗證 List、Set 接口特性
  • 2.4 List 和 Set 常見的實作類介紹
  • • 2.4.1 數組和連結清單優缺點
    • 2.4.2 ArrayList
    • 2.4.3 LinkedList
    • 2.4.4 Vector

一、繼承結構圖

相對于數組而言，集合彌補數組的一些不足，存儲對象類型單一，數組大小固定(初始化設定)，當我們不指定泛型類型的時候，可以存儲任意類型，集合大小也會随着需求而變，由繼承關系圖、文檔中可看出：

• Collection 接口是集合類的根接口，一個集合代表一組 Object 對象，可以被視為集合的元素，有的集合允許重複，有的不允許，有的是有序的，有的是無序的，JDK 中并沒有提供 Collection 接口的直接實作類，它提供了更具體的子接口的實作，如 Set 和 List ，下面分析。
• Iterator 所有的集合類，都實作了Iterator接口，這是一個用于周遊集合中元素的接口，主要包含以下三種方法：
  • hasNext 是否還有下一個元素
  • next 傳回下一個元素
  • remove 删除元素

二、List 和 Set

2.1 List

官方文檔中對 List 接口描述如下：

從上面的描述中可以得到以下資訊：

• 一個有序的集合
• 允許有重複資料，并且允許多個 null 值
• 提供了一個疊代器 ListIterator
• List 接口最常用的實作類是 ArrayList、LinkedList 和 Vector

2.2 Set

從上面的描述中可以得到以下資訊：

• 一個無序的集合
• 不允許有重複資料，并且最多隻允許有一個 null 值
• Set 接口最常用的實作類是 HashSet、LinkedHashSet 以及 TreeSet

2.3 驗證 List、Set 接口特性

//---------------驗證是否允許添加重複資料------------------
 		List<String> stringList = new ArrayList<>();
        stringList.add("hello_world_1");
        stringList.add("hello_world_1");
        stringList.add("hello_world_2");
        stringList.add("hello_world_3");
        stringList.add("hello_world_4");
        stringList.add("hello_world_5");
        stringList.add("hello_world_5");

        Log.e("spspsp", "listSize= " + stringList.size());

        Set<String> stringSet = new HashSet<>();
        stringSet.addAll(stringList);

        Log.e("spspsp", "setSize= " + stringSet.size());

		//日志資訊--------（1）
		E/spspsp: listSize= 7
		E/spspsp: setSize= 5
		
		//---------------驗證有序、無序------------------
		
		for (String list:stringList){

            Log.e("spspsp", "輸出list的元素，依次為=" + list);
        }

        for (String set:stringSet){

            Log.e("spspsp", "輸出set的元素，依次為=" + set);
        }
		
		//日志資訊--------（2）
		E/spspsp: 輸出list的元素，依次為=hello_world_1
 		E/spspsp: 輸出list的元素，依次為=hello_world_1
 		E/spspsp: 輸出list的元素，依次為=hello_world_2
 		E/spspsp: 輸出list的元素，依次為=hello_world_3
 		E/spspsp: 輸出list的元素，依次為=hello_world_4
 		E/spspsp: 輸出list的元素，依次為=hello_world_5
		E/spspsp: 輸出list的元素，依次為=hello_world_5

		E/spspsp: 輸出set的元素，依次為=hello_world_1
		E/spspsp: 輸出set的元素，依次為=hello_world_4
		E/spspsp: 輸出set的元素，依次為=hello_world_5
		E/spspsp: 輸出set的元素，依次為=hello_world_2
		E/spspsp: 輸出set的元素，依次為=hello_world_3
	
		//---------------驗證元素為 null 的個數------------------
		stringList.add(null);
        stringList.add(null);
        stringList.add(null);
        Log.e("spspsp", "listSize=" + stringList.size());

        stringSet.add(null);
        Log.e("spspsp", "setSize=" + stringSet.size());
		
		//日志資訊--------（3）
		E/spspsp: listSize= 10
		E/spspsp: setSize= 6

		//繼續修改上面的代碼，stringSet 添加兩個 null 元素
		stringSet.add(null);
        stringSet.add(null);
        Log.e("spspsp", "setSiz=" + stringSet.size());
		
		//日志資訊--------（4）
		E/spspsp: setSize= 6
	
           

根據上面的日志資訊總結如下

• 根據日志資訊（1）知：實作 List 接口的類，可添加重複資料，而實作 Set 接口的類将重複資料去除，在日常開發中，通常借助 Set 的這個特性來去除 List 中重複資料。
• 根據日志資訊（2）知：實作 List 的接口的類，輸出元素的順序即為元素插入時的順序，而實作 Set 接口的類輸出順序則無規律。
• 根據日志資訊（3）和（4）知：實作 List 的接口的類，可允許添加多個值為 null 的元素，而實作 Set 接口的類隻允許添加一個值為 null 的元素，最後一步雖然添加了兩個值為 null 的元素，但 Size 依然是 6。

2.4 List 和 Set 常見的實作類介紹

2.4.1 數組和連結清單優缺點

強行插入這兩個概念有助于對後續介紹的 ArrayList、LinkedList 等底層實作原理的了解有很大幫助，這篇文章對數組和連結清單的差別分析的比較清晰，以下通過表格形式展示數組、連結清單的優缺點：

比較方面	數組	連結清單
優點	随機通路性強，查找速度快	插入删除速度快，記憶體使用率高，大小不固定，拓展很靈活。
缺點	插入和删除效率低，可能浪費記憶體，記憶體空間要求高，必須有足夠的連續記憶體空間。此外，數組大小固定，不能動态拓展	不能随機查找，必須從第一個開始周遊，查找效率低

注意：(個人觀點)随機通路性，對于一種資料存儲結構而言，通路到其中任一節點的複雜度，簡單地了解為，通路每個節點的難易程度。

數組：可通過下标直接通路，比如 [4] 通路的就是第 5 個節點

連結清單：要想通路第 5 個節點，必須從頭結點依次去找

2.4.2 ArrayList

基本特點

• 有序
• 随機通路性強（查詢快）
• 底層實際操作的是一個 Object [ ]
• 添加、删除慢，有些情況會用到底層擴容機制，牽一發而動全身，添加、删除一個資料，動用整個數組所有元素的下标。

類實作結構

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
           

• 實作 List，元素是有序的,可以重複的,可以有 null 元素。
• 實作 Cloneable，支援複制
• 實作 Serializable， 支援序列化
• 實作 RandomAccess，支援快速通路，RandomAccess 作為一種标記性接口，其作用主要适用于判斷，通過判斷是否實作該接口，來執行不同的算法。

上面關于 RandomAccess 的描述可用以下僞代碼表示

if (list instanceof RandomAccess){
		
	 do something();
 }else{
	
	 do something else();
 }
           

在 Collection 類中 shuffle 方法代碼如下：

public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }
           

在這裡，對于實作了該接口，建議使用 for 循環來周遊資料，否則，建議使用 Iterator 來周遊資料。

成員變量

//預設容量
    private static final int DEFAULT_CAPACITY = 10;
    //空數組
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //預設容量的空數組
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //arraylist 資料緩存區（該 ArrayList 的容量大小 = elementData.length（緩沖區長度））
    transient Object[] elementData;
    private int size;
           

注意：elementData，源碼中給出的解釋：該數組是存放 ArrayList 資料的緩沖區，ArrayList 的大小即該數組的大小，當第一個元素被添加至高緩沖區時，任何帶有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 将被擴容至預設容量大小

transient 使變量不被序列化

構造函數

//無參構造函數
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //一個參數的構造函數，參數：指定一個初始容量
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //一個參數的構造函數，參數：指定一個集合
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
           
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
           

對 ArrayList 源碼進行分析

添加元素

假設通過無參構造函數建立 ArrayList 執行個體，增加一個元素

public boolean add(E e) {
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
           

假設，使用無參的構造函數進行初始化，并且第 1 次添加元素，上面的流程完整如下：

• 首先調用 ensureCapacityInternal 方法，此時還未添加元素，是以 size = 0，則該方法傳遞的參數是 size + 1 = 1。
• 由上步可知，minCapacity = 1，并且此時的 ArrayList 容量(elementData.length = 0)，則滿足條件 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，進入判斷擷取 DEFAULT_CAPACITY 和 minCapacity 中較大的值賦給 minCapacity，預設初始化為 10。
• 緊接着調用 ensureExplicitCapacity(int minCapacity) 且知 minCapacity = 10，進入方法内部先去執行 modCount 自增，代表操作次數，暫且先不管，接着又是一個判斷，這裡判斷 minCapacity 和 elementData.length 的大小，若 minCapacity 大，則進行擴容即執行 grow(minCapacity) 方法，否則不用進行擴容，也就是到這裡就結束了。然而在前面假定的條件下 elementData.length = 0，是以 if 條件為 true，首次進行擴容。
• 由上步可知 grow(minCapacity) 的參數 minCapacity = 10，接着将 elementData.length 的值賦給 oldCapacity = 0 作為舊容量，又将 oldCapacity + (oldCapacity >> 1) 的值賦給 newCapacity = 0 作為新容量，進而滿足條件 newCapacity < minCapacity，最後把 minCapacity 指派給 newCapacity，即 newCapacity = minCapacity = 10，最後執行 elementData = Arrays.copyOf(elementData, newCapacity)，結果是 elementData = [null, null, null, null, null, null, null, null, null, null] ，即 elementData.length = 10。
• 最後回到 add(E e) 方法中執行 elementData[size++] = e，此刻，size = 0，對于這句代碼可以了解成 elementData[ 0 ] = e，然後 size 自增加 1，到這裡該情況下的分析就全部結束了。

在上面基礎上，ensureCapacityInternal(int minCapacity) 方法中，if 判斷不成立，這是因為 elementData 的容量已不再為 0，上面已經詳細的分析過了，在這就不再贅述了，是以将直接去執行 ensureExplicitCapacity(minCapacity) 方法。當第 2…10 次去添加元素的時候，在 ensureExplicitCapacity(int minCapacity) 方法中，minCapacity 的最大值才是 10（當第 10 次添加，意味着數組中已經添加 9 個元素，在 add(E e) 方法中 size = 9 時，size + 1 = 10 即 minCapacity 最大），minCapacity > elementData.length 不成立，也就意味着不需要區擴容。當第 11 次添加元素時，又會進行擴容，由 grow 方法中 int newCapacity = oldCapacity + (oldCapacity >> 1) 可看出 ArrayList 内部的擴容前後容量變化即新容量是舊容量的 1.5 倍。

在 grow 方法中，當 newCapacity 非常大乃至大于 MAX_ARRAY_SIZE 的時候，則會執行方法 hugeCapacity(int minCapacity)，在該方法中，先判斷 minCapacity 是否小于 0，小于 0，則會報記憶體溢出，緊接着會判斷 minCapacity(可允許的最小的容量)是否大于 MAX_ARRAY_SIZE，大于會将 Integer.MAX_VALUE 賦給 newCapacity，反之，MAX_ARRAY_SIZE 賦給 newCapacity。

删除元素

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
           

相對于 add 方法，remove 方法還是比較簡單的，進入方法内部首先會對 index 進行判斷，若 index >= size，則會報數組越界。numMoved 表示需要移動元素的個數，當 numMoved > 0 時，會将數組 elementData 從下标為 index 位置，向後截取 numMoved 個元素，整體向前挪一位。緊接着讓 size 先自減 1，然後讓緩沖區數組 elementData 中之前下标為 size-1 處的元素設定為 null，以便 GC 回收，最後再将被删除的元素傳回。

舉個例子友善與了解 System.arraycopy，假設有兩個完全相同的數組 A = B = { a，b，c，d，e }，現在要删除數組 A 中下标 index = 1 處的資料（即元素 b），由數組存儲結構的連續性可知，index = 1 後面的所有資料（即 numMoved 3 個元素）取出來，覆寫掉數組 B 中下标 index = 1 開始的三個資料，則最新的 B 數組元素為 { a，c，d，e，e }，接着執行 elementData[–size] = null ，該操作可拆分成兩步，先讓 B 數組的 size 自減 1（即 size = 4），再執行 elementData [ 4 ] = null，以便 GC 回收，經過此操作後，B 數組元素為 { a，c，d，e }。注意，本例僅為了友善了解，不要太糾結例子，除此之外，本例中的數組 A 對應源碼中複制操作前的 elementData，數組 B 對應源碼中複制操作後的 elementData。

2.4.3 LinkedList

基本特點

• LinkedList 底層資料結構基于連結清單來實作（解釋見下方）
• 相對于 ArrayList，插入、删除快，查詢慢，不具有随機通路性

連結清單分類如下：

圖檔均來自于這裡并且有對應的解釋，需要的可以進去了解一下。

單連結清單結構圖：

每個節點包含 data、next 兩部分

data 代表目前節點中包含的資料，next 表示指針，指向後一個節點

單連結清單的特點就是尾節點的 next 指向 null

單向循環連結清單結構圖：

與單連結清單不同的是單向循環鍊尾節點的 next 指向頭結點，形成循環

雙連結清單結構圖：

與上面最大的不同在于每個節點中有兩個指針 pre、next，pre 指向前一個節點

雙向循環連結清單表結構圖：

類比單連結清單和單向循環連結清單的關系，頭結點 pre 指針指向尾節點、尾節點 next 指針指向頭結點

既然 LinkedList 底層資料結構基于連結清單來實作，翻看源碼發現在 LinkedList 的内部有一個靜态類定義了節點，代碼如下：

private static class Node<E> {
        E item;		//目前節點中存儲的資料
        Node<E> next;	//下一個節點
        Node<E> prev;   //上一個節點
		//構造節點的方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
           

由上面的代碼可知， LinkedList 底層的連結清單其實是一個雙連結清單，每個節點裡面包含兩個指針 prev、next 分别指向前一個節點、後一個節點，item 表示目前節點中存儲的資料

從源碼角度分析 LinkedList 的實作原理

成員變量和構造函數

transient int size = 0;    //清單大小
	transient Node<E> first;   //頭結點
	transient Node<E> last;    //尾節點
	public LinkedList(){}  //構造一個空清單
	//建構一個 list 該 list 包含指定集合的所有元素
	public LinkedList(Collection<? extends E> c) {
   	 this();
    	addAll(c);
	}
	public boolean addAll(Collection<? extends E> c) {
    	return addAll(size, c);
	}
	public boolean addAll(int index, Collection<? extends E> c) {
        // 檢查下标 index 是否合法
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
		// 當 index == size 為 true，表示目前是個空連結清單
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
		// 利用 for 循環将插進來數組中的元素結合 pred 生成新節點并依次拼接
        for (Object o : a) {
           
            E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
		// 由上面可知：當 index = size，即目前是空連結清單時 succ = null 成立
        if (succ == null) {	
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }
	private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}
	// 判斷 index 是否越界
	private boolean isPositionIndex(int index) {
    	return index >= 0 && index <= size;
	}
	//擷取目前 index 的節點
	Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

           

上面注釋很清晰，這裡就不再贅述，下面會單獨講解有參數的構造方法

從有參構造函數跟進，首先會發現調用方法 addAll（c） 方法，接着又會發現 addAll（c） 方法内部其實調用的是方法 addAll（size，c） ，在該方法内部首先判斷下标是否越界，接着将集合轉換成數組 Object 類型的數組 a，并把數組長度賦給 newNum，判斷數組長度是否為 0，若為 0，則傳回 false，說明作為參數的集合為空，接着又定義了兩個節點 pred、succ，因為是首次添加，則 index = size = 0，是以 pred 和 succ 均為為空節點，然後周遊數組 a，周遊過程中其實就是使用數組中的每個元素與前一個節點建構出來的新節點依次進行拼接。 拼接完成後，将該方法中的參數集合 c 中最後一個元素和前一個節點建構出來的新節點作為尾節點 （last = pred = newNode），最後一步，size 自增 numNew。

情景1：差別上面的首次添加一個集合，而是将一個非空集合添加到一個已有大小的集合中

直接分析方法 addAll(int index, Collection<? extends E> c)，與上面重複的步驟在這裡就不多贅述了，直接從第 2 個 if 判斷着手分析，如果不是首次添加，那麼 index 肯定是小于 size，是以就會執 行 node(index) 方法，在該方法中首先會判斷 index 與 size / 2 去比較，若 index >= size / 2，則從尾節點去開始向前去查找，反之，則從頭結點開始向後查找，最後傳回目前下标所在的節點并賦給 succ ，又把目前下标的前一個節點賦給 pred，緊接着周遊數組，将數組中的元素與 pred 建構出來的新節點依此添加在 pred 節點後面，最後一步，size 自增 numNew（傳進來集合的 size）。

情景2：使用無參構造方法建構出一個新清單，然後首次向清單裡面添加一個元素：

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
           

在 linkLast 方法裡面首先看到的是将尾節點 last 賦給節點 l，然後利用 l 節點建構出一個新節點 newNode，并且本身位于新節點 newNode 的前面，在上面假設的前提之下，此處的 last 節點應該是個空節點，是以滿足節點 l == null，可得出新節點 newNode 即就是頭結點 first，最後執行 size 的自加，添加資料成功。

總結：建構一個新節點，若首次添加，則 last = newNode = first（即頭結點 = 新節點 = 尾節點），若非首次添加，之前的尾節點 next 指向新節點 newNode

上面主要針對的是添加元素，那麼删除資料呢？删除可分為四種方式：

1. 直接删除頭結點
2. 直接删除尾結點
3. 删除指定元素
4. 删除指定下标 index 上的元素

由于第 3，4 中均是調用 unlink 方法，是以下面會合并分析

// 删除頭結點，removeFirst 中已經做了非空判斷，排除空連結清單情況
	private E unlinkFirst(Node<E> f) {
        // 取出目前被删除節點中的元素
        final E element = f.item;
        //取出下一個節點，并指派給 next
        final Node<E> next = f.next;
        // 目前要删除的元素置空，友善回收
        f.item = null;
        // 目前要删除節點的 next 指針對應的下一個節點置空，友善回收
        f.next = null; // help GC
        // 把 next 設定成頭結點
        first = next;
         // 當 next == null，表示連結清單中隻有一個節點，也就是将要被删除的節點。
         // 當 next != null，表示next 為該連結清單中頭結點，
         //	并把節點 next 中的 prev 指針指向的節點置空
        if (next == null)
            last = null;
        else
            next.prev = null;
        // 連結清單長度 -1
        size--;
        modCount++;
        // 傳回目前被删除的元素
        return element;
    }
    // 删除尾結點，removeLast 中已經做了非空判斷，排除空連結清單情況
    // 與上面分析步驟都差不多這裡就不再贅述了
     private E unlinkLast(Node<E> l) {
     
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    // 删除指定下标
     public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
     // 删除指定元素
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
     // 删除指定元素、删除指定下标均調用此方法
	 E unlink(Node<E> x) {
        // 取出目前節點 x 中的元素 element，前節點 prev 和後節點 next。
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
	   /* 
	    * 判斷 x 節點的前節點 prev 是否為空，
	    * 若為空，說明節點 x 應該是頭結點，那麼 x 節點被删除之後，
	    * x 節點之後的節點（即 next 節點）則成為頭結點。
		* 若非空，會把 x 節點中 prev 指針指向的前節點置空，友善回收，并且會把
		* prev 節點中的 next 指針指向節點 next。
		*/ 
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
	   /* 
	    * 判斷 x 節點的前節點 next 是否為空，
	    * 若為空，說明節點 x 應該是尾結點，那麼 x 節點被删除之後，
	    * x 節點之前的節點（即 prev 節點）則成為尾結點。
		* 若非空，會把 x 節點中 next 指針指向的後節點置空，友善回收，并且會把
		* next 節點中的 prev 指針指向節點 prev。
		*/ 
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
           

2.4.4 Vector

基本特點(對比 ArrayList，描述兩者的差別)，由于與 ArrayList 同實作了 List 接口，是以那些公共方法，就不再贅述了。

• Vector 與 ArrayList 相同的是底層也基于動态數組實作
• Vector 是線程安全，而 ArrayList 非線程安全，是以也就意味着在不考慮線程安全情況下，一般 ArrayList 效率高一些
• Vector 擴容大小是目前基數的 1 倍，而 ArrayList 則是 0.5 倍

Vector 與 ArrayList 的 add 、remove，基本上都如出一轍這裡就不多說了，接下來說兩個 ArrayList 裡面沒有的用法。

Enumeration

枚舉類接口，定義了兩個方法：

• boolean hasMoreElements()：
• E nextElement()：

Enumeration 出現在 Vector 類中，是用來周遊 Vector 中的元素，源碼見下方：

public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;

            public boolean hasMoreElements() {
                return count < elementCount;
            }

            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }
           

當 count 自增到與 elementCount(相當于 size) 同大小，則會傳回 false，否則傳回 true。在 nextElement 方法中以此取出 Vector 中的元素。

setSize

/**
     * Sets the size of this vector. If the new size is greater than the
     * current size, new {@code null} items are added to the end of
     * the vector. If the new size is less than the current size, all
     * components at index {@code newSize} and greater are discarded.
     *
     * @param  newSize   the new size of this vector
     * @throws ArrayIndexOutOfBoundsException if the new size is negative
     */
    public synchronized void setSize(int newSize) {
        modCount++;
        if (newSize > elementCount) {
            ensureCapacityHelper(newSize);
        } else {
            for (int i = newSize ; i < elementCount ; i++) {
                elementData[i] = null;
            }
        }
        elementCount = newSize;
    }
           

當 newSize > elementCount 時，檢查是否需要擴容，不管需不需要擴容，在舊數組 elementData 最後一個元素後面補 (newSize - elementCount) 個 null。

當 newSize < elementCount 時，從舊數組 elementData 下标為 0 處開始，取出 newSize 個元素，其餘的元素全部被回收

本篇文章主要是對實作 List 和 Set 接口的常見類的分析與整理 一方面為了鞏固 Java 基礎知識，另一方面也要學會從源碼角度去分析、處理問題，後續會持續更新關于 Set 常用子類的相關知識，文章中若有錯誤之處、或不足之處，歡迎指正，以免誤導他人???!!!