細談ArrayList和LinkedList (1)

引言

作為java開發人員，相信大家對ArrayList和LinkedList都不陌生，new她分分鐘一個，而且ArrayList查詢快，增刪慢and LinkedList增刪快，查詢慢的特點可謂無人不知，無人不曉，但是作為龐大的JDK集合團隊允許你兩句話就能做出解釋嗎，或者說疑惑的你就不想證明點什么？雖然每天跟她在代碼中恩恩愛愛，你儂我儂，就像跟你的女朋友卿卿我我好多年，但是突然有一天她問起：“你了解我嗎？”，
你：“了解！”，
“不，你不了解！”

ArrayList實作介面、繼承類

要想知道一個類能做什么，首先得了解她實作了哪些介面以及介面的特點，雖然每天跟她face to face，很多致命細節都會落空，這件事得追溯的幾天前，我同事阿涵上周陪她女朋友去逛街，他女朋友看中了一雙鞋很漂亮，非得要買，阿涵百般阻止，她女友開口了，說：“如果你能說出我的腳碼，我就不買了”， 阿涵猶豫了兩秒鐘，靈光一閃，看著自己腳底的鞋子跟女友腳底的鞋子，目測差了4公分，
阿涵自信滿滿的說：“39”，
女友淚目，阿涵以為她被感動了，“阿涵，我們分手吧”，
阿涵一臉懵A?C，就問了：“為什么呀 ?”，
女友：“你不了解我，我們在一起這么久了都不知道我的腳碼，都不如專柜的那個帥帥的男生了解我”，
阿涵既憤怒又懊悔，在商場大聲哭啼，鼻涕四濺，哀求挽留， “Please don’t leave me, please !”，
女友看出來阿涵對她是真愛，給了他一次機會，說：“阿涵，既然你跟代碼在一起的時間比跟我在一起的時間都長，那么給我解釋一下ArrayList吧！”
阿涵第一時間喊我，“阿選，幫我搞定ArrayList，我請你吃大餐”，為了挽救阿涵這段來之不易的感情，為了讓阿涵頭頂上變得風輕云淡，我決定摩擦ArrayList！

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

對比

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

RandomAccess

原始碼解釋大概意思是，他是一個介面標記，支持隨機訪問（基于下標），用于區分ArrayList和LinkedList，更好的去選擇遍歷優化方式，提高性能，

Cloneable

Cloneable是一個介面，實作這個介面，重寫clone方法，默認呼叫父類clone方法，
我舉一個例子，便于理解：
定義一個pojo類，實作Cloneable介面，重寫父類clone方法
淺拷貝

public class BallTeam implements Cloneable, Serializable {

    private static final long serialVersionUID = -3998490931149880710L;

    private String name;
    private int championNum;
    private Player player;

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

屬性Player：

public class Player implements Cloneable {

    private String playerName;
    private int playerAge;

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
 }

撰寫測驗方法：

private static void copyDepth() throws CloneNotSupportedException {
        BallTeam ballTeamNo = new BallTeam("Laker", 17);
        Player playerNo = new Player("James", 36);
        ballTeamNo.setPlayer(playerNo);

        BallTeam ballTeamClone = (BallTeam) ballTeamNo.clone();
        ballTeamNo.setname("Heat");
        ballTeamNo.setChampionNum(18);
        ballTeamNo.getPlayer().setPlayerName("Davis");

        System.out.println("noClone playerName : " + ballTeamNo.getPlayer().getPlayerName());
        System.out.println("clone playerName   : " + ballTeamClone.getPlayer().getPlayerName());

        System.out.println("noClone name       : "+ballTeamNo.getname());
        System.out.println("clone name         : "+ballTeamClone.getname());

        System.out.println("noClone championNum: "+ballTeamNo.getChampionNum());
        System.out.println("clone championNum  : "+ballTeamClone.getChampionNum());

        System.out.println("noClone playerObj  : "+ballTeamNo.getPlayer());
        System.out.println("clone playerObj    : "+ballTeamClone.getPlayer());
    }

列印結果：

基本資料型別：clone完成后championNum不會跟源變數改變而變化，所以他是獨立的，
String型別：name沒發生變化，也是獨立的，但是兩個name指向字串常量池中不同的常量；
參考型別：在堆疊中參考的是堆記憶體的同一物件Player，指向相同的地址，所以Player playerName發生改變，也就是參考的物件屬性發生改變，

深拷貝
所有參考型別變數除了String，都要實作Cloneable介面（陣列可以直接呼叫clone方法），重寫clone方法，并且各自呼叫父類的clone方法，重新賦值，
修改BallTeam類中重寫的clone方法：

 @Override
    protected Object clone() throws CloneNotSupportedException {
        BallTeam ballTeam = (BallTeam) super.clone();
        ballTeam.setPlayer((Player) player.clone());
        return ballTeam;
    }

執行結果：

很明顯參考型別變數經過clone，并且指向了不同地址，源變數不受影響，
類似于java方法傳參：
基本資料型別 是在堆疊中復制一份，然后在方法體中執行，復制的是變數名和值，方法體中變數改變不會影響源變數；
參考資料型別 復制的是變數名和參考地址，地址指向堆記憶體的物件，物件變了，源變數也會變；
String型別 被final修飾的不可變物件，重新賦值時，會在常量池中找存在的字串，如果有，直接取地址，如果沒有，重新new一個，并且將地址賦值給堆疊中的變數，源變數不改變，

Serializable

序列化的目的：

1. 存盤
2. 網路傳輸

序列化定義：
將記憶體中的物件轉化成流的形式并持久化磁盤中；
反序列化定義
以流的形式恢復成物件，

如果一個類實作了Serializable介面，就是通知jvm你要幫我序列化，并且會默認生成一個serialVersionUID，反序列化時jvm會自動檢測檔案中的serialVersionUID，判斷它是否與當前類中的serialVersionUID一致，如果不一致，會導致InvalidClassException例外，
寫一個序列化反序列化的方法：

private static void serializerTrain() throws IOException, ClassNotFoundException {
        List<BallTeam> ballTeams = new ArrayList<>();
        ballTeams.add(new BallTeam("Laker",17));
        ballTeams.add(new BallTeam("Celtics",17));
        ballTeams.add(new BallTeam("Bulls",6));
        ballTeams.add(new BallTeam("Warriors",6));

        FileOutputStream fos = new FileOutputStream("C:\\basic_code\\it\\october\\src\\com\\practice\\collection\\obj.txt");
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(ballTeams);
        oos.flush();
        oos.close();


        FileInputStream fis = new FileInputStream("C:\\basic_code\\it\\october\\src\\com\\practice\\collection\\obj.txt");
        ObjectInputStream ois = new ObjectInputStream(fis);
        List<BallTeam> ballTeamList = (List<BallTeam>) ois.readObject();
        ois.close();
    }

如果BallTeam不實作Serializable這個介面，反序列化會報錯，
執行：

AbstractList

繼承這個抽象類說明就擁有增、刪、查、改的功能，

List

這里大家都有疑問，你說你都繼承了AbstractList了，為什么還要實作List介面？

I’ve asked Josh Bloch, and he informs me that it was a mistake. He used to think, long ago, that there was some value in it, but he since “saw the light”. Clearly JDK maintainers haven’t considered this to be worth backing out later.

意思就是：我問過Josh Bloch，他告訴我這就是個錯誤，并且以后會取消，
當然這不是我問的，

ArrayList屬性

	//序列化版本號，類檔案標簽，類的內容改變會導致反序列化失敗，
 private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 未指定實體化容量的默認陣列長度
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 初始化ArrayList指定長度（下面要考）指向這個陣列
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 與EMPTY_ELEMENTDATA 區分開來，
     * 初始化ArrayList不指定長度指向此陣列，默認長度為10，并且會按照相應的擴容因子擴容，
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 真正存放元素的地方（陣列，下面要考）
     */
    transient Object[] elementData; 

    /**
     * 真正存放元素個數
     */
    private int size;

ArrayList構造

	 /**
     *如果指定長度并且長度大于0，就new一個指定長度的陣列指向elementData，
     *如果等于0，EMPTY_ELEMENTDATA空陣列屬性指向elementData 
     */
    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);
        }
    }

    /**
     *無參構造，初始化一個空陣列，并在第一次添加的時候擴大長度為10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 有參構造添加一個集合物件，并將集合物件轉換成陣列賦值給elementData 
     * 判斷長度是否為0，如果為0，相當于new ArrayList(0)，
     * 如果不為0，判斷該陣列是否是Object[].class型別的，
     * 如果不是就重新copy到new的新陣列中，copy長度為原陣列長度和size中的最小值
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // ArrayList屬性EMPTY_ELEMENTDATA空陣列指向并賦值給elementData 
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

添加元素

 	/**
     * 確認陣列容量，判斷是不是需要擴容，運算元modCount++，元素個數size++
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
	private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
	/**
	 *在構造方法中初始化未指定長度會有這一步操作
	 *elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以這里判斷成功，如果size+1 < 10 這里回傳的長度就是10，
	 *如果指定了長度，在這里會直接回傳size+1
	 */
	 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    /**
     * 如果說size+1 > elementData.length ，也就是要添加的元素容量超過原來陣列容量,
     * 就需要擴容
     * 初始化不指定容器長度，會在第一次添加的時候擴容長度到10
     */
	private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

指定下標添加

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        ensureCapacityInternal(size + 1);  // 同上，確認陣列長度，需不需要擴容
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//將陣列此下標以及此下標往后的資料往后復制一格，是復制不是移動，將新的下標位置和后一個下標位置都是指向相同元素（下圖）
        elementData[index] = element;//將插入的元素賦值給該下標
        size++;
    }

擴容

    private void grow(int minCapacity) {
      
        int oldCapacity = elementData.length;//獲取陣列長度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//將陣列長度擴大1.5倍
        if (newCapacity - minCapacity < 0)//擴大1.5倍不夠，直接將所需容量賦值
        	//一般不指定初始化容量，陣列長度為0，擴大1.5倍還是0，會走這一步
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)//如果擴容1.5倍太大，直接用Integer.MAX_VALUE
        	//(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE
            newCapacity = hugeCapacity(minCapacity);
        //將原陣列elementData的資料復制到大小為newCapacity的新陣列（new出來的）當中，并且重新賦值給elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

移除元素

 	public E remove(int index) {
        rangeCheck(index);//檢查索引是否合理

        modCount++;//運算元標記
        E oldValue = elementData(index);//獲取具體元素

        int numMoved = size - index - 1;
        if (numMoved > 0)
        //這里主要判斷移除的元素下標是不是最后一個，如果是，直接將下標元素置為null，
        //如果不是最后一個，該下標后邊的所有元素往前復制一格，也是將最后一位置空
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; //無參考的元素會被GC回收
        return oldValue;
    }
    //遍歷下標所有元素，對元素是否為空做了判斷，如果該下標元素為null也會被移除，主要目的還是找到想要移除元素o的下標，知道下標同上remove(int index)，只不過又另寫了一個方法fastRemove(int index)，洗掉下標為index的元素
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    //約等于remove(int index),只不過這里不用做索引是否合法校驗，不用回傳具體元素
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; 
    }

迭代器

 private class Itr implements Iterator<E> {
        int cursor;       // 代表下一個要訪問的元素下標
        int lastRet = -1; // 代表上一個要訪問的元素下標
        int expectedModCount = modCount;//是跟ArrayList 運算元modCount保持一致的一個期望值

        Itr() {}

		//如果下一元素的下標等于元素個數就證明已經迭代結束了，回傳
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();//檢查expectedModCount和modCount是否相等，如果迭代中間，洗掉或添加過元素，會拋例外ConcurrentModificationException
            int i = cursor;
            if (i >= size) //針對cursor做出判斷，是不是一次性迭代數代超過元素個數
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;//cursor 初始化為0，lastRet初始化為-1，第一次迭代后為0，每一次迭代cursor 和lastRet 都會+1，
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)//如果不進行迭代，直接洗掉元素會報錯，因為初始化lastRet =-1
         		
                throw new IllegalStateException();
             //只有呼叫next方法，lastRet 被賦值后才會執行，
            checkForComodification();//校驗同上

            try {
                ArrayList.this.remove(lastRet);//這里的modCount會+1
                cursor = lastRet;//元素洗掉后，將lastRet賦值給cursor 
                lastRet = -1;//lastRet重新置為初始值，
                //也就是說呼叫next方法后，只能呼叫一次remove方法，否則就會報錯
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

fail-fast機制

定義：
是java集合(Collection)中的一種錯誤檢測機制，當在迭代集合的程序中該集合在結構上發生改變的時候，就有可能會發生fail-fast，即拋出 ConcurrentModificationException例外，
發生原因：
在單執行緒或多執行緒環境下，迭代程序中元素被添加或洗掉，
應用場景：
ArrayList、HashMap中都有一個屬性叫modCount，每次對集合的修改（增加、洗掉）這個值都會加1，在迭代遍歷前記錄這個值到expectedModCount中，遍歷中檢查兩者是否一致，如果出現不一致就說明modCount發生修改，則拋出ConcurrentModificationException例外，
描述：
并不是所有集合都有這種機制，ConcurrentHashMap、CopyOnWriterArrayList等都是沒有，
底層陣列結構的集合基于下標存取(set、get)效率比較高，時間復雜度為O(1)，像查找（index of、contains、lastIndexOf…）、插入（add）、洗掉（remove）時間復雜度為O(n)

總結

并不是ArrayList一定比LinkedList 增刪慢，主要原因是ArrayList在不指定初始化長度的情況下會頻繁的grow、arraycopy，效率很低，

private static void arrayAndLinkedCompare() {
        int len = 10000000;
        ArrayList<Integer> arrayList1 = new ArrayList<>(len);
        LinkedList<Integer> linkedList = new LinkedList<>();

        long start1 = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            arrayList1.add(i);
        }
        long end1 = System.currentTimeMillis();
        System.out.println("arrayList1 need time: " + (end1 - start1));

        long start2 = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            linkedList.add(i);
        }
        long end2 = System.currentTimeMillis();
        System.out.println("linkedList need time: " + (end2 - start2));
    }

執行結果：
arrayList1 need time: 4806
linkedList need time: 13237
在故事結尾，阿涵成功的挽救的他的愛情，但是他每次才能夠一個arrayList1 need time的時間，她女友說了，“阿涵，我需要一個linkedList need time，你再學習一下LinkedList 好嗎？”