Java集合

作為一個(gè)Developer逸寓，Java集合類是我們?cè)诠ぷ髦羞\(yùn)用最多的峡眶、最頻繁的類。相比于數(shù)組(Array)來(lái)說(shuō)京革，集合類的長(zhǎng)度可變奇唤，更加適合于現(xiàn)代開(kāi)發(fā)需求；

Java集合就像一個(gè)容器匹摇，可以存儲(chǔ)任何類型的數(shù)據(jù)咬扇，也可以結(jié)合泛型來(lái)存儲(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ú)立的孽尽，沒(méi)有任何關(guān)系。Map中都是以key-value的形式存在忧勿，其中key必須唯一杉女，主要有HashMap、HashTable鸳吸、TreeMap三個(gè)實(shí)現(xiàn)類熏挎。

1 List

在Collection中，List集合是有序的晌砾，Developer可對(duì)其中每個(gè)元素的插入位置進(jìn)行精確地控制坎拐，可以通過(guò)索引來(lái)訪問(wèn)元素，遍歷元素养匈。

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

其中呕乎，ArrayList底層通過(guò)數(shù)組實(shí)現(xiàn)积担，隨著元素的增加而動(dòng)態(tài)擴(kuò)容。而LinkedList底層通過(guò)鏈表來(lái)實(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ī)訪問(wèn)存儲(chǔ)元素的功能把曼，RandomAccess是一個(gè)標(biāo)記接口杨帽，沒(méi)有任何方法；
(3)ArrayList實(shí)現(xiàn)Cloneable嗤军，得到了clone()方法注盈，可以實(shí)現(xiàn)克隆功能；
(4)ArrayList實(shí)現(xiàn)Serializable叙赚，表示可以被序列化老客，通過(guò)序列化去傳輸，典型的應(yīng)用就是hessian協(xié)議震叮。

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

• 容量不固定胧砰，隨著容量的增加而動(dòng)態(tài)擴(kuò)容（閾值基本不會(huì)達(dá)到）
• 有序集合（插入的順序==輸出的順序）
• 插入的元素可以為null
• 增刪改查效率更高（相對(duì)于LinkedList來(lái)說(shuō)）
• 線程不安全

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

LinkedList是一個(gè)雙向鏈表，每一個(gè)節(jié)點(diǎn)都擁有指向前后節(jié)點(diǎn)的引用苇瓣。相比于ArrayList來(lái)說(shuō)尉间，LinkedList的隨機(jī)訪問(wèn)效率更低。

它繼承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ì)列，也就是既可以先入先出损话，又可以先入后出侦啸，說(shuō)簡(jiǎn)單些就是既可以在頭部添加元素槽唾，也可以在尾部添加元素丧枪；
(3)LinkedList實(shí)現(xiàn)Cloneable，得到了clone()方法庞萍，可以實(shí)現(xiàn)克隆功能拧烦；
(4)LinkedList實(shí)現(xiàn)Serializable，表示可以被序列化钝计，通過(guò)序列化去傳輸恋博，典型的應(yīng)用就是hessian協(xié)議。

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

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():就是用來(lái)獲取集合中每一個(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)上很多的例子鲤拿，很多都說(shuō)假褪，在新增操作時(shí)，ArrayList效率不如LinkedList近顷，因?yàn)锳rrayList底層是數(shù)組實(shí)現(xiàn)生音，在動(dòng)態(tài)擴(kuò)容時(shí)，性能有所損耗窒升，而LinkedList不存在數(shù)組擴(kuò)容機(jī)制久锥，所以LinkedList效率更高。那么結(jié)果究竟怎樣异剥，來(lái)看下面的數(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è)試開(kāi)始");
        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è)試開(kāi)始");
        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)過(guò)JDK近幾年的更新發(fā)展，對(duì)于數(shù)組復(fù)制的實(shí)現(xiàn)進(jìn)行了優(yōu)化督怜，以至于ArrayList的性能也得到了提高殴瘦。

（2）元素獲取比較：

由于LinkedList是鏈表結(jié)構(gòu)，沒(méi)有角標(biāo)的概念号杠，沒(méi)有實(shí)現(xiàn)RandomAccess接口蚪腋，不具備隨機(jī)元素訪問(wèn)功能，所以在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è)試開(kāi)始");
        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è)試開(kāi)始");
        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ī)訪問(wèn)方面表現(xiàn)的十分優(yōu)秀，比LinkedList強(qiáng)了很多堂飞，基本上保持在10多倍以上灌旧。

LinkedList為什么這么慢呢？這主要是LinkedList的代碼實(shí)現(xiàn)所致绰筛，每一次獲取都是從頭開(kāi)始遍歷枢泰，一個(gè)個(gè)節(jié)點(diǎn)去查找，每查找一次就遍歷一次铝噩，所以性能自然得不到提升衡蚂。

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

接下來(lái)，我們幾對(duì)ArrayList的源碼進(jìn)行一個(gè)解析，其中筆者提出了幾個(gè)問(wèn)題讳窟？

(1)ArrayList構(gòu)造

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

(3)迭代器-modCount

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

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

我們通過(guò)這這幾個(gè)問(wèn)題让歼，來(lái)一步步的學(xué)習(xí)ArrayList！

• ArrayList構(gòu)造器：

在JDK1.7版本中丽啡，ArrayList的無(wú)參構(gòu)造方法并沒(méi)有生成容量為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初始容量大小：在無(wú)參構(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無(wú)參構(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ò)容后的大小是原來(lái)的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)來(lái)進(jìn)行刪除射窒，不需要去遍歷整個(gè)集合，效率更高将塑；

而remove(Object o)是針對(duì)于對(duì)象來(lái)進(jìn)行刪除脉顿，需要遍歷整個(gè)集合進(jìn)行equals()方法比對(duì)，所以效率較低点寥；

不過(guò)艾疟，無(wú)論是哪種形式的刪除，最終都會(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 怠苔，也就是說(shuō)刪除的不是最后一個(gè)元素：
    if (numMoved > 0)
        // 將elementData數(shù)組index+1位置開(kāi)始拷貝到elementData從index開(kāi)始的空間
        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 玻粪，也就是說(shuō)刪除的不是最后一個(gè)元素：
    if (numMoved > 0)
        // 將elementData數(shù)組index+1位置開(kāi)始拷貝到elementData從index開(kāi)始的空間
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //size減1，并將最后一個(gè)元素置為null
    elementData[--size] = null;
}

• set()

由于ArrayList實(shí)現(xiàn)了RandomAccess诬垂，所以具備了隨機(jī)訪問(wèn)特性奶段，調(diào)用elementData()可以獲取到對(duì)應(yīng)元素的值；

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

• get()

通過(guò)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晦鞋。

通過(guò)上面的例子中蹲缠，我們可以知道當(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ù)組可能并沒(méi)有全部保存元素。

例如：我們創(chuàng)建了new Object[10]數(shù)組對(duì)象葱轩，但是我們只向其中添加了1個(gè)元素睦焕，而剩余的9個(gè)位置并沒(méi)有添加元素。當(dāng)我們進(jìn)行序列化時(shí)靴拱，并不會(huì)只序列化其中一個(gè)元素垃喊，而是將整個(gè)數(shù)組進(jìn)行序列化操作，那些沒(méi)有被元素填充的位置也進(jìn)行了序列化操作袜炕，間接的浪費(fèi)了磁盤(pán)的空間本谜，以及程序的性能。

所以偎窘，ArrayList才會(huì)在elementData屬性前加上transient修飾符乌助。

接下來(lái)，我們來(lái)看下ArrayList的writeObject()陌知、readObject()：

//序列化寫(xiě)入：
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寫(xiě)入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++編寫(xiě)的底層函數(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）

在寫(xiě)本篇LinkedList源碼之前，筆者也看了網(wǎng)上不少的講解文章万伤。

發(fā)現(xiàn)很多文章在介紹的時(shí)候窒悔，都說(shuō)LinkedList是一個(gè)環(huán)形鏈表結(jié)構(gòu)，頭尾相連敌买。但简珠，當(dāng)我開(kāi)始看源碼的時(shí)候，發(fā)現(xiàn)并不是環(huán)形鏈表虹钮，是一個(gè)直線型鏈表結(jié)構(gòu)聋庵，我一度以為是我理解有誤。后來(lái)發(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)澈段，前指針 和 后指針?lè)謩e指向?qū)?yīng)元素：
    final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
    succ.prev = newNode;
    //succ的前指針元素可能為null，為null的話說(shuō)明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集合增加元素來(lái)說(shuō)，可以簡(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)蒂秘。

• remove()

LinkedList的刪除也提供了2種形式泽本，其一是通過(guò)角標(biāo)刪除元素，其二就是通過(guò)對(duì)象刪除元素材彪；不過(guò)观挎，無(wú)論哪種刪除，最終調(diào)用的都是unlink來(lái)實(shí)現(xiàn)的段化；

//刪除對(duì)應(yīng)角標(biāo)的元素：
public E remove(int index) {
    checkElementIndex(index);
    //node()方法通過(guò)角標(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)重要橙弱，通過(guò)對(duì)應(yīng)角標(biāo)獲取到對(duì)應(yīng)的集合元素歧寺。

可以看到，node（）中是根據(jù)角標(biāo)的大小是選擇從前遍歷還是從后遍歷整個(gè)集合棘脐。也可以間接的說(shuō)明斜筐，LinkedList在隨機(jī)獲取元素時(shí)性能很低，每次的獲取都得從頭或者從尾遍歷半個(gè)集合蛀缝。

//設(shè)置對(duì)應(yīng)角標(biāo)的元素：
public E set(int index, E element) {
    checkElementIndex(index);
    //通過(guò)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)度的一半，則從頭開(kāi)始遍歷屈梁；否則嗤练，從后開(kāi)始遍歷榛了；
    if (index < (size >> 1)) {
        java.util.LinkedList.Node<E> x = first;
        //從頭結(jié)點(diǎn)開(kāi)始遍歷：遍歷的長(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è)方法潭苞，也是開(kāi)發(fā)中最常用的方法忽冻。其中真朗，核心方法node(int index)在上面已經(jīng)介紹過(guò)此疹。

在通過(guò)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中，并沒(méi)有自己實(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> {}

注：LinkedList實(shí)現(xiàn)的Deque隊(duì)列的方法蹦骑，等講到Deque時(shí)在闡述；