細談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
序列化的目的：
- 存檔
- 網路傳輸
序列化定義：
將記憶體中的物件轉化成流的形式並持久化磁碟中；
反序列化定義
以流的形式恢復成物件。
如果一個類實現了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 好嗎？」