List 接口

前面我們學習了Iterator、Collection，為集合的學習打下了基礎，現在我們來學習集合的第一大體系 List。

List 是一個接口，定義了一組元素是有序的、可重復的集合。

List 繼承自 Collection，較之 Collection，List 還添加了以下操作方法

• 位置相關：List 的元素是有序的，因此有get(index)、set(index,object)、add(index,object)、remove(index) 方法。
• 搜索：indexOf()，lastIndexOf();
• 迭代：使用 Iterator 的功能板迭代器
• 范圍性操作：使用 subList 方法對 list 進行任意范圍操作。

List的抽象實現類 AbstractList

AbstractList 繼承自 AbstractCollection 類，實現了 List 接口。整個類的設計類似于AbstractCollection,實現了大多數方法，抽象了對于需要根據數據操作的方法。

List 的實現類

ArrayList

ArrayList 是我們最常用的一個類，它具有如下特點：

• 容量不固定，可以動態擴容
• 有序(基于數組的實現，當然有序~~)
• 元素可以為 null
• 效率高查找操作的時間復雜度是 O(1)增刪操作的時間復雜度是 O(n)其他操作基本也都是 O(n)
• 占用空間少，相比 LinkedList，不用占用額外空間維護表結構

從成員變量，我們可以得知

• Object[] elementData：數據結構---數組
• 兩個默認空數組，僅在構造方法中使用，不關心
• DEFAULT_CAPACITY： 數組初始容量為10
• size：當前元素個數
• MAX_ARRAY_SIZE：數組最大容量

現在我們知道了 ArrayList 其實就是基于數組的實現。因此，增刪改查操作就變得很容易理解了。

• get(index)直接獲取數組的底 index 個元素
• set(index,object)直接修改數組的第 index 個元素的引用
• add(index，object)添加一個元素到index，這里會牽涉到數組的擴容，擴容我們后面再單獨看

這里的操作很簡單，比如說含有8個元素的數組array，要在第五個位置插入一個元素x，則將第[5,8)角標的元素分別往后移動一位變成[6,9)，此時角標為5的位置空出來，使 array[5] = x 即可。

• remove(object)刪除一個元素,刪除的過程同添加元素。

現在我們來看看擴容機制,假設我們現在有一個集合 list，里面正好含有10個元素，此時，我們調用 add(object)方法添加一個元素，看看是怎樣執行擴容操作的。

public boolean add(E var1) {    //查看是數組長度是否夠    this.ensureCapacityInternal(this.size + 1);    this.elementData[this.size++] = var1;    return true;}private void ensureCapacityInternal(int var1) {    //檢查是否是默認長度為0的數組，如果是則長度設為10    if(this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        var1 = Math.max(10, var1);    }    this.ensureExplicitCapacity(var1);}private void ensureExplicitCapacity(int var1) {    ++this.modCount;    //當前需要的長度大于數組長度，執行擴容操作    if(var1 - this.elementData.length > 0) {        this.grow(var1);    }}private void grow(int var1) {    int var2 = this.elementData.length;    //var3 = var2*1.5;擴容1.5倍    int var3 = var2 + (var2 >> 1);    if(var3 - var1 < 0) {        var3 = var1;    }    //新容量超出最大值    if(var3 - 2147483639 > 0) {        var3 = hugeCapacity(var1);    }    //重新創建了一個1.5倍容量的數組賦值給elementData    this.elementData = Arrays.copyOf(this.elementData, var3);}復制代碼

從上面我們可以看到，修改某個角標的值或者查找某個角標的值時，我們可以直接調用數組的操作，效率很高。但是添加和刪除則是要操作整個數組的移動，效率稍低。

這里我們也可以看到，其實 ArrayList 就是一個針對數組操作的封裝類。

LinkedList

剛剛我們看了 ArrayList，ArrayList 的增刪操作效率相對較低。因此，Java 給我們設計了另外一種增刪效率比較高的集合 LinkedList。

LinkedList 繼承自 AbstractSequentialList。

AbstractSequentialList 又繼承自AbstractList，并且基于 iterator 實現了默認增刪改查操作。

再回過頭來看 LinkedList，LinkedList 還實現了Deque(雙向隊列)接口，雙向隊列后面我們會單獨去學習，這里不再做過多的贅述。

再來看看成員變量~~

• size 鏈表元素個數
• first 第一個元素
• last 最后一個元素

特點？和 ArrayList 的優缺點互補。

鏈表的實現，鏈表的實現很簡單，就是最基本的鏈表數據結構。理解鏈表數據結構可以跳過這里了。

我舉個例子吧，現在要讓 a、b、c、d 四個同學按順序投籃。有兩種方法，第一種是 abcd 排成一個隊伍，依次去投籃；但是體育課上讓所有的同學等著投籃很浪費時間，因此有了第二種辦法：依次告訴 a‘你投了藍之后叫 b 來投籃’，告訴 b‘你投了藍之后叫 c 來投籃’以此類推。這樣，就形成了一個簡單的單向列表，abcd 按照順序依次去投籃。此時，x 同學由于身體不舒服需要提前投籃回教室休息，則老師只需要告訴 a 同學投完籃之后不用叫 b 同學了，改叫 x 同學，x 同學投完籃之后叫 b 同學即可。不多說了，新手聽不懂，老手用不上。不懂鏈表的同學好好去學學數據結構吧。

后面的增刪改查操作就只是基礎的遍歷鏈表操作，就不去一一去讀源碼了，鏈表操作記不太清楚的同學可以去看一下 LinkedList 的源碼。

Vector

在學習了 ArrayList 之后，Vector 這個類我想用”線程安全的 ArrayList“可以一句話概括了。

Vector 和 ArrayList 一樣都繼承自 AbstractList，為什么說”Vector 是線程安全的 ArrayList“，本來還準備列個表讓大家對比一下成員變量以及主要操作方法的實現。but，除了 Vector 的方法上多了個 synchronized 外，代碼都是一樣的，比較個毛。因此，如果需要考慮線程安全，直接使用 Vector 即可，但是因為所有方法都加了synchronized ，效率相對會比較低，如果沒有線程安全的需求，那就使用 ArrayList 唄。

最后，還是說一下Vector 和 ArrayList的區別吧，反正也沒什么卵用，大家看看就好

• Vector 出生早，JDK1.0的時候出生的，ArrayList 是1.2才出生
• Vector 是線程安全的，ArrayList 不是。(這是最大的特點了)
• Vector 默認擴容2倍，ArrayList 是1.5倍。這個~~有意義嗎？
• Vector 多了一種迭代器 Enumeration。好吧，反正我沒用過。

Enumeration

為了找到 Enumeration 這種迭代器有什么特點，我去翻了一下 Vector 的代碼，找到了一個這樣的方法和這樣的接口，你們感受一下。

public Enumeration elements() {    return new Enumeration() {        int count = 0;        public boolean hasMoreElements() {            return this.count < Vector.this.elementCount;        }        public E nextElement() {            Vector var1 = Vector.this;            synchronized(Vector.this) {//區別在這里                if(this.count < Vector.this.elementCount) {                    return Vector.this.elementData(this.count++);                }            }            throw new NoSuchElementException("Vector Enumeration");        }    };}public interface Enumeration {    boolean hasMoreElements();    E nextElement();}復制代碼

mmp，這個 Enumeration 和Iterator 接口除了名字不一樣，還有什么區別？然后仔細看了一遍，在elements()方法里面的匿名內部了里面找到了nextElement()方法里面有個同步代碼塊。好吧， Enumeration 大概是線程安全的Iterator？

Stack

Stack 繼承自Vector，也是一個線程安全的集合。

Stack 也是基于數組實現的。

Stack 實現的是棧結構集合

什么是棧結構？

數據結構中，棧也是一種線性的數據結構，遵守 LIFO(后進先出)的操作順序，這里用一張很污的圖，保證你們看了之后能熟記棧結構特征。

小時候肯定都玩過羽毛球吧，羽毛球不經打，要經常換球，于是我買了一盒羽毛球，如下圖，就是一個羽毛球盒子，最先放進去的羽毛球(棧底的)，要最后才能取出來。

Stack 的 代碼實現

類結構圖如下，代碼量也不多，一共才30幾行

public class Stack extends Vector {    private static final long serialVersionUID = 1224463164541339165L;    public Stack() {    }    //入棧，添加一個元素到數組的最后一個    public E push(E var1) {        this.addElement(var1);        return var1;    }    //出棧，刪除數組最后一個元素并返回    public synchronized E pop() {        int var2 = this.size();        Object var1 = this.peek();        this.removeElementAt(var2 - 1);        return var1;    }    //獲取最后一個元素，不刪除    public synchronized E peek() {        int var1 = this.size();        if(var1 == 0) {            throw new EmptyStackException();        } else {            return this.elementAt(var1 - 1);        }    }    public boolean empty() {        return this.size() == 0;    }    獲取棧中的 位置。    public synchronized int search(Object var1) {        int var2 = this.lastIndexOf(var1);        return var2 >= 0?this.size() - var2:-1;    }}復制代碼

整個類的實現非常簡單，就是繼承 Vector，然后添加了 peek、pop、push、search 等方法，然后然添加刪除都在最末尾的元素做操作即可。

思考：怎樣用鏈表的結構快速實現 LinkedListStack？