核心概述：在之前的篇章中，我們學(xué)習(xí)了數(shù)組，因?yàn)閿?shù)組本身數(shù)據(jù)結(jié)構(gòu)的局限性馆类，對于數(shù)組內(nèi)元素除查詢操作外的其他操作（增刪改）比較低效，所以弹谁，我們又學(xué)習(xí)了集合ArrayList乾巧，初步體驗(yàn)了集合操作的便捷性。本篇我們將開始系統(tǒng)地學(xué)習(xí)Java中的集合體系预愤。

第一章：對象數(shù)組

數(shù)組是容器沟于，即可以存儲基本數(shù)據(jù)類型也可以引用數(shù)據(jù)類型，存儲了引用數(shù)據(jù)類型的數(shù)組稱為對象數(shù)組植康，例如：String[]旷太，Person[]，Student[]销睁。

public static void main(String[] args){
    //創(chuàng)建存儲Person對象的數(shù)組
    Person[] persons = {
        new Person("張三",20),
        new Person("李四",21),
        new Person("王五",22),
    };
    //遍歷數(shù)組
    for(int i = 0 ; i < persons.length; i++){
        Person person = persons[i];
        System.out.println(person.getName()+"::"+person.getAge());
    }
}

數(shù)組的弊端：

• 數(shù)組長度是固定的供璧，一旦創(chuàng)建不可修改。
• 需要添加元素冻记，只能創(chuàng)建新的數(shù)組睡毒，將原數(shù)組中的元素進(jìn)行復(fù)制。

為了解決數(shù)組的定長問題冗栗，Java語言從JDK1.2開始出現(xiàn)集合框架演顾。

第二章：認(rèn)識集合

1.1-集合概述（了解）

在之前的篇章中我們已經(jīng)學(xué)習(xí)過并使用過集合ArrayList<E> 供搀，那么集合到底是什么呢？

簡而言之偶房，集合就是是java中提供的一種容器趁曼，可以用來存儲多個數(shù)據(jù)军浆。

這么說棕洋，集合和數(shù)組非常相似，就是存儲多個數(shù)據(jù)的容器乒融。那么掰盘，集合和數(shù)組有什么區(qū)別呢？

• 數(shù)組的長度是固定的赞季。集合的長度是可變的愧捕。
• 數(shù)組中存儲的是同一類型的元素，可以存儲任意類型數(shù)據(jù)申钩。集合存儲的都是引用數(shù)據(jù)類型次绘。如果想存儲基本類型數(shù)據(jù)需要存儲對應(yīng)的包裝類型。

1.2-Java中的集合框架（了解）

以下的集合體系描述撒遣，不是所有的集合邮偎，而是常用的集合。

單列集合體系

image

雙列集合體系

image

由于集合體系豐富义黎，我們將會分多個篇幅學(xué)習(xí)禾进，本篇我們將學(xué)習(xí)單列集合體系Collection中的List系列集合。

1.3-Collection集合通用方法（記憶）

Collection是所有單列集合的父接口廉涕，因此在Collection中定義了單列集合(List和Set)通用的一些方法泻云，這些方法可用于操作所有的單列集合。方法如下：

• public boolean add(E e)： 把給定的對象添加到當(dāng)前集合中 狐蜕。
• public boolean addAll(Collection<? extends E>)將另一個集合元素添加到當(dāng)前集合中宠纯。
• public void clear() :清空集合中所有的元素。
• public boolean remove(E e): 把給定的對象在當(dāng)前集合中刪除层释。
• public boolean contains(Object obj): 判斷當(dāng)前集合中是否包含給定的對象婆瓜。
• public boolean isEmpty(): 判斷當(dāng)前集合是否為空。
• public int size(): 返回集合中元素的個數(shù)湃累。
• public Object[] toArray(): 把集合中的元素勃救，存儲到數(shù)組中。

代碼示例

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        // 添加元素
        list.add("張三");
        list.add("李四");
        Collection<String> list2 = new ArrayList<>();
        list2.add("王五");
        list2.add("趙六");
        // 將list2集合元素添加到list集合中
        list.addAll(list2);
        System.out.println(list);

        // 移除元素
        list.remove("張三");
        System.out.println(list);
        // 判斷集合中是否包含某個元素
        boolean isHas = list.contains("張三");
        System.out.println(isHas); // false
        // 判斷當(dāng)前集合是否為空
        boolean isEmpty = list.isEmpty();
        System.out.println(isEmpty);
        // 清空元素
        list.clear();
        System.out.println(list);
        // 集合的長度
        System.out.println(list.size());
        // 集合中的元素存儲到一個數(shù)組中
        Object[]s =  list.toArray();
    }
}

第三章：遍歷集合

3.1-Iterator方式遍歷（記憶）

介紹

Iterator治力，是一個迭代器接口蒙秒。Collection中的成員方法iterator()被調(diào)用后，會返回一個Iterator對象宵统。利用這個對象可以實(shí)現(xiàn)遍歷集合晕讲。如何遍歷呢覆获？在取元素之前先要判斷集合中有沒有元素，如果有瓢省，就把這個元素取出來弄息，繼續(xù)在判斷，如果還有就再取出出來勤婚。一直把集合中的所有元素全部取出摹量。這種取出方式專業(yè)術(shù)語稱為迭代。

Iterator對象的成員方法：

• hasNext(); 檢測集合中是否存在下一個元素
• next(); 找到并獲取下一個元素

示例代碼：

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        list.add("張三");
        list.add("李四");
        list.add("王五");
        // 得到一個迭代器對象
        Iterator<String> it = list.iterator();
        // 判斷集合中是否還有元素
        while (it.hasNext()) {
            // 取出元素
            String str = it.next();
            System.out.println(str);
        }
    }
}

迭代器執(zhí)行過程

在調(diào)用Iterator的next方法之前馒胆，迭代器的索引位于第一個元素之前缨称，不指向任何元素，當(dāng)?shù)谝淮握{(diào)用迭代器的next方法后祝迂，迭代器的索引會向后移動一位睦尽，指向第一個元素并將該元素返回，當(dāng)再次調(diào)用next方法時型雳，迭代器的索引會指向第二個元素并將該元素返回当凡，依此類推，直到hasNext方法返回false纠俭，表示到達(dá)了集合的末尾沿量，終止對元素的遍歷。

image

迭代器源碼分析

迭代器是遍歷Collection集合的通用方式柑晒，任意Collection集合都可以使用迭代器進(jìn)行遍歷欧瘪，那么每一種集合的自身特性是不同的，也就是存儲元素的方式不同匙赞，那么是如何做到遍歷方式的統(tǒng)一呢佛掖，接下來我們分析一下迭代器的源代碼。

每個Collection集合都會實(shí)現(xiàn)涌庭，方法 Iterator iterator()芥被，返回Iterator接口實(shí)現(xiàn)類，以ArrayList集合為例

java.util.Iterator接口：

public interface Iterator<E> {
    boolean hasNext();
    E next();
}

java.util.ArrayList類：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
   /*
    *  ArrayList實(shí)現(xiàn)接口Collection
    *  重寫方法iterator()
    *  返回Iterator接口實(shí)現(xiàn)類 Itr類的對象
    */
    public Iterator<E> iterator() {
        return new Itr();
    }
    
   /*
    * ArrayList中定義內(nèi)部類Itr,實(shí)現(xiàn)接口Iterator
    * 重寫hasNext(),next()方法
    */
    private class Itr implements Iterator<E> {
        public boolean hasNext() { 
            // ...
       }
       public E next() { 
            // ...
       }
    }

所以結(jié)論是：

• 所有集合的迭代器坐榆，全由內(nèi)部類實(shí)現(xiàn)拴魄。
• 集合中定義內(nèi)部類，實(shí)現(xiàn)迭代器接口席镀，可以使所有集合的遍歷方式統(tǒng)一匹中。
• 調(diào)用迭代器的方法hasNext()，next()均執(zhí)行集合中內(nèi)部類的重寫方法豪诲。

并發(fā)修改異常

在使用迭代器遍歷集合中顶捷，不能使用集合本身的方法改變集合的長度，一旦被改變將會拋出ConcurrentModificationException并發(fā)修改異常屎篱。

public static void main(String[] args){
    Collection<String> coll = new ArrayList<String>();
    coll.add("hello1");
    coll.add("hello2");
    coll.add("hello3");
    coll.add("hello4");
    Iterator<String> it = coll.iterator();
    while (it.hasNext()){
      String str = it.next();
      if("hello2".equals(str)){
         coll.add("hello5");
    }
}

以上程序服赎，在迭代器遍歷過程中葵蒂，使用了集合add方法修改集合的長度，這個操作是不允許的重虑，被禁止的践付，程序中會拋出并發(fā)修改異常。

3.2-增強(qiáng)for方式遍歷（記憶）

概述

增強(qiáng)for循環(huán)(也稱for each循環(huán))是JDK1.5以后出來的一個高級for循環(huán)缺厉，專門用來遍歷數(shù)組和集合的永高。它的內(nèi)部原理其實(shí)是個Iterator迭代器，所以在遍歷的過程中芽死，不能對集合中的元素進(jìn)行增刪操作乏梁。

語法格式

for(元素的數(shù)據(jù)類型  變量 : Collection集合or數(shù)組){ 
    //寫操作代碼
}

變量，表示取出的某一個元素

代碼示例：

import java.util.ArrayList;
import java.util.Collection;

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        list.add("張三");
        list.add("李四");
        list.add("王五");
        for (String s : list) {
            System.out.println(s);
        }
    }
}
/*
    輸出結(jié)果：
        張三
        李四
        王五
*/

第四章：數(shù)據(jù)結(jié)構(gòu)

4.1-概述（了解）

數(shù)據(jù)結(jié)構(gòu)就是計算機(jī)存儲关贵、組織數(shù)據(jù)的方式 。

指的是相互之間存在著特定關(guān)系的一種或多種的數(shù)據(jù)元素集合卖毁。

為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)呢揖曾？

通常情況下，精心選擇合適的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或存儲的效率亥啦。

比如：為什么數(shù)組查詢速度快炭剪，增刪改效率較低？為什么有的集合更適合用于查詢翔脱，有的更適合用于增刪改奴拦？

4.2-數(shù)據(jù)結(jié)構(gòu)-棧（了解）

介紹

棧：棧（stack）又名堆棧，是一種運(yùn)算受限的線性表届吁。

受限：限定僅在表尾進(jìn)行插入和刪除操作的線性表（這一端被稱為棧頂错妖，另一端稱為棧底）

image

這里兩個名詞需要注意：

• 壓棧（入棧）：就是存元素。即疚沐，把元素存儲到棧的頂端位置暂氯，棧中已有元素依次向棧底方向移動一個位置。
• 彈棧（出棧）：就是取元素亮蛔。即痴施，把棧的頂端位置元素取出，棧中已有元素依次向棧頂方向移動一個位置究流。

特性

先進(jìn)后出辣吃，是棧結(jié)構(gòu)的特點(diǎn)。

image

4.3-數(shù)據(jù)結(jié)構(gòu)-隊列（了解）

介紹

隊列：是一種受限的特殊線性表芬探。

受限：只允許在表的前端（隊頭）進(jìn)行刪除操作神得，后端（隊尾）進(jìn)行插入操作。

特性

先進(jìn)先出灯节，是隊列數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)循头。

image

4.4-數(shù)據(jù)結(jié)構(gòu)-數(shù)組（了解）

介紹

數(shù)組：一組有序的（索引有序并且從0開始）類型相同的長度固定的元素集合绵估。

特性

• 元素有序
• 元素同類型
• 長度固定

應(yīng)用效果

查詢快，從數(shù)組索引0開始查找卡骂，根據(jù)指定位置的偏移量可快速獲取數(shù)據(jù)国裳。

增刪慢，數(shù)組的長度是固定的全跨，若刪除或增加一格元素缝左，則會先創(chuàng)建一個新的數(shù)組褒链，再把原數(shù)組的數(shù)據(jù)根據(jù)操作復(fù)制到新數(shù)組中淆攻。

4.5-數(shù)據(jù)結(jié)構(gòu)-鏈表（了解）

鏈表

鏈表:linked list,由一系列結(jié)點(diǎn)node（鏈表中每一個元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成砚偶。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域挪钓，另一個是存儲下一個結(jié)點(diǎn)地址的指針域是越。我們常說的鏈表結(jié)構(gòu)有單向鏈表與雙向鏈表，那么這里給大家介紹的是單向鏈表碌上。

image

特性

• 多個結(jié)點(diǎn)之間倚评，通過地址進(jìn)行連接。例如馏予，多個人手拉手天梧，每個人使用自己的右手拉住下個人的左手，依次類推霞丧，這樣多個人就連在一起了呢岗。
• 結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。
• 每個結(jié)點(diǎn)包括兩個部分（單鏈表）
  • 一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域
  • 另一個是存儲下一個結(jié)點(diǎn)地址的指針域蛹尝。

應(yīng)用效果

• 查詢慢：鏈表的地址不是連續(xù)的后豫，每次查找都得從頭開始查找。
• 增刪快：增刪操作不會影響鏈表的整體結(jié)構(gòu)箩言。

image

第五章：List集合

5.1-概述（了解）

概述

java.util.List接口硬贯，繼承Collection接口，有序的 collection（也稱為序列）陨收。此接口的用戶可以對列表中每個元素的插入位置進(jìn)行精確地控制饭豹。用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素务漩。與Set接口不同拄衰，List接口通常允許重復(fù)元素。

特點(diǎn)

• List集合是有序的集合饵骨，存儲和取出的順序一致翘悉。
• List集合允許存儲重復(fù)的元素。
• List集合中的每個元素具有索引居触。

集合類名后綴是List妖混，例如ArrayList老赤，LinkedList等，都是List接口實(shí)現(xiàn)類制市，都具有List接口的特點(diǎn)抬旺。

5.2-List集合常用方法（記憶）

List作為Collection集合的子接口，不但繼承了Collection接口中的全部方法祥楣，而且還增加了一些根據(jù)元素索引來操 作集合的特有方法开财，如下：

方法：

1. public void add(int index, E element) : 將指定的元素，添加到該集合中的指定位置上误褪。
2. public E get(int index) :返回集合中指定位置的元素责鳍。
3. public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
4. public E set(int index, E element) :用指定元素替換集合中指定位置的元素,返回值的更新前的元素

代碼：

   List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    // public void add(int index, E element) : 將指定的元素兽间，添加到該集合中的指定位置上历葛。
    list.add(1,"d");
    System.out.println(list); // [a, d, b, c]
    // public E get(int index) :返回集合中指定位置的元素。
    System.out.println(list.get(2)); // b
    // public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素渡八。
    list.remove(1);
    System.out.println(list); // [a, b, c]
    // public E set(int index, E element) :用指定元素替換集合中指定位置的元素,返回值的更新前的元素
    list.set(1,"B");
    System.out.println(list); // [a, B, c]

第六章：ArrayList集合

6.1-概述（了解）

java.util.ArrayList集合數(shù)據(jù)存儲的結(jié)構(gòu)是數(shù)組結(jié)構(gòu)啃洋。元素增刪慢，查找快屎鳍，線程不安全，運(yùn)行速度快问裕。由于日常開發(fā)中使用最多的功能為查詢數(shù)據(jù)逮壁、遍歷數(shù)據(jù)，所以ArrayList是最常用的集合粮宛。

許多程序員開發(fā)時非常隨意地使用ArrayList完成任何需求窥淆，并不嚴(yán)謹(jǐn)，這種用法是不提倡的巍杈。

6.2-ArrayList源代碼分析（了解）

底層就是數(shù)組

底層是Object對象數(shù)組忧饭，數(shù)組存儲的數(shù)據(jù)類型是Object，數(shù)組名字為elementData筷畦。

ArrayList類中部分源碼

transient Object[] elementData;

創(chuàng)建ArrayList對象分析：無參數(shù)

初始化ArrayList對象词裤，創(chuàng)建一個為10的空列表。也可以指定列表長度鳖宾，構(gòu)造方法傳遞長度即可吼砂。

new ArrayList(); //默認(rèn)長度為10
new ArrayList(int initialCapacity); //指定長度

ArrayList無參數(shù)構(gòu)造方法分析：

// 定義Object對象類型的空數(shù)組，數(shù)組在內(nèi)存中存在鼎文，但長度為0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

解析：這里可以看出渔肩，當(dāng)我們new ArrayList()的時候，并沒有創(chuàng)建長度為10的數(shù)組拇惋，而是創(chuàng)建了一個長度為0的數(shù)組周偎，當(dāng)我們使用add()方法添加元素的時候抹剩，就會將數(shù)組由0長度，擴(kuò)容為10長度蓉坎。

ArrayList添加元素add方法分析：

//ArrayList的成員變量size澳眷，默認(rèn)為0，統(tǒng)計集合中元素的個數(shù)
private int size;
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

解析：集合添加元素之前袍嬉，先調(diào)用方法ensureCapacityInternal()增加容量境蔼，傳遞size+1，size默認(rèn)為0伺通。傳遞參數(shù)0+1的結(jié)果箍土。

ensureCapacityInternal()增加容量方法分析：

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

解析：方法ensureCapacityInternal()接收到參數(shù)1，繼續(xù)調(diào)用方法calculateCapacity()計算容量罐监，傳遞數(shù)組和1吴藻。

calculateCapacity()計算容量方法分析：

private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

解析：方法中判斷elementData是否和DEFAULTCAPACITY_EMPTY_ELEMENTDATA數(shù)組相等，在構(gòu)造方法中：this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;因此結(jié)果為true弓柱，方法將會返回參數(shù)DEFAULT_CAPACITY（=10）和 minCapacity（=1）中最大的值沟堡，return 10;此時方法calculateCapacity()結(jié)束，繼續(xù)執(zhí)行() ensureExplicitCapacity()矢空，傳遞參數(shù)10

ensureExplicitCapacity()保證明確容量方法分析:

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

解析：方法中進(jìn)行判斷（10-elemetData.length>0）結(jié)果為true航罗，10-0>0。調(diào)用方法grow()傳遞10屁药。

grow()增加容量方法分析：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        //**將10賦值給變量newCapacity
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //**數(shù)組復(fù)制粥血， Arrays.copyOf底層實(shí)現(xiàn)是System.arrayCopy()
    elementData = Arrays.copyOf(elementData, newCapacity);
}

解析：方法grow()接收到參數(shù)10，進(jìn)過計算酿箭，執(zhí)行newCapacity = minCapacity;這行程序复亏，此時變量newCapacity的值為10，然后進(jìn)行數(shù)組復(fù)制操作缭嫡，復(fù)制新數(shù)組的長度為10缔御，為此ArrayList集合初始化創(chuàng)建過程完畢。

創(chuàng)建ArrayList對象分析：帶有初始化容量構(gòu)造方法

ArrayList有參數(shù)構(gòu)造方法分析：new ArrayList(10)

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);
    }
}

解析：創(chuàng)建ArrayList集合妇蛀，傳遞參數(shù)10耕突，變量initialCapacity接收到10，直接進(jìn)行數(shù)組的創(chuàng)建：this.elementData = new Object[initialCapacity]讥耗。如果傳遞的參數(shù)為0有勾，那么結(jié)果就和使用無參數(shù)構(gòu)造方法相同，如果傳遞的參數(shù)小于0古程，拋出IllegalArgumentException無效參數(shù)異常蔼卡。

add添加元素方法分析:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

解析：集合添加元素，調(diào)用方法add并傳遞被添加的元素，首先調(diào)用方法ensureCapacityInternal()進(jìn)行容量的檢查雇逞，然后將元素添加到elemenetData數(shù)組中荤懂，size變量是記錄存儲多少個元素的，默認(rèn)值為0塘砸，添加第一個元素的時候节仿，size為0，添加第一個元素掉蔬，再++廊宪。返回true，List集合允許重復(fù)元素女轿。

ensureCapacityInternal()方法最終會執(zhí)行到grow方法箭启。

private void grow(int minCapacity) {
    //定義變量（老容量），保存數(shù)組的長度 = 10
    int oldCapacity = elementData.length;
    //定義變量（新容量） = 老容量+老容量右移1位
    //右移是二進(jìn)制位計算蛉迹，相等于除以2,得出新容量=老容量+老容量/2
    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);
}

解析：例如當(dāng)前的集合中的數(shù)組長度為10傅寡，進(jìn)行擴(kuò)容。得出新容量+老容量=老容量/2

第七章：LinkedList集合

7.1-概述（了解）

java.util.LinkedList集合數(shù)據(jù)存儲的結(jié)構(gòu)是鏈表結(jié)構(gòu)北救。方便元素添加荐操、刪除的集合。

集合特點(diǎn)：元素增刪快珍策，查找慢托启，線程不安全，運(yùn)行速度快攘宙。

LinkedList是一個雙向鏈表驾中，那么雙向鏈表是什么樣子的呢，我們用個圖了解下：

image

7.2-特有方法（了解）

實(shí)際開發(fā)中對一個集合元素的添加與刪除經(jīng)常涉及到首尾操作模聋，而LinkedList提供了大量首尾操作的方法。這些方法我們作為了解即可：

• public void addFirst(E e):將指定元素插入此列表的開頭唠亚。
• public void addLast(E e):將指定元素添加到此列表的結(jié)尾链方。
• public E getFirst():返回此列表的第一個元素。
• public E getLast():返回此列表的最后一個元素灶搜。
• public E removeFirst():移除并返回此列表的第一個元素祟蚀。
• public E removeLast():移除并返回此列表的最后一個元素。
• public E pop():從此列表所表示的堆棧處彈出一個元素割卖。
• public void push(E e):將元素推入此列表所表示的堆棧前酿。
• public boolean isEmpty()：如果列表不包含元素，則返回true鹏溯。

LinkedList是List的子類罢维，List中的方法LinkedList都是可以使用，這里就不做詳細(xì)介紹丙挽，我們只需要了解LinkedList的特有方法即可肺孵。在開發(fā)時匀借，LinkedList集合也可以作為堆棧，隊列的結(jié)構(gòu)使用平窘。

     LinkedList list = new LinkedList();
    list.add("a");
    list.add("b");
    // public void addFirst(E e) :將指定元素插入此列表的開頭吓肋。
    list.addFirst("A");
    // public void addLast(E e) :將指定元素添加到此列表的結(jié)尾。
    list.addLast("B");
    System.out.println(list); // [A, a, b, B]
    // public E getFirst() :返回此列表的第一個元素瑰艘。
    System.out.println(list.getFirst()); // A
    // public E getLast() :返回此列表的最后一個元素是鬼。
    System.out.println(list.getLast()); // B
    // public E removeFirst() :移除并返回此列表的第一個元素。
    list.removeFirst();
    // public E removeLast() :移除并返回此列表的最后一個元素紫新。
    list.removeLast();
    System.out.println(list); //[a, b]
    // public E pop() :從此列表所表示的堆棧處彈出一個元素均蜜。
    list.pop();
    System.out.println(list); // [b]
    // public void push(E e) :將元素推入此列表所表示的堆棧。
    list.push("a");
    System.out.println(list); // [a, b]
    // public boolean isEmpty() ：如果列表不包含元素弊琴，則返回true兆龙。
    System.out.println(list.isEmpty()); // false

7.3-源碼分析（了解）

LinkedList成員變量分析：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
}

解析：成員變量size是長度，記錄了集合中存儲元素的個數(shù)敲董。first和last分別表示鏈表開頭和結(jié)尾的元素紫皇，因此鏈表可以方便的操作開頭元素和結(jié)尾元素。

LinkedList內(nèi)部類Node類分析：

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集合中的內(nèi)部類Node腋寨，表示鏈表中的節(jié)點(diǎn)對象聪铺，Node類具有3個成員變量:

• item：存儲的對象。
• next：下一個節(jié)點(diǎn)萄窜。
• prev：上一個節(jié)點(diǎn)铃剔。

從Node類的源代碼中可以分析出，LinkedList是雙向鏈表查刻，一個對象键兜，他記錄了上一個節(jié)點(diǎn)，也記錄了下一個節(jié)點(diǎn)穗泵。

LinkedList添加元素方法add()分析：

public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast方法

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++;
}

解析：調(diào)用集合方法add()添加元素普气，本質(zhì)上調(diào)用的是linkLast()方法進(jìn)行添加。

• final Node<E> l = last：當(dāng)集合中添加第一個元素時last=null佃延。
• final Node<E> newNode = new Node<>(l, e, null)：創(chuàng)建Node類內(nèi)部類對象现诀，傳遞null（上一個節(jié)點(diǎn)），被添加的元素和null（下一個節(jié)點(diǎn)）履肃。
• last = newNode：將新增的節(jié)點(diǎn)newNode,復(fù)制給鏈表中的最后一個節(jié)點(diǎn)last仔沿。
• if(l == null)：第一次添加元素時，結(jié)果為true尺棋，first=newNode封锉，鏈表中的第一個節(jié)點(diǎn)=新添加的節(jié)點(diǎn)。
• size++ ：記錄了集合中元素的個數(shù)。
• modCount++：記錄了集合被操作的次數(shù)烘浦。

LinkedList獲取元素方法get()分析

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

node方法

Node<E> node(int 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;
    }
}

解析：index < (size >> 1)采用二分法抖坪，如果要獲取元素的索引小于長度的一半，那么就從0開始闷叉，找到集合長度的一半擦俐，如果要獲取的元素的長度大于集合的一半，那么就從最大索引開始握侧，找到集合長度的一半蚯瞧。

結(jié)論：鏈表本身并沒有索引，當(dāng)我們通過索引獲取的時候品擎，內(nèi)部采用了循環(huán)到集合長度的方式依次查找的埋合。

第八章：綜合案例

8.1-需求

按照斗地主的規(guī)則，完成洗牌發(fā)牌的動作萄传。
具體規(guī)則：

• 使用54張牌打亂順序,
• 三個玩家參與游戲甚颂，
• 三人交替摸牌，每人17張牌秀菱，
• 最后三張留作底牌振诬。

8.2-分析

牌可以設(shè)計為一個ArrayList<String>,每個字符串為一張牌。
每張牌由花色數(shù)字兩部分組成衍菱，我們可以使用花色集合與數(shù)字集合嵌套迭代完成每張牌的組裝赶么。
牌由Collections類的shuffle方法進(jìn)行隨機(jī)排序。

8.3-代碼

package www.penglei666.com;

import java.util.ArrayList;
import java.util.Collections;

public class Poker {
    public static void main(String[] args) {
        /*
         * 1: 準(zhǔn)備牌操作
         */
        //1.1 創(chuàng)建牌盒 將來存儲牌面的
        ArrayList<String> pokerBox = new ArrayList<String>();
        //1.2 創(chuàng)建花色集合
        ArrayList<String> colors = new ArrayList<String>();

        //1.3 創(chuàng)建數(shù)字集合
        ArrayList<String> numbers = new ArrayList<String>();

        //1.4 分別給花色 以及 數(shù)字集合添加元素
        colors.add("?");
        colors.add("?");
        colors.add("?");
        colors.add("?");

        for(int i = 2;i<=10;i++){
            numbers.add(i+"");
        }
        numbers.add("J");
        numbers.add("Q");
        numbers.add("K");
        numbers.add("A");
        //1.5 創(chuàng)造牌  拼接牌操作
        // 拿出每一個花色  然后跟每一個數(shù)字 進(jìn)行結(jié)合  存儲到牌盒中
        for (int i =0 ; i<colors.size() ;i++) {
            //color每一個花色 guilian
            //遍歷數(shù)字集合
            for(int j = 0; j <numbers.size() ; j++){
                //結(jié)合
                String card = colors.get(i)+numbers.get(j);
                //存儲到牌盒中
                pokerBox.add(card);
            }
        }
        //1.6大王小王
        pokerBox.add("小?");
        pokerBox.add("大?");
        // System.out.println(pokerBox);
        //洗牌 是不是就是將  牌盒中 牌的索引打亂
        // Collections類  工具類  都是 靜態(tài)方法
        // shuffer方法
        /*
         * static void shuffle(List<?> list)
         *     使用默認(rèn)隨機(jī)源對指定列表進(jìn)行置換脊串。
         */
        //2:洗牌
        Collections.shuffle(pokerBox);
        //3 發(fā)牌
        //3.1 創(chuàng)建 三個 玩家集合  創(chuàng)建一個底牌集合
        ArrayList<String> player1 = new ArrayList<String>();
        ArrayList<String> player2 = new ArrayList<String>();
        ArrayList<String> player3 = new ArrayList<String>();
        ArrayList<String> dipai = new ArrayList<String>();

        //遍歷 牌盒  必須知道索引
        for(int i = 0;i<pokerBox.size();i++){
            //獲取 牌面
            String card = pokerBox.get(i);
            //留出三張底牌 存到 底牌集合中
            if(i>=51){//存到底牌集合中
                dipai.add(card);
            } else {
                //玩家1   %3  ==0
                if(i%3==0){
                    player1.add(card);
                }else if(i%3==1){//玩家2
                    player2.add(card);
                }else{//玩家3
                    player3.add(card);
                }
            }
        }
        //看看
        System.out.println("東方月初："+player1);
        System.out.println("涂山紅紅："+player2);
        System.out.println("王權(quán)富貴："+player3);
        System.out.println("底牌："+dipai);
        
    }
}

image