核心概述：在之前的篇章中，我們學(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ù)組是容器，即可以存儲(chǔ)基本數(shù)據(jù)類型也可以引用數(shù)據(jù)類型，存儲(chǔ)了引用數(shù)據(jù)類型的數(shù)組稱為對象數(shù)組，例如：String[]，Person[]，Student[]。

public static void main(String[] args){
    //創(chuàng)建存儲(chǔ)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中提供的一種容器，可以用來存儲(chǔ)多個(gè)數(shù)據(jù)。

這么說，集合和數(shù)組非常相似，就是存儲(chǔ)多個(gè)數(shù)據(jù)的容器。那么，集合和數(shù)組有什么區(qū)別呢？

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

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

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

單列集合體系

image

雙列集合體系

image

由于集合體系豐富，我們將會(huì)分多個(gè)篇幅學(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>)將另一個(gè)集合元素添加到當(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(): 返回集合中元素的個(gè)數(shù)。
• public Object[] toArray(): 把集合中的元素，存儲(chǔ)到數(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);
        // 判斷集合中是否包含某個(gè)元素
        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());
        // 集合中的元素存儲(chǔ)到一個(gè)數(shù)組中
        Object[]s =  list.toArray();
    }
}

第三章：遍歷集合

3.1-Iterator方式遍歷（記憶）

介紹

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

Iterator對象的成員方法：

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

示例代碼：

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("王五");
        // 得到一個(gè)迭代器對象
        Iterator<String> it = list.iterator();
        // 判斷集合中是否還有元素
        while (it.hasNext()) {
            // 取出元素
            String str = it.next();
            System.out.println(str);
        }
    }
}

迭代器執(zhí)行過程

在調(diào)用Iterator的next方法之前，迭代器的索引位于第一個(gè)元素之前，不指向任何元素，當(dāng)?shù)谝淮握{(diào)用迭代器的next方法后，迭代器的索引會(huì)向后移動(dòng)一位，指向第一個(gè)元素并將該元素返回，當(dāng)再次調(diào)用next方法時(shí)，迭代器的索引會(huì)指向第二個(gè)元素并將該元素返回，依此類推，直到hasNext方法返回false，表示到達(dá)了集合的末尾，終止對元素的遍歷。

image

迭代器源碼分析

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

每個(gè)Collection集合都會(huì)實(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ā)修改異常

在使用迭代器遍歷集合中，不能使用集合本身的方法改變集合的長度，一旦被改變將會(huì)拋出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方法修改集合的長度，這個(gè)操作是不允許的，被禁止的，程序中會(huì)拋出并發(fā)修改異常。

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

概述

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

語法格式

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

變量，表示取出的某一個(gè)元素

代碼示例：

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ì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式 。

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

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

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

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

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

介紹

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

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

image

這里兩個(gè)名詞需要注意：

• 壓棧（入棧）：就是存元素。即，把元素存儲(chǔ)到棧的頂端位置，棧中已有元素依次向棧底方向移動(dòng)一個(gè)位置。
• 彈棧（出棧）：就是取元素。即，把棧的頂端位置元素取出，棧中已有元素依次向棧頂方向移動(dòng)一個(gè)位置。

特性

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

image

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

介紹

隊(duì)列：是一種受限的特殊線性表。

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

特性

先進(jìn)先出，是隊(duì)列數(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ù)組的長度是固定的，若刪除或增加一格元素，則會(huì)先創(chuàng)建一個(gè)新的數(shù)組，再把原數(shù)組的數(shù)據(jù)根據(jù)操作復(fù)制到新數(shù)組中。

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

鏈表

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

image

特性

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

應(yīng)用效果

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

image

第五章：List集合

5.1-概述（了解）

概述

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

特點(diǎn)

• List集合是有序的集合，存儲(chǔ)和取出的順序一致。
• List集合允許存儲(chǔ)重復(fù)的元素。
• List集合中的每個(gè)元素具有索引。

集合類名后綴是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ù)存儲(chǔ)的結(jié)構(gòu)是數(shù)組結(jié)構(gòu)。元素增刪慢，查找快，線程不安全，運(yùn)行速度快。由于日常開發(fā)中使用最多的功能為查詢數(shù)據(jù)、遍歷數(shù)據(jù)，所以ArrayList是最常用的集合。

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

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

底層就是數(shù)組

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

ArrayList類中部分源碼

transient Object[] elementData;

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

初始化ArrayList對象，創(chuàng)建一個(gè)為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()的時(shí)候，并沒有創(chuàng)建長度為10的數(shù)組，而是創(chuàng)建了一個(gè)長度為0的數(shù)組，當(dāng)我們使用add()方法添加元素的時(shí)候，就會(huì)將數(shù)組由0長度，擴(kuò)容為10長度。

ArrayList添加元素add方法分析：

//ArrayList的成員變量size，默認(rèn)為0，統(tǒng)計(jì)集合中元素的個(gè)數(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()計(jì)算容量，傳遞數(shù)組和1。

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

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，方法將會(huì)返回參數(shù)DEFAULT_CAPACITY（=10）和 minCapacity（=1）中最大的值，return 10;此時(shí)方法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)過計(jì)算，執(zhí)行newCapacity = minCapacity;這行程序，此時(shí)變量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變量是記錄存儲(chǔ)多少個(gè)元素的，默認(rèn)值為0，添加第一個(gè)元素的時(shí)候，size為0，添加第一個(gè)元素，再++。返回true，List集合允許重復(fù)元素。

ensureCapacityInternal()方法最終會(huì)執(zhí)行到grow方法。

private void grow(int minCapacity) {
    //定義變量（老容量），保存數(shù)組的長度 = 10
    int oldCapacity = elementData.length;
    //定義變量（新容量） = 老容量+老容量右移1位
    //右移是二進(jìn)制位計(jì)算，相等于除以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ù)存儲(chǔ)的結(jié)構(gòu)是鏈表結(jié)構(gòu)。方便元素添加、刪除的集合。

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

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

image

7.2-特有方法（了解）

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

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

LinkedList是List的子類，List中的方法LinkedList都是可以使用，這里就不做詳細(xì)介紹，我們只需要了解LinkedList的特有方法即可。在開發(fā)時(shí)，LinkedList集合也可以作為堆棧，隊(duì)列的結(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() :返回此列表的第一個(gè)元素。
    System.out.println(list.getFirst()); // A
    // public E getLast() :返回此列表的最后一個(gè)元素。
    System.out.println(list.getLast()); // B
    // public E removeFirst() :移除并返回此列表的第一個(gè)元素。
    list.removeFirst();
    // public E removeLast() :移除并返回此列表的最后一個(gè)元素。
    list.removeLast();
    System.out.println(list); //[a, b]
    // public E pop() :從此列表所表示的堆棧處彈出一個(gè)元素。
    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是長度，記錄了集合中存儲(chǔ)元素的個(gè)數(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個(gè)成員變量:

• item：存儲(chǔ)的對象。
• next：下一個(gè)節(jié)點(diǎn)。
• prev：上一個(gè)節(jié)點(diǎn)。

從Node類的源代碼中可以分析出，LinkedList是雙向鏈表，一個(gè)對象，他記錄了上一個(gè)節(jié)點(diǎn)，也記錄了下一個(gè)節(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)集合中添加第一個(gè)元素時(shí)last=null。
• final Node<E> newNode = new Node<>(l, e, null)：創(chuàng)建Node類內(nèi)部類對象，傳遞null（上一個(gè)節(jié)點(diǎn)），被添加的元素和null（下一個(gè)節(jié)點(diǎn)）。
• last = newNode：將新增的節(jié)點(diǎn)newNode,復(fù)制給鏈表中的最后一個(gè)節(jié)點(diǎn)last。
• if(l == null)：第一次添加元素時(shí)，結(jié)果為true，first=newNode，鏈表中的第一個(gè)節(jié)點(diǎn)=新添加的節(jié)點(diǎn)。
• size++ ：記錄了集合中元素的個(gè)數(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)我們通過索引獲取的時(shí)候，內(nèi)部采用了循環(huán)到集合長度的方式依次查找的。

第八章：綜合案例

8.1-需求

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

• 使用54張牌打亂順序,
• 三個(gè)玩家參與游戲，
• 三人交替摸牌，每人17張牌，
• 最后三張留作底牌。

8.2-分析

牌可以設(shè)計(jì)為一個(gè)ArrayList<String>,每個(gè)字符串為一張牌。
每張牌由花色數(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)建牌盒 將來存儲(chǔ)牌面的
        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)造牌  拼接牌操作
        // 拿出每一個(gè)花色  然后跟每一個(gè)數(shù)字 進(jìn)行結(jié)合  存儲(chǔ)到牌盒中
        for (int i =0 ; i<colors.size() ;i++) {
            //color每一個(gè)花色 guilian
            //遍歷數(shù)字集合
            for(int j = 0; j <numbers.size() ; j++){
                //結(jié)合
                String card = colors.get(i)+numbers.get(j);
                //存儲(chǔ)到牌盒中
                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)建 三個(gè) 玩家集合  創(chuàng)建一個(gè)底牌集合
        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