Java集合

作為一個(gè)Developer肴楷，Java集合類是我們?cè)诠ぷ髦羞\(yùn)用最多的水由、最頻繁的類。相比于數(shù)組(Array)來說赛蔫，集合類的長(zhǎng)度可變砂客，更加適合于現(xiàn)代開發(fā)需求；

Java集合就像一個(gè)容器呵恢，可以存儲(chǔ)任何類型的數(shù)據(jù)鞠值，也可以結(jié)合泛型來存儲(chǔ)具體的類型對(duì)象。在程序運(yùn)行時(shí)渗钉，Java集合可以動(dòng)態(tài)的進(jìn)行擴(kuò)展彤恶，隨著元素的增加而擴(kuò)大。在Java中鳄橘，集合類通常存在于java.util包中声离。

Java集合主要由2大體系構(gòu)成，分別是Collection體系和Map體系瘫怜，其中Collection和Map分別是2大體系中的頂層接口术徊。

Collection主要有三個(gè)子接口，分別為L(zhǎng)ist(列表)鲸湃、Set(集)赠涮、Queue(隊(duì)列)。其中暗挑，List笋除、Queue中的元素有序可重復(fù)，而Set中的元素?zé)o序不可重復(fù)；

List中主要有ArrayList、LinkedList兩個(gè)實(shí)現(xiàn)類；Set中則是有HashSet實(shí)現(xiàn)類实胸；而Queue是在JDK1.5后才出現(xiàn)的新集合，主要以數(shù)組和鏈表兩種形式存在椿访。

Map同屬于java.util包中，是集合的一部分，但與Collection是相互獨(dú)立的贝奇，沒有任何關(guān)系。Map中都是以key-value的形式存在靠胜，其中key必須唯一掉瞳，主要有HashMap、HashTable浪漠、TreeMap三個(gè)實(shí)現(xiàn)類陕习。

image.png

1 List

在Collection中，List集合是有序的址愿，Developer可對(duì)其中每個(gè)元素的插入位置進(jìn)行精確地控制该镣，可以通過索引來訪問元素，遍歷元素响谓。

在List集合中损合，我們常用到ArrayList和LinkedList這兩個(gè)類。

其中娘纷，ArrayList底層通過數(shù)組實(shí)現(xiàn)嫁审，隨著元素的增加而動(dòng)態(tài)擴(kuò)容。而LinkedList底層通過鏈表來實(shí)現(xiàn)赖晶，隨著元素的增加不斷向鏈表的后端增加節(jié)點(diǎn)律适。

ArrayList是Java集合框架中使用最多的一個(gè)類，是一個(gè)數(shù)組隊(duì)列遏插，線程不安全集合捂贿。

它繼承于AbstractList，實(shí)現(xiàn)了List, RandomAccess, Cloneable, Serializable接口涩堤。
(1)ArrayList實(shí)現(xiàn)List眷蜓，得到了List集合框架基礎(chǔ)功能；
(2)ArrayList實(shí)現(xiàn)RandomAccess胎围，獲得了快速隨機(jī)訪問存儲(chǔ)元素的功能吁系，RandomAccess是一個(gè)標(biāo)記接口，沒有任何方法白魂；
(3)ArrayList實(shí)現(xiàn)Cloneable汽纤，得到了clone()方法，可以實(shí)現(xiàn)克隆功能福荸；
(4)ArrayList實(shí)現(xiàn)Serializable蕴坪，表示可以被序列化，通過序列化去傳輸，典型的應(yīng)用就是hessian協(xié)議背传。

它具有如下特點(diǎn)：

• 容量不固定呆瞻，隨著容量的增加而動(dòng)態(tài)擴(kuò)容（閾值基本不會(huì)達(dá)到）
• 有序集合（插入的順序==輸出的順序）
• 插入的元素可以為null
• 增刪改查效率更高（相對(duì)于LinkedList來說）
• 線程不安全
  數(shù)據(jù)結(jié)構(gòu)：（JDK1.7）

image.png

LinkedList是一個(gè)雙向鏈表，每一個(gè)節(jié)點(diǎn)都擁有指向前后節(jié)點(diǎn)的引用径玖。相比于ArrayList來說痴脾，LinkedList的隨機(jī)訪問效率更低。

它繼承AbstractSequentialList梳星，實(shí)現(xiàn)了List, Deque, Cloneable, Serializable接口赞赖。
(1)LinkedList實(shí)現(xiàn)List，得到了List集合框架基礎(chǔ)功能冤灾；
(2)LinkedList實(shí)現(xiàn)Deque前域，Deque 是一個(gè)雙向隊(duì)列，也就是既可以先入先出韵吨，又可以先入后出匿垄，說簡(jiǎn)單些就是既可以在頭部添加元素，也可以在尾部添加元素归粉；
(3)LinkedList實(shí)現(xiàn)Cloneable年堆，得到了clone()方法，可以實(shí)現(xiàn)克隆功能盏浇；
(4)LinkedList實(shí)現(xiàn)Serializable变丧，表示可以被序列化，通過序列化去傳輸绢掰，典型的應(yīng)用就是hessian協(xié)議痒蓬。

數(shù)據(jù)結(jié)構(gòu)：（JDK1.7）

image.png

1.1 List常用方法

A:添加功能
boolean add(E e):向集合中添加一個(gè)元素
void add(int index, E element):在指定位置添加元素
boolean addAll(Collection<? extends E> c)：向集合中添加一個(gè)集合的元素。
    
B:刪除功能
void clear()：刪除集合中的所有元素
E remove(int index)：根據(jù)指定索引刪除元素滴劲，并把刪除的元素返回
boolean remove(Object o)：從集合中刪除指定的元素
boolean removeAll(Collection<?> c):從集合中刪除一個(gè)指定的集合元素攻晒。

C:修改功能
E set(int index, E element):把指定索引位置的元素修改為指定的值，返回修改前的值班挖。

D:獲取功能
E get(int index)：獲取指定位置的元素
Iterator iterator():就是用來獲取集合中每一個(gè)元素鲁捏。

E:判斷功能
boolean isEmpty()：判斷集合是否為空。
boolean contains(Object o)：判斷集合中是否存在指定的元素萧芙。
boolean containsAll(Collection<?> c)：判斷集合中是否存在指定的一個(gè)集合中的元素给梅。

F:長(zhǎng)度功能
int size():獲取集合中的元素個(gè)數(shù)

G:把集合轉(zhuǎn)換成數(shù)組
Object[] toArray():把集合變成數(shù)組。

1.2 ArrayList基本操作

public class ArrayListTest {
    public static void main(String[] agrs){
        //創(chuàng)建ArrayList集合：
        List<String> list = new ArrayList<String>();
        System.out.println("ArrayList集合初始化容量："+list.size());

        //添加功能：
        list.add("Hello");
        list.add("world");
        list.add(2,"!");
        System.out.println("ArrayList當(dāng)前容量："+list.size());

        //修改功能：
        list.set(0,"my");
        list.set(1,"name");
        System.out.println("ArrayList當(dāng)前內(nèi)容："+list.toString());

        //獲取功能：
        String element = list.get(0);
        System.out.println(element);

        //迭代器遍歷集合：(ArrayList實(shí)際的跌倒器是Itr對(duì)象)
        Iterator<String> iterator =  list.iterator();
        while(iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }
        
        //for循環(huán)迭代集合：
        for(String str:list){
            System.out.println(str);
        }

        //判斷功能：
        boolean isEmpty = list.isEmpty();
        boolean isContain = list.contains("my");

        //長(zhǎng)度功能：
        int size = list.size();

        //把集合轉(zhuǎn)換成數(shù)組：
        String[] strArray = list.toArray(new String[]{});

        //刪除功能：
        list.remove(0);
        list.remove("world");
        list.clear();
        System.out.println("ArrayList當(dāng)前容量："+list.size());
    }
}

1.3 LinkedList基本操作

public class LinkedListTest {
    public static void main(String[] agrs){
        List<String> linkedList = new LinkedList<String>();
        System.out.println("LinkedList初始容量："+linkedList.size());

        //添加功能：
        linkedList.add("my");
        linkedList.add("name");
        linkedList.add("is");
        linkedList.add("jiaboyan");
        System.out.println("LinkedList當(dāng)前容量："+ linkedList.size());

        //修改功能:
        linkedList.set(0,"hello");
        linkedList.set(1,"world");
        System.out.println("LinkedList當(dāng)前內(nèi)容："+ linkedList.toString());

        //獲取功能：
        String element = linkedList.get(0);
        System.out.println(element);

        //遍歷集合：(LinkedList實(shí)際的跌倒器是ListItr對(duì)象)
        Iterator<String> iterator =  linkedList.iterator();
        while(iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }
        //for循環(huán)迭代集合：
        for(String str:linkedList){
            System.out.println(str);
        }

        //判斷功能：
        boolean isEmpty = linkedList.isEmpty();
        boolean isContains = linkedList.contains("jiaboyan");

        //長(zhǎng)度功能：
        int size = linkedList.size();

        //刪除功能：
        linkedList.remove(0);
        linkedList.remove("jiaboyan");
        linkedList.clear();
        System.out.println("LinkedList當(dāng)前容量：" + linkedList.size());
    }
}

1.4 ArrayList和LinkedList比較

（1）元素新增性能比較：

查看了網(wǎng)上很多的例子双揪，很多都說动羽，在新增操作時(shí)，ArrayList效率不如LinkedList渔期，因?yàn)锳rrayList底層是數(shù)組實(shí)現(xiàn)运吓，在動(dòng)態(tài)擴(kuò)容時(shí)渴邦，性能有所損耗，而LinkedList不存在數(shù)組擴(kuò)容機(jī)制拘哨，所以LinkedList效率更高谋梭。那么結(jié)果究竟怎樣，來看下面的數(shù)據(jù)倦青！

public class ListTest {

    //迭代次數(shù)
    public static int ITERATION_NUM = 100000;

    public static void main(String[] agrs) {
        insertPerformanceCompare();
    }

    //新增性能比較：
    public static void insertPerformanceCompare() {
        Thread.sleep(5000);

        System.out.println("LinkedList新增測(cè)試開始");
        long start = System.nanoTime();
        List<Integer> linkedList = new LinkedList<Integer>();
        for (int x = 0; x < ITERATION_NUM; x++) {
            linkedList.add(x);
        }
        long end = System.nanoTime();
        System.out.println(end - start);

        System.out.println("ArrayList新增測(cè)試開始");
        start = System.nanoTime();
        List<Integer> arrayList = new ArrayList<Integer>();
        for (int x = 0; x < ITERATION_NUM; x++) {
            arrayList.add(x);
        }
        end = System.nanoTime();
        System.out.println(end - start);
    }
}

結(jié)果：

結(jié)果與預(yù)想的有些不太一樣章蚣，ArrayList的新增性能并不低。

究其原因姨夹，可能是經(jīng)過JDK近幾年的更新發(fā)展，對(duì)于數(shù)組復(fù)制的實(shí)現(xiàn)進(jìn)行了優(yōu)化矾策，以至于ArrayList的性能也得到了提高磷账。

image.png

（2）元素獲取比較：

由于LinkedList是鏈表結(jié)構(gòu)，沒有角標(biāo)的概念贾虽，沒有實(shí)現(xiàn)RandomAccess接口逃糟，不具備隨機(jī)元素訪問功能，所以在get方面表現(xiàn)的差強(qiáng)人意蓬豁，ArrayList再一次完勝绰咽。

public class ListTest {

    //迭代次數(shù)，集合大械胤唷：
    public static int ITERATION_NUM = 100000;

    public static void main(String[] agrs) {
        getPerformanceCompare();
    }

    //獲取性能比較：
    public static void getPerformanceCompare() {
        Thread.sleep(5000);
        
        //填充ArrayList集合：
        List<Integer> arrayList = new ArrayList<Integer>();
        for (int x = 0; x < ITERATION_NUM; x++) {
            arrayList.add(x);
        }

        //填充LinkedList集合：
        List<Integer> linkedList = new LinkedList<Integer>();
        for (int x = 0; x < ITERATION_NUM; x++) {
            linkedList.add(x);
        }

        //創(chuàng)建隨機(jī)數(shù)對(duì)象：
        Random random = new Random();

        System.out.println("LinkedList獲取測(cè)試開始");
        long start = System.nanoTime();
        for (int x = 0; x < ITERATION_NUM; x++) {
            int j = random.nextInt(x + 1);
            int k = linkedList.get(j);
        }
        long end = System.nanoTime();
        System.out.println(end - start);

        System.out.println("ArrayList獲取測(cè)試開始");
        start = System.nanoTime();
        for (int x = 0; x < ITERATION_NUM; x++) {
            int j = random.nextInt(x + 1);
            int k = arrayList.get(j);
        }
        end = System.nanoTime();
        System.out.println(end - start);
    }
}

結(jié)果：

從結(jié)果中可以看到取募，ArrayList在隨機(jī)訪問方面表現(xiàn)的十分優(yōu)秀，比LinkedList強(qiáng)了很多蟆技，基本上保持在10多倍以上玩敏。

LinkedList為什么這么慢呢？這主要是LinkedList的代碼實(shí)現(xiàn)所致质礼，每一次獲取都是從頭開始遍歷旺聚，一個(gè)個(gè)節(jié)點(diǎn)去查找，每查找一次就遍歷一次眶蕉，所以性能自然得不到提升砰粹。

image.png

1.5 ArrayList源碼分析（基于JDK1.7.0_45）

接下來，我們幾對(duì)ArrayList的源碼進(jìn)行一個(gè)解析造挽，其中筆者提出了幾個(gè)問題碱璃？

(1)ArrayList構(gòu)造

(2)增刪改查實(shí)現(xiàn)

(3)迭代器-modCount

(4)為什么數(shù)組對(duì)象要使用transient修飾符

(5)System.arraycopy（）參數(shù)含義 Arrays.copyOf（）參數(shù)含義

我們通過這這幾個(gè)問題，來一步步的學(xué)習(xí)ArrayList饭入！

• ArrayList構(gòu)造器：
  在JDK1.7版本中厘贼，ArrayList的無參構(gòu)造方法并沒有生成容量為10的數(shù)組；

elementData對(duì)象是ArrayList集合底層保存元素的實(shí)現(xiàn)圣拄；

size屬性記錄了ArrayList集合中實(shí)際元素的個(gè)數(shù)嘴秸；

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

    //實(shí)現(xiàn)Serializable接口，生成的序列版本號(hào)：
    private static final long serialVersionUID = 8683452581122892189L;

    //ArrayList初始容量大小：在無參構(gòu)造中不使用了
    private static final int DEFAULT_CAPACITY = 10;

    //空數(shù)組對(duì)象：初始化中默認(rèn)賦值給elementData
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //ArrayList中實(shí)際存儲(chǔ)元素的數(shù)組：
    private transient Object[] elementData;

    //集合實(shí)際存儲(chǔ)元素長(zhǎng)度：
    private int size;

    //ArrayList有參構(gòu)造：容量大小
    public ArrayList(int initialCapacity) {
        //即父類構(gòu)造：protected AbstractList() {}空方法
        super();
        //如果傳遞的初始容量小于0 岳掐，拋出異常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        //初始化數(shù)據(jù)：創(chuàng)建Object數(shù)組
        this.elementData = new Object[initialCapacity];
    }

    //ArrayList無參構(gòu)造：
    public ArrayList() {
        //即父類構(gòu)造：protected AbstractList() {}空方法
        super();
        //初始化數(shù)組：空數(shù)組凭疮，容量為0
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //ArrayList有參構(gòu)造：Java集合
    public ArrayList(Collection<? extends E> c) {
        //將集合轉(zhuǎn)換為數(shù)組：
        elementData = c.toArray();
        //設(shè)置數(shù)組的長(zhǎng)度：
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
}

• add()
  ArrayList增加元素的方法事關(guān)重要，我們都知道ArrayList底層是由數(shù)組串述，可以隨著元素的增加而擴(kuò)容执解，那么具體是如何實(shí)現(xiàn)的呢？

在JDK1.7當(dāng)中纲酗，當(dāng)?shù)谝粋€(gè)元素添加時(shí)衰腌，ensureCapacityInternal()方法會(huì)計(jì)算ArrayList的擴(kuò)容大小，默認(rèn)為10觅赊；

其中g(shù)row()方法最為重要右蕊，如果需要擴(kuò)容，那么擴(kuò)容后的大小是原來的1.5倍吮螺，實(shí)際上最終調(diào)用了Arrays.copyOf()方法得以實(shí)現(xiàn)饶囚；

//添加元素e
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    //將對(duì)應(yīng)角標(biāo)下的元素賦值為e：
    elementData[size++] = e;
    return true;
}
//得到最小擴(kuò)容量
private void ensureCapacityInternal(int minCapacity) {
    //如果此時(shí)ArrayList是空數(shù)組,則將最小擴(kuò)容大小設(shè)置為10：
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //判斷是否需要擴(kuò)容：
    ensureExplicitCapacity(minCapacity);
}
//判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
    //操作數(shù)+1
    modCount++;
    //判斷最小擴(kuò)容容量-數(shù)組大小是否大于0：
    if (minCapacity - elementData.length > 0)
        //擴(kuò)容：
        grow(minCapacity);
}
//ArrayList動(dòng)態(tài)擴(kuò)容的核心方法:
private void grow(int minCapacity) {
    //獲取現(xiàn)有數(shù)組大小：
    int oldCapacity = elementData.length;
    //位運(yùn)算鸠补，得到新的數(shù)組容量大小萝风，為原有的1.5倍：
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新擴(kuò)容的大小依舊小于傳入的容量值，那么將傳入的值設(shè)為新容器大凶涎摇：
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    //如果新容器大小规惰，大于ArrayList最大長(zhǎng)度：
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //計(jì)算出最大容量值：
        newCapacity = hugeCapacity(minCapacity);
    //數(shù)組復(fù)制：
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//計(jì)算ArrayList最大容量：
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)
        throw new OutOfMemoryError();
    //如果新的容量大于MAX_ARRAY_SIZE。將會(huì)調(diào)用hugeCapacity將int的最大值賦給newCapacity:
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

• remove()
  remove(int index)是針對(duì)于角標(biāo)來進(jìn)行刪除泉蝌，不需要去遍歷整個(gè)集合卿拴，效率更高；
  而remove(Object o)是針對(duì)于對(duì)象來進(jìn)行刪除梨与，需要遍歷整個(gè)集合進(jìn)行equals()方法比對(duì)堕花，所以效率較低；

不過粥鞋，無論是哪種形式的刪除缘挽，最終都會(huì)調(diào)用System.arraycopy()方法進(jìn)行數(shù)組復(fù)制操作，所以效率都會(huì)受到影響呻粹；

//在ArrayList的移除index位置的元素
public E remove(int index) {
    //檢查角標(biāo)是否合法：不合法拋異常
    rangeCheck(index);
    //操作數(shù)+1：
    modCount++;
    //獲取當(dāng)前角標(biāo)的value:
    E oldValue = elementData(index);
    //獲取需要?jiǎng)h除元素 到最后一個(gè)元素的長(zhǎng)度壕曼，也就是刪除元素后，后續(xù)元素移動(dòng)的個(gè)數(shù)等浊；
    int numMoved = size - index - 1;
    //如果移動(dòng)元素個(gè)數(shù)大于0 腮郊，也就是說刪除的不是最后一個(gè)元素：
    if (numMoved > 0)
        // 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //size減1，并將最后一個(gè)元素置為null
    elementData[--size] = null;
    //返回被刪除的元素：
    return oldValue;
}

//在ArrayList的移除對(duì)象為O的元素筹燕，不返回被刪除的元素：
public boolean remove(Object o) {
    //如果o==null轧飞，則遍歷集合衅鹿，判斷哪個(gè)元素為null：
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //快速刪除，和前面的remove（index）一樣的邏輯
                fastRemove(index);
                return true;
            }
    } else {
        //同理：
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//快速刪除：
private void fastRemove(int index) {
    //操作數(shù)+1
    modCount++;
    //獲取需要?jiǎng)h除元素 到最后一個(gè)元素的長(zhǎng)度过咬，也就是刪除元素后大渤，后續(xù)元素移動(dòng)的個(gè)數(shù)；
    int numMoved = size - index - 1;
    //如果移動(dòng)元素個(gè)數(shù)大于0 掸绞，也就是說刪除的不是最后一個(gè)元素：
    if (numMoved > 0)
        // 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //size減1泵三，并將最后一個(gè)元素置為null
    elementData[--size] = null;
}

• set()
  由于ArrayList實(shí)現(xiàn)了RandomAccess，所以具備了隨機(jī)訪問特性衔掸，調(diào)用elementData()可以獲取到對(duì)應(yīng)元素的值烫幕；

//設(shè)置index位置的元素值了element，返回該位置的之前的值
public E set(int index, E element) {
    //檢查index是否合法：判斷index是否大于size
    rangeCheck(index);
    //獲取該index原來的元素：
    E oldValue = elementData(index);
    //替換成新的元素：
    elementData[index] = element;
    //返回舊的元素：
    return oldValue;
}

• get()
  通過elementData()方法獲取對(duì)應(yīng)角標(biāo)元素敞映，在返回時(shí)候進(jìn)行類型轉(zhuǎn)換较曼；

//獲取index位置的元素
public E get(int index) {
    //檢查index是否合法：
    rangeCheck(index);
    //獲取元素：
    return elementData(index);
}
//獲取數(shù)組index位置的元素：返回時(shí)類型轉(zhuǎn)換
E elementData(int index) {
    return (E) elementData[index];
}

• modCount含義
  在Itr迭代器初始化時(shí),將ArrayList的modCount屬性的值賦值給了expectedModCount。

通過上面的例子中驱显，我們可以知道當(dāng)進(jìn)行增刪改時(shí)，modCount會(huì)隨著每一次的操作而+1瞳抓，modCount記錄了ArrayList內(nèi)發(fā)生改變的次數(shù)埃疫。

當(dāng)?shù)髟诘鷷r(shí)，會(huì)判斷expectedModCount的值是否還與modCount的值保持一致孩哑，如果不一致則拋出異常栓霜。

AbstractList類當(dāng)中定義的變量：

protected transient int modCount = 0;

ArrayList獲取迭代器對(duì)象：

//返回一個(gè)Iterator對(duì)象，Itr為ArrayList的一個(gè)內(nèi)部類横蜒，其實(shí)現(xiàn)了Iterator<E>接口
public Iterator<E> iterator() {
    return new java.util.ArrayList.Itr();
}

迭代器實(shí)現(xiàn)：

//Itr實(shí)現(xiàn)了Iterator接口胳蛮，是ArrayList集合的迭代器對(duì)象
private class Itr implements Iterator<E> {
    //類似游標(biāo)，指向迭代器下一個(gè)值的位置
    int cursor; 

    //迭代器最后一次取出的元素的位置丛晌。
    int lastRet = -1; 

    //Itr初始化時(shí)候ArrayList的modCount的值仅炊。
    int expectedModCount = modCount;

    //利用游標(biāo)，與size之前的比較澎蛛，判斷迭代器是否還有下一個(gè)元素
    public boolean hasNext() {
        return cursor != size;
    }
    
    //迭代器獲取下一個(gè)元素：
    public E next() {
        //檢查modCount是否改變：
        checkForComodification();
        int i = cursor;
        //游標(biāo)不會(huì)大于等于集合的長(zhǎng)度：
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = java.util.ArrayList.this.elementData;
        //游標(biāo)不會(huì)大于集合中數(shù)組的長(zhǎng)度：
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        //游標(biāo)+1
        cursor = i + 1;
        //取出元素：
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        //檢查modCount是否改變：防止并發(fā)操作集合
        checkForComodification();
        try {
            //刪除這個(gè)元素：
            java.util.ArrayList.this.remove(lastRet);
            //刪除后抚垄，重置游標(biāo)，和當(dāng)前指向元素的角標(biāo) lastRet
            cursor = lastRet;
            lastRet = -1;
            //重置expectedModCount：
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    //并發(fā)檢查：
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

• transient
  transient修飾符是什么含義谋逻？
  當(dāng)我們序列化對(duì)象時(shí)呆馁，如果對(duì)象中某個(gè)屬性不進(jìn)行序列化操作，那么在該屬性前添加transient修飾符即可實(shí)現(xiàn)毁兆；例如：

private transient Object[] elementData;

那么浙滤，為什么ArrayList不想對(duì)elementData屬性進(jìn)行序列化呢？elementData可是集合中保存元素的數(shù)組啊气堕，如果不序列化elementData屬性纺腊，那么在反序列化時(shí)候畔咧，豈不是丟失了原先的元素？
ArrayList在添加元素時(shí)摹菠，可能會(huì)對(duì)elementData數(shù)組進(jìn)行擴(kuò)容操作盒卸，而擴(kuò)容后的數(shù)組可能并沒有全部保存元素。
例如：我們創(chuàng)建了new Object[10]數(shù)組對(duì)象次氨，但是我們只向其中添加了1個(gè)元素蔽介，而剩余的9個(gè)位置并沒有添加元素。當(dāng)我們進(jìn)行序列化時(shí)煮寡，并不會(huì)只序列化其中一個(gè)元素虹蓄，而是將整個(gè)數(shù)組進(jìn)行序列化操作，那些沒有被元素填充的位置也進(jìn)行了序列化操作幸撕，間接的浪費(fèi)了磁盤的空間薇组，以及程序的性能。
所以坐儿，ArrayList才會(huì)在elementData屬性前加上transient修飾符律胀。
接下來，我們來看下ArrayList的writeObject()貌矿、readObject()：

//序列化寫入：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

// 序列化讀忍烤：
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
    s.defaultReadObject();
    s.readInt();
    if (size > 0) {
        ensureCapacityInternal(size);
        Object[] a = elementData;
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

ArrayList在序列化時(shí)會(huì)調(diào)用writeObject()，直接將elementData寫入ObjectOutputStream逛漫；
而反序列化時(shí)則調(diào)用readObject()黑低，從ObjectInputStream獲取elementData；

• Arrays.copyOf()
  該方法在內(nèi)部創(chuàng)建了一個(gè)新數(shù)組酌毡，底層實(shí)現(xiàn)是調(diào)用System.arraycopy()克握；

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

original - 要復(fù)制的數(shù)組
newLength - 要返回的副本的長(zhǎng)度
newType - 要返回的副本的類型

• System.arraycopy()
  該方法是用了native關(guān)鍵字，調(diào)用的為C++編寫的底層函數(shù).

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

src - 源數(shù)組枷踏。
srcPos - 源數(shù)組中的起始位置菩暗。
dest - 目標(biāo)數(shù)組。
destPos - 目標(biāo)數(shù)據(jù)中的起始位置旭蠕。
length - 要復(fù)制的數(shù)組元素的數(shù)量勋眯。

1.6 LinkedList源碼分析（基于JDK1.7.0_45）

在寫本篇LinkedList源碼之前，筆者也看了網(wǎng)上不少的講解文章下梢。
發(fā)現(xiàn)很多文章在介紹的時(shí)候客蹋，都說LinkedList是一個(gè)環(huán)形鏈表結(jié)構(gòu)，頭尾相連孽江。但讶坯，當(dāng)我開始看源碼的時(shí)候，發(fā)現(xiàn)并不是環(huán)形鏈表岗屏，是一個(gè)直線型鏈表結(jié)構(gòu)辆琅，我一度以為是我理解有誤漱办。后來發(fā)現(xiàn)，JDK1.7之前的版本是環(huán)形鏈表婉烟，而到了JDK1.7以后進(jìn)行了優(yōu)化娩井，變成了直線型鏈表結(jié)構(gòu)；

• 集合基礎(chǔ)結(jié)構(gòu)
  在LinkedList中似袁，內(nèi)部類Node對(duì)象最為重要洞辣，它組成了LinkedList集合的整個(gè)鏈表，分別指向上一個(gè)點(diǎn)昙衅、下一個(gè)結(jié)點(diǎn)扬霜，存儲(chǔ)著集合中的元素；
  成員變量中而涉，first表明是頭結(jié)點(diǎn)著瓶，last表明是尾結(jié)點(diǎn)；

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    //LinkedList的元素個(gè)數(shù)：
    transient int size = 0;

    //LinkedList的頭結(jié)點(diǎn)：Node內(nèi)部類
    transient java.util.LinkedList.Node<E> first;

    //LinkedList尾結(jié)點(diǎn)：Node內(nèi)部類
    transient java.util.LinkedList.Node<E> last;

    //空實(shí)現(xiàn)：頭尾結(jié)點(diǎn)均為null啼县，鏈表不存在
    public LinkedList() {
    }

    //調(diào)用添加方法：
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    //節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)材原，包含前后節(jié)點(diǎn)的引用和當(dāng)前節(jié)點(diǎn)
    private static class Node<E> {
        //結(jié)點(diǎn)元素：
        E item;
        //結(jié)點(diǎn)后指針
        java.util.LinkedList.Node<E> next;
        //結(jié)點(diǎn)前指針
        java.util.LinkedList.Node<E> prev;

        Node(java.util.LinkedList.Node<E> prev, E element, java.util.LinkedList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

• add()
  LinkedList的添加方法，主要分為2種季眷，一是直接添加一個(gè)元素余蟹，二是在指定角標(biāo)下添加一個(gè)元素；
  add(E e)底層調(diào)用linkLast(E e)方法瘟裸，就是在鏈表的最后面插入一個(gè)元素客叉；
  add(int index, E element)诵竭，插入的角標(biāo)如果==size话告，則插入到鏈表最后；否則卵慰，按照角標(biāo)大小插入到對(duì)應(yīng)位置沙郭；

//添加元素：添加到最后一個(gè)結(jié)點(diǎn)；
public boolean add(E e) {
    linkLast(e);
    return true;
}

//last節(jié)點(diǎn)插入新元素：
void linkLast(E e) {
    //將尾結(jié)點(diǎn)賦值個(gè)體L:
    final java.util.LinkedList.Node<E> l = last;
    //創(chuàng)建新的結(jié)點(diǎn)裳朋，將新節(jié)點(diǎn)的前指針指向l:
    final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
    //新節(jié)點(diǎn)置為尾結(jié)點(diǎn)：
    last = newNode;
    //如果尾結(jié)點(diǎn)l為null：則是空集合新插入
    if (l == null)
        //頭結(jié)點(diǎn)也置為 新節(jié)點(diǎn)：
        first = newNode;
    else
        //l節(jié)點(diǎn)的后指針指向新節(jié)點(diǎn)：
        l.next = newNode;
    //長(zhǎng)度+1
    size++;
    //操作數(shù)+1
    modCount++;
}

//向?qū)?yīng)角標(biāo)添加元素：
public void add(int index, E element) {
    //檢查傳入的角標(biāo) 是否正確：
    checkPositionIndex(index);
    //如果插入角標(biāo)==集合長(zhǎng)度病线，則插入到集合的最后面：
    if (index == size)
        linkLast(element);
    else
        //插入到對(duì)應(yīng)角標(biāo)的位置：獲取此角標(biāo)下的元素先
        linkBefore(element, node(index));
}
//在succ前插入 新元素e：
void linkBefore(E e, java.util.LinkedList.Node<E> succ) {
    //獲取被插入元素succ的前指針元素：
    final java.util.LinkedList.Node<E> pred = succ.prev;
    //創(chuàng)建新增元素節(jié)點(diǎn)，前指針 和 后指針分別指向?qū)?yīng)元素：
    final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
    succ.prev = newNode;
    //succ的前指針元素可能為null鲤嫡，為null的話說明succ是頭結(jié)點(diǎn)送挑，則把新建立的結(jié)點(diǎn)置為頭結(jié)點(diǎn)：
    if (pred == null)
        first = newNode;
    else
        //succ前指針不為null，則將前指針的結(jié)點(diǎn)的后指針指向新節(jié)點(diǎn)：
        pred.next = newNode;
    //長(zhǎng)度+1
    size++;
    //操作數(shù)+1
    modCount++;
}

對(duì)于LinkedList集合增加元素來說暖眼，可以簡(jiǎn)單的概括為以下幾點(diǎn)：
將添加的元素轉(zhuǎn)換為L(zhǎng)inkedList的Node對(duì)象節(jié)點(diǎn)惕耕；
增加該Node節(jié)點(diǎn)的前后引用，即該Node節(jié)點(diǎn)的prev诫肠、next屬性司澎，讓其分別指向哪一個(gè)節(jié)點(diǎn)）欺缘；
修改該Node節(jié)點(diǎn)的前后Node節(jié)點(diǎn)中pre/next屬性，使其指向該節(jié)點(diǎn)挤安。

image.png

• remove()
  LinkedList的刪除也提供了2種形式谚殊，其一是通過角標(biāo)刪除元素，其二就是通過對(duì)象刪除元素蛤铜；不過嫩絮，無論哪種刪除，最終調(diào)用的都是unlink來實(shí)現(xiàn)的昂羡；

//刪除對(duì)應(yīng)角標(biāo)的元素：
public E remove(int index) {
    checkElementIndex(index);
    //node()方法通過角標(biāo)獲取對(duì)應(yīng)的元素絮记，在后面介紹
    return unlink(node(index));
}

//刪除LinkedList中的元素，可以刪除為null的元素虐先，逐個(gè)遍歷LinkedList的元素怨愤，重復(fù)元素只刪除第一個(gè)：
public boolean remove(Object o) {
    //如果刪除元素為null：
    if (o == null) {
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        //如果刪除元素不為null：
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

//移除LinkedList結(jié)點(diǎn)：remove()方法中調(diào)用
E unlink(java.util.LinkedList.Node<E> x) {
    //獲取被刪除結(jié)點(diǎn)的元素E：
    final E element = x.item;
    //獲取被刪除元素的后指針結(jié)點(diǎn)：
    final java.util.LinkedList.Node<E> next = x.next;
    //獲取被刪除元素的前指針結(jié)點(diǎn)：
    final java.util.LinkedList.Node<E> prev = x.prev;

    //被刪除結(jié)點(diǎn)的 前結(jié)點(diǎn)為null的話：
    if (prev == null) {
        //將后指針指向的結(jié)點(diǎn)置為頭結(jié)點(diǎn)
        first = next;
    } else {
        //前置結(jié)點(diǎn)的  尾結(jié)點(diǎn)指向被刪除的next結(jié)點(diǎn)；
        prev.next = next;
        //被刪除結(jié)點(diǎn)前指針置為null:
        x.prev = null;
    }
    //對(duì)尾結(jié)點(diǎn)同樣處理：
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

• set()
  LinkedList的set(int index, E element)方法與add(int index,E element)的設(shè)計(jì)思路基本一致蛹批，都是創(chuàng)建新Node節(jié)點(diǎn)撰洗，插入到對(duì)應(yīng)的角標(biāo)下，修改前后節(jié)點(diǎn)的prev腐芍、next屬性差导；
  其中，node(int index)方法至關(guān)重要猪勇，通過對(duì)應(yīng)角標(biāo)獲取到對(duì)應(yīng)的集合元素设褐。
  可以看到，node（）中是根據(jù)角標(biāo)的大小是選擇從前遍歷還是從后遍歷整個(gè)集合泣刹。也可以間接的說明助析，LinkedList在隨機(jī)獲取元素時(shí)性能很低，每次的獲取都得從頭或者從尾遍歷半個(gè)集合椅您。

//設(shè)置對(duì)應(yīng)角標(biāo)的元素：
public E set(int index, E element) {
    checkElementIndex(index);
    //通過node()方法外冀，獲取到對(duì)應(yīng)角標(biāo)的元素：
    java.util.LinkedList.Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

//獲取對(duì)應(yīng)角標(biāo)所屬于的結(jié)點(diǎn)：
java.util.LinkedList.Node<E> node(int index) {
    //位運(yùn)算：如果位置索引小于列表長(zhǎng)度的一半，則從頭開始遍歷掀泳；否則雪隧，從后開始遍歷；
    if (index < (size >> 1)) {
        java.util.LinkedList.Node<E> x = first;
        //從頭結(jié)點(diǎn)開始遍歷：遍歷的長(zhǎng)度就是index的長(zhǎng)度员舵，獲取對(duì)應(yīng)的index的元素
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //從集合尾結(jié)點(diǎn)遍歷：
        java.util.LinkedList.Node<E> x = last;
        //同樣道理：
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

• get()
  get(int index)
  終于到了最后一個(gè)方法脑沿，也是開發(fā)中最常用的方法。其中马僻，核心方法node(int index)在上面已經(jīng)介紹過庄拇。
  在通過node(int index)獲取到對(duì)應(yīng)節(jié)點(diǎn)后，返回節(jié)點(diǎn)中的item屬性巫玻，該屬性就是我們所保存的元素丛忆。

//獲取相應(yīng)角標(biāo)的元素：
public E get(int index) {
    //檢查角標(biāo)是否正確：
    checkElementIndex(index);
    //獲取角標(biāo)所屬結(jié)點(diǎn)的 元素值：
    return node(index).item;
}

• 迭代器
  在LinkedList中祠汇，并沒有自己實(shí)現(xiàn)iterator()方法，而是使用其父類AbstractSequentialList的iterator()方法;

List<String> linkedList = new LinkedList<String>();
Iterator<String> iterator =  linkedList.iterator();

父類AbstractSequentialList中的 iterator():

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    public Iterator<E> iterator() {
        return listIterator();
    }
}

父類AbstractList中的 listIterator()：

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {            
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
}

LinkedList中的 listIterator()：

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {}