Java中List集合介紹（炒雞詳細(xì)呦）

1培慌，Java集合介紹

作為一個(gè)程序猿图筹，Java集合類可以說是我們?cè)诠ぷ髦羞\(yùn)用最多卫漫、最頻繁的類菲饼。相比于數(shù)組（Array）來說，集合類的長度可變列赎，更加方便開發(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è)子接口竭翠，分別為List(列表)、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)類汁咏。

5621908-7942b72db40da267.png

2亚斋，List介紹

在Collection中，List集合是有序的攘滩，可對(duì)其中每個(gè)元素的插入位置進(jìn)行精確地控制帅刊，可以通過索引來訪問元素，遍歷元素漂问。

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

2.1 ArrayList集合

1蚤假，ArrayList底層通過數(shù)組實(shí)現(xiàn)栏饮，隨著元素的增加而動(dòng)態(tài)擴(kuò)容。

2勤哗，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é)議七问。

ArrayList集合的特點(diǎn)：

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

ArrayList的底層數(shù)據(jù)結(jié)構(gòu)：

5621908-36ce970172e9c687.png

2.2 LinkedList集合

1，LinkedList底層通過鏈表來實(shí)現(xiàn)械巡，隨著元素的增加不斷向鏈表的后端增加節(jié)點(diǎn)刹淌。

2，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)單點(diǎn)就是既可以在頭部添加元素粟耻，也可以在尾部添加元素查近；
3，LinkedList實(shí)現(xiàn)Cloneable挤忙，得到了clone()方法霜威，可以實(shí)現(xiàn)克隆功能；
4册烈，LinkedList實(shí)現(xiàn)Serializable戈泼，表示可以被序列化，通過序列化去傳輸赏僧，典型的應(yīng)用就是hessian協(xié)議大猛。

LinkedList集合的底層數(shù)據(jù)結(jié)構(gòu)：

5621908-3c2ee31c5af228ca.png

3，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:長度功能
int size():獲取集合中的元素個(gè)數(shù)

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

3.1 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());
        // ArrayList集合初始化容量：0
        
        //添加功能：
        list.add("Hello");
        list.add("world");
        list.add(2,"!");
        System.out.println("ArrayList當(dāng)前容量："+list.size());
        // ArrayList當(dāng)前容量：3

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

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

        //迭代器遍歷集合：(ArrayList實(shí)際的跌倒器是Itr對(duì)象)
        Iterator<String> iterator =  list.iterator();
        while(iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }
        /**  
            my
            name
            !
        */

        //for循環(huán)迭代集合：
        for(String str:list){
            System.out.println(str);
        }
        /**  
            my
            name
            !
        */

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

        //長度功能：
        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());
        // ArrayList當(dāng)前容量：0
    }
}

3.2 LinkedList 基本操作

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

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

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

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

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

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

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

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

4趾撵，ArrayList和LinkedList比較

（1）元素新增性能比較

網(wǎng)上很多說的是侄柔，在做新增操作時(shí)，ArrayList的效率遠(yuǎn)不如LinkedList占调，因?yàn)?code>Arraylist底層時(shí)數(shù)組實(shí)現(xiàn)的暂题，在動(dòng)態(tài)擴(kuò)容時(shí)，性能會(huì)有所損耗究珊，而LinkedList不存在數(shù)組擴(kuò)容機(jī)制薪者，所以LinkedList的新增性能較好。究竟時(shí)哪個(gè)好呢剿涮，我們用實(shí)踐得到結(jié)果言津。

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

    public static void main(String[] args) {
        try{
            insertPerformanceCompare();
        }catch (Exception e){}
    }

    //新增性能比較：
    public static void insertPerformanceCompare() throws InterruptedException {
        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);
    }
}

測(cè)試結(jié)果：

第一次：
    LinkedList新增測(cè)試開始
    10873720
    ArrayList新增測(cè)試開始
    5535277
第二次：
    LinkedList新增測(cè)試開始
    13097503
    ArrayList新增測(cè)試開始
    6046139
第三次：
    LinkedList新增測(cè)試開始
    12004669
    ArrayList新增測(cè)試開始
    6509783

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

原因：

? 可能是經(jīng)過JDK近幾年的更新發(fā)展悬槽，對(duì)于數(shù)組復(fù)制的實(shí)現(xiàn)進(jìn)行了優(yōu)化，以至于ArrayList的性能也得到了提高瞬浓。

（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) {
       try{
            getPerformanceCompare();
        }catch (Exception e){}
    }

    //獲取性能比較：
    public static void getPerformanceCompare()throws InterruptedException {
        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);
    }
}

測(cè)試結(jié)果：

第一次：
    LinkedList獲取測(cè)試開始
    8190063123
    ArrayList獲取測(cè)試開始
    8590205
第二次：
    LinkedList獲取測(cè)試開始
    8100623160
    ArrayList獲取測(cè)試開始
    11948919
第三次：
    LinkedList獲取測(cè)試開始
    8237722833
    ArrayList獲取測(cè)試開始
    6333427

從結(jié)果可以看出位迂，ArrayList在隨機(jī)訪問方面表現(xiàn)的十分優(yōu)秀访雪，比LinkedList強(qiáng)了很多。

原因：

? 這主要是LinkedList的代碼實(shí)現(xiàn)所致掂林，每一次獲取都是從頭開始遍歷臣缀，一個(gè)個(gè)節(jié)點(diǎn)去查找，每查找一次就遍歷一次泻帮，所以性能自然得不到提升精置。

5，ArrayList源碼分析

接下來锣杂，我們對(duì)ArrayList集合進(jìn)行源碼分析脂倦，其中先來幾個(gè)問題：

（1）ArrayList的構(gòu)造

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

（3）迭代器——modCount

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

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

我們通過上面幾個(gè)問題番宁，對(duì)ArrayList的源碼進(jìn)行一步一步的解析。

ArrayList構(gòu)造器

1赖阻，在JDK1.7版本中蝶押，ArrayList的無參構(gòu)造方法并沒有生成容量為10的數(shù)組。

2火欧，elementData對(duì)象是ArrayList集合底層保存元素的實(shí)現(xiàn)棋电。

3，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ǔ)元素長度：
    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ù)組的長度：
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
}

add() 添加

1，在JDK1.7當(dāng)中哀军，當(dāng)?shù)谝粋€(gè)元素添加時(shí)沉眶，ensureCapacityInternal()方法會(huì)計(jì)算ArrayList的擴(kuò)容大小，默認(rèn)為10杉适。

2，其中grow()方法最為重要柳击，如果需要擴(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最大長度：
    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() 刪除

1，remove(int index)是針對(duì)于角標(biāo)來進(jìn)行刪除西设，不需要去遍歷整個(gè)集合厕吉，效率更高枢步。

2，而remove(Object o)是針對(duì)于對(duì)象來進(jìn)行刪除，需要遍歷整個(gè)集合進(jìn)行equals()方法比對(duì)署隘，所以效率較低。

3，不過，無論是哪種形式的刪除洪规，最終都會(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è)元素的長度淹冰，也就是刪除元素后，后續(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è)元素的長度正罢，也就是刪除元素后，后續(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含義

1蝗柔，在Itr迭代器初始化時(shí),將ArrayList的modCount屬性的值賦值給了expectedModCount闻葵。

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

3厢钧，當(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ì)大于等于集合的長度：
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = java.util.ArrayList.this.elementData;
        //游標(biāo)不會(huì)大于集合中數(shù)組的長度：
        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 修飾符

1，當(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();
        }
    }
}

1葫辐，ArrayList在序列化時(shí)會(huì)調(diào)用writeObject()搜锰，直接將elementData寫入ObjectOutputStream。

2耿战，反序列化時(shí)則調(diào)用readObject()蛋叼，從ObjectInputStream獲取elementData。

Arrays.copyOf() 數(shù)組擴(kuò)容

該方法在內(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 - 要返回的副本的長度

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ù)量暴浦。

6，LinkedList源碼分析

看到網(wǎng)上都說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)

1，在LinkedList中匣吊，內(nèi)部類Node對(duì)象最為重要儒拂，它組成了LinkedList集合的整個(gè)鏈表，分別指向上一個(gè)點(diǎn)色鸳、下一個(gè)結(jié)點(diǎn)社痛，存儲(chǔ)著集合中的元素。

2命雀，成員變量中蒜哀，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è)元素匈织。

（1）add(E e)底層調(diào)用linkLast(E e)方法浪默，就是在鏈表的最后面插入一個(gè)元素。

（2）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;
    //長度+1
    size++;
    //操作數(shù)+1
    modCount++;
}

//向?qū)?yīng)角標(biāo)添加元素：
public void add(int index, E element) {
    //檢查傳入的角標(biāo) 是否正確：
    checkPositionIndex(index);
    //如果插入角標(biāo)==集合長度掸哑，則插入到集合的最后面：
    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;
    //長度+1
    size++;
    //操作數(shù)+1
    modCount++;
}

對(duì)于LinkedList集合增加元素來說，可以簡(jiǎn)單的概括為以下幾點(diǎn)：

1摔癣，將添加的元素轉(zhuǎn)換為LinkedList的Node對(duì)象節(jié)點(diǎn)奴饮。

2，增加該Node節(jié)點(diǎn)的前后引用择浊，即該Node節(jié)點(diǎn)的prev戴卜、next屬性，讓其分別指向哪一個(gè)節(jié)點(diǎn)）琢岩。

3投剥，修改該Node節(jié)點(diǎn)的前后Node節(jié)點(diǎn)中pre/next屬性，使其指向該節(jié)點(diǎn)担孔。

5621908-b9b9a5292a25c6cd.jpg

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() 修改元素

1泰鸡，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屬性。

2余舶，其中啊鸭，node(int index)方法至關(guān)重要，通過對(duì)應(yīng)角標(biāo)獲取到對(duì)應(yīng)的集合元素匿值。

3赠制，可以看到，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)算：如果位置索引小于列表長度的一半，則從頭開始遍歷达传；否則篙耗，從后開始遍歷；
    if (index < (size >> 1)) {
        java.util.LinkedList.Node<E> x = first;
        //從頭結(jié)點(diǎn)開始遍歷：遍歷的長度就是index的長度宪赶，獲取對(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)

在通過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> {}

7追他，小結(jié)

本篇文章簡(jiǎn)單介紹了Java中List集合，由于純手打岛蚤，難免會(huì)有紕漏邑狸，如果發(fā)現(xiàn)錯(cuò)誤的地方，請(qǐng)第一時(shí)間告訴我涤妒，這將是我進(jìn)步的一個(gè)很重要的環(huán)節(jié)单雾。