• 本文是根據(jù)源碼進(jìn)行學(xué)習(xí)的,如果我有什么理解不對的地方請多指正,謝謝您

• 上面基本就是List集合類的類圖關(guān)系了,圖中省略掉了比如Cloneable等標(biāo)記接口,那么List分別具體的主要實(shí)現(xiàn)類有:ArrayList,Vector,LinkedList,Stack,那么這篇文章會對這四個(gè)實(shí)現(xiàn)類進(jìn)行介紹(由于篇幅原因,本文只說到了ArrayList和LinkedList)

ArrayList

• 這是最常用的List的實(shí)現(xiàn)類,那么這個(gè)類的存儲是由數(shù)組實(shí)現(xiàn)的,如果超過數(shù)組規(guī)定閥值,那么就會進(jìn)行自動擴(kuò)容,自動擴(kuò)容其實(shí)就是將數(shù)組數(shù)據(jù)復(fù)制到一個(gè)新的更大的數(shù)組中以達(dá)到擴(kuò)容的目的,我們來看一下ArrayList的部分屬性源碼

  //默認(rèn)容量,將在添加第一個(gè)元素時(shí)擴(kuò)展為 DEFAULT_CAPACITYprivate static final int DEFAULT_CAPACITY = 10;//共享空數(shù)組實(shí)例private static final Object[] EMPTY_ELEMENTDATA = {};//這是保存數(shù)據(jù)的數(shù)組,非私有以簡化嵌套類訪問//arraylist 的容量是此array數(shù)組的長度//當(dāng)?shù)谝粋€(gè)元素被添加時(shí),當(dāng)任何一個(gè)空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴(kuò)展為DEFAULT_CAPACITYtransient Object[] elementData;//共享空數(shù)組實(shí)例，用于默認(rèn)大小的空實(shí)例//將其與 EMPTY_ELEMENTDATA 區(qū)分開來,以了解添加第一個(gè)元素時(shí)要增加多少private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};private int size;
  ...

初始化

• ArrayList提供了三種構(gòu)造方法,如下

  public ArrayList() {...}public ArrayList(int initialCapacity) {...}public ArrayList(Collection<? extends E> c) {...}

• 空參 : 我們從第一個(gè)ArrayList的空參的構(gòu)造方法介紹,下面是源碼的實(shí)現(xiàn)

  public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

• 怎么理解之前的代碼注釋當(dāng)?shù)谝粋€(gè)元素被添加時(shí),任何一個(gè)空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴(kuò)展為DEFAULT_CAPACITY呢?ArrayList為空并且兩個(gè)屬性值相等的時(shí)候,說明是調(diào)用了無參構(gòu)造,在構(gòu)造執(zhí)行完的時(shí)候,并沒有被構(gòu)造為默認(rèn)大小,而是當(dāng)?shù)谝粋€(gè)元素添加時(shí)候,判斷的條件成立即兩屬性值相等,才會進(jìn)行擴(kuò)展為默認(rèn)大小

• 所以說當(dāng)我們構(gòu)建空參對象的時(shí)候,初始值數(shù)組長度是為0的,并沒有直接擴(kuò)充為長度為10的數(shù)組,代碼驗(yàn)證

  public static void main(String[] args) throws Exception {
      ArrayList<String> arrayList = new ArrayList<>();
      getSize(arrayList);
      arrayList.add("x");
      getSize(arrayList);
  }private static void getSize(ArrayList<String> arrayList) throws Exception {
      Field elementData = arrayList.getClass().getDeclaredField("elementData");
      elementData.setAccessible(true);
      Object[] o = (Object[]) elementData.get(arrayList);
      System.out.println(o.length);
  }//0 10//而當(dāng)我們以0為初始化長度參數(shù)創(chuàng)建ArrayList的時(shí)候,其實(shí)就是告訴他我一個(gè)都不存,所以他就創(chuàng)建了一個(gè)0長度的數(shù)組,而當(dāng)我們添加數(shù)據(jù)的時(shí)候,就會自動擴(kuò)容一個(gè)//驗(yàn)證 : 可以將初始化改成這樣        ArrayList<String> arrayList = new ArrayList<>(0);//然后輸出為 0 1//所以這也就是為什么要區(qū)分DEFAULTCAPACITY_EMPTY_ELEMENTDATA  與 EMPTY_ELEMENTDATA

• 從中我們可以看到,只是初始化空參的ArrayList的話,那么只是將一個(gè)空數(shù)組賦值給elementData屬性,那么EMPTY_ELEMENTDATA也是空數(shù)組對象,他是用來干啥的呢?他只是用作是構(gòu)造有參空ArrayLIst的時(shí)候=0.而DEFAULTCAPACITY_EMPTY_ELEMENTDATA才是我們構(gòu)造空參ArrayList時(shí)候使用的對象,即這樣的,從下面一個(gè)分析另一個(gè)構(gòu)造的時(shí)候就能看出來

  //使用EMPTY_ELEMENTDATAList<String> arrayList = new ArrayList<>(0);//使用DEFAULTCAPACITY_EMPTY_ELEMENTDATAList<String> arrayList = new ArrayList<>();

• 我們還注意到DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA都是以private static final修飾,所以這兩個(gè)空數(shù)組是屬于類的,僅存在一份,說這個(gè)的意思就是,當(dāng)你創(chuàng)建兩個(gè)容量為0的ArrayList的時(shí)候,都會指向一個(gè)堆內(nèi)存中的對象,我們可以嘗試一下

  public static void main(String[] args) throws Exception {
      ArrayList<String> list1 = new ArrayList<>();
      Field elementData1 = list1.getClass().getDeclaredField("elementData");
      elementData1.setAccessible(true);
      Object o1 = elementData1.get(list1);
      ArrayList<String> list2 = new ArrayList<>();
      Field elementData2 = list2.getClass().getDeclaredField("elementData");
      elementData2.setAccessible(true);
      Object o2 = elementData1.get(list2);
      System.out.println(o1 == o2);
  } //true

• 所以ArrayList其實(shí)已經(jīng)想好了為我們的空集合做一個(gè)緩存,而當(dāng)我們向空集合中添加數(shù)據(jù)的時(shí)候,elementData就會指向其他的對象,這個(gè)是add方法的源碼范圍,所以一會再說,到這第一個(gè)空參的構(gòu)造方法已經(jīng)介紹的差不多了,下面是有int類型參數(shù)的構(gòu)造方法的源碼實(shí)現(xiàn)

  public ArrayList(int initialCapacity) {  //不為0,按照指定長度創(chuàng)建數(shù)組
      if (initialCapacity > 0) {        this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {      //為0就直接指向創(chuàng)建好的數(shù)組
          this.elementData = EMPTY_ELEMENTDATA;
      } else {      //參數(shù)不合法
          throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
      }
  }

• 不用細(xì)說,這個(gè)是很容易的,也可以看出來為什么ArrayList要設(shè)計(jì)兩個(gè)空數(shù)組以備使用,這個(gè)構(gòu)造沒什么可說的,那么下面就是以集合為參數(shù)的創(chuàng)建方式的源碼

  //將參數(shù)轉(zhuǎn)換為ArrayListpublic ArrayList(Collection<? extends E> c) {  //因?yàn)镃ollection中就定義了toArray方法,所以他的實(shí)現(xiàn)類就都會實(shí)現(xiàn)自己的toArray,所以可以直接調(diào)用返回?cái)?shù)組而不會出錯(cuò)
      elementData = c.toArray();    //如果返回的數(shù)組的長度不是空的數(shù)組的話
      if ((size = elementData.length) != 0) {      //防范c.ToArray錯(cuò)誤不返回Object[]
          if (elementData.getClass() != Object[].class)        //那么就將elementData中的元素都轉(zhuǎn)換為Object類型
              elementData = Arrays.copyOf(elementData, size, Object[].class);
      } else {        //到這就是空數(shù)組,所以直接引用創(chuàng)建好的空數(shù)組即可,還能節(jié)省空間
          this.elementData = EMPTY_ELEMENTDATA;
      }
  }

• 到這ArrayList的創(chuàng)建方式大概的就過了一邊,那么下面的ArrayList的實(shí)現(xiàn)方法,我就只挑幾個(gè)核心方法來看一下源碼

add

• 首當(dāng)其沖的就是add,我們使用一下ArrayList來add元素,然后我們進(jìn)行代碼走讀,那么我們看一下源碼

  //使用ArrayList<String> arrayList = new ArrayList<>();
  arrayList.add("A");//源碼開始public boolean add(E e) {
      modCount++;  //代表操作ArrayList的次數(shù),有關(guān)于fast-fail機(jī)制,之后再說
      //參數(shù)值:并不是A參數(shù)是一個(gè)URL, 數(shù)組對象 , 2
      add(e, elementData, size); //調(diào)用類中方法
      return true; //返回結(jié)果} // 結(jié)束代碼

• 上面可以說是很簡單了,但是在debug的時(shí)候我發(fā)現(xiàn)存儲元素的elementData數(shù)組中其實(shí)已經(jīng)有東西了,如下圖

• 然后當(dāng)我debug step over到結(jié)束代碼的時(shí)候,程序跳到這這樣一個(gè)代碼

  public synchronized void addURL(URL url) {    if (closed || url == null)        return;    synchronized (unopenedUrls) {        if (! path.contains(url)) {
              unopenedUrls.addLast(url);
              path.add(url);
          }
      }
  }//再跳public InternalError(String message) {    super(message);
  }//還跳static {
      System.loadLibrary("instrument");
  }//還有很多...

• 上面的一些代碼其實(shí)不用知道其意思,但是可以告訴我們的是,ArrayList中的elementData不單純是存儲我們需要存儲的元素的,而是在首次add的時(shí)候會借助elementData這個(gè)數(shù)組去加載一些文件或者其他東西,而在第二次add的時(shí)候就不需要這個(gè)步驟了,并且在首次加載完一些路徑后或者庫后,elementData就會將他們清除,以為已經(jīng)加載上了,然后這時(shí)候才會來存儲我們的元素,錄了一段小視頻,可以下載來看一下

• 經(jīng)過后面再次實(shí)驗(yàn), 除了首次使用ArrayList的add方法會加載一些東西,當(dāng)我們再次new出ArrayList的時(shí)候,首次使用add方法就不會再家在任何東西了,如下的測試代碼

  List<String> list = new ArrayList<>();
  list.add("X");
  List<String> list2 = new ArrayList<>();
  list2.add("X");

• 其中在我debug時(shí)候會看到很多getLoader`loders一些方法或者屬性,那么在這感覺是首次使用ArrayList的類加載機(jī)制在起作用,我在社區(qū)提問題了,所以大家可以看一下,聯(lián)想到類加載機(jī)制非常感謝回復(fù)我的1382148494135822`大哥, 問答頁 : 關(guān)于ArrayList的問題,請大佬進(jìn)來看看

• 回到add方法上來,我們發(fā)現(xiàn)它會調(diào)用類中的另一個(gè)add方法.源碼如下

  private void add(E e, Object[] elementData, int s) {  //如果滿了就擴(kuò)容
      if (s == elementData.length)
          elementData = grow();    //然后將要存的元素存入到數(shù)組指定位置
      elementData[s] = e;    //加一
      size = s + 1;
  }

• 這個(gè)方法中用到的grow方法源碼如下

  private Object[] grow() {    return grow(size + 1);
  }private Object[] grow(int minCapacity) {    return elementData = Arrays.copyOf(elementData,
                                         newCapacity(minCapacity));
  }//返回至少與給定最小容量相同的容量private int newCapacity(int minCapacity) {    int oldCapacity = elementData.length;    //10+(10>>1)=15 ,即擴(kuò)容1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);    //擴(kuò)容后如果還比最小的容量小或者相等的話
      if (newCapacity - minCapacity <= 0) {      //判斷是否是初始化的情況
          if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)        //是的話就直接返回默認(rèn)容量10,從這就可以看出來才剛開始初始化大小
              return Math.max(DEFAULT_CAPACITY, minCapacity);        if (minCapacity < 0) // overflow錯(cuò)誤,最小值不可能是負(fù)數(shù)
              throw new OutOfMemoryError();        //如果不是初始化也不是參數(shù)錯(cuò)誤,那么就返回最小的容量
          return minCapacity;
      }    //到這表示擴(kuò)容后的容量比最小容量要大
      //是否達(dá)到了最大長度,如果沒到達(dá)就返回?cái)U(kuò)容后的長度,否則就調(diào)用hugeCapacity
      return (newCapacity - MAX_ARRAY_SIZE <= 0)
          ? newCapacity
          : hugeCapacity(minCapacity);
  }private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow錯(cuò)誤
          throw new OutOfMemoryError();    //如果達(dá)到了規(guī)定的最大數(shù)組長度,那么就擴(kuò)容到整數(shù)的最大長度,否則就是當(dāng)前默認(rèn)的數(shù)組最大長度
      return (minCapacity > MAX_ARRAY_SIZE)
          ? Integer.MAX_VALUE
          : MAX_ARRAY_SIZE;
  }private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 還有一個(gè)指定位置的add方法,下面是源碼實(shí)現(xiàn)

  public void add(int index, E element) {    //檢查是否數(shù)組越界
      rangeCheckForAdd(index);
      modCount++;    final int s; //臨時(shí)保存size
      Object[] elementData; //臨時(shí)保存elementData
      if ((s = size) == (elementData = this.elementData).length)
          elementData = grow(); //如果長度等于size代表要擴(kuò)容了
      //核心方法System.arraycopy,他會將你要操作的index地方的位置空出了
      System.arraycopy(elementData, index,
                       elementData, index + 1,
                       s - index);    //然后index空出來的位置賦值               
      elementData[index] = element;    //加一
      size = s + 1;
  }

• 好了ArrayList的add方法已經(jīng)介紹完了,如果有不對的地方請指正

addAll

• 源碼實(shí)現(xiàn)

  public boolean addAll(Collection<? extends E> c) {  //轉(zhuǎn)換數(shù)組
      Object[] a = c.toArray();
      modCount++;    //獲取傳入集合的長度
      int numNew = a.length;    //是空集合的話直接返回
      if (numNew == 0)        return false;
      Object[] elementData;    final int s;    //如果傳入集合的長度大于elementData中空余的位置個(gè)數(shù)就增長
      if (numNew > (elementData = this.elementData).length - (s = size))
          elementData = grow(s + numNew);    //增長完了就將傳入的數(shù)據(jù)copy進(jìn)去
      System.arraycopy(a, 0, elementData, s, numNew);    //元素個(gè)數(shù)修改
      size = s + numNew;    //返回成功
      return true;
  }

Get

• 源碼實(shí)現(xiàn)

  public E get(int index) {    //檢查index
      Objects.checkIndex(index, size);    //然后調(diào)用方法
      return elementData(index);
  }E elementData(int index) {  //直接下標(biāo)取元素
      return (E) elementData[index];
  }

• 很簡單就不說了

remove

• 源碼實(shí)現(xiàn)按照索引刪除

  public E remove(int index) {    //檢查index
      Objects.checkIndex(index, size);    final Object[] es = elementData;    //用于返回值
      E oldValue = (E) es[index];
  
      fastRemove(es, index);    return oldValue;
  }private void fastRemove(Object[] es, int i) {
      modCount++;    final int newSize;    //去掉一個(gè)元素后的長度如果大于指定刪除的索引的位置
      if ((newSize = size - 1) > i)    //把刪除元素后面的元素往前挪一位
          System.arraycopy(es, i + 1, es, i, newSize - i);    //避免內(nèi)存泄露
      es[size = newSize] = null;
  }

• 源碼實(shí)現(xiàn)按照對象刪除

  public boolean remove(Object o) {    final Object[] es = elementData;    final int size = this.size;    int i = 0;  //元素首次出現(xiàn)位置記錄
      //尋找元素的邏輯
      found: {        if (o == null) {            for (; i < size; i++)                if (es[i] == null)                    break found;
          } else {            for (; i < size; i++)                if (o.equals(es[i]))                    break found;
          }        //到這代表沒找到.返回false
          return false;
      }    //找到了就按照下標(biāo)刪除
      fastRemove(e  s, i);    return true;
  }

indexOf

• 源碼實(shí)現(xiàn)

  public int indexOf(Object o) {    return indexOfRange(o, 0, size);
  }int indexOfRange(Object o, int start, int end) {
      Object[] es = elementData;    if (o == null) {        for (int i = start; i < end; i++) {            if (es[i] == null) {              //尋找到首個(gè)想等元素的時(shí)候返回索引
                  return i;
              }
          }
      } else {        for (int i = start; i < end; i++) {            if (o.equals(es[i])) {              //尋找到首個(gè)想等元素的時(shí)候返回索引
                  return i;
              }
          }
      }    //未找到返回-1
      return -1;
  }

• 這個(gè)實(shí)現(xiàn)比較簡單,并且ArrayList的一些*indexOf*類似的方法的大致思路都是如此的

writeObject

• 這是序列化的方法

  private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {    //將操作次數(shù)記錄
      int expectedModCount = modCount;    //將類中的no-static和no-transient屬性寫到流中
      s.defaultWriteObject();
      s.writeInt(size);    //依次寫出元素
      for (int i=0; i<size; i++) {
          s.writeObject(elementData[i]);
      }    //如果再次過程中數(shù)組中內(nèi)容遭到改變,序列化停止并且拋出異常
      if (modCount != expectedModCount) {        throw new ConcurrentModificationException();
      }
  }

readObject

• 這是反序列化的方法

  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {    // 讀取大小和其他的內(nèi)容
      s.defaultReadObject();    //讀取容量
      s.readInt();    //如果讀取到size>0
      if (size > 0) {        // 與clone()一樣,根據(jù)大小而非容量分配數(shù)組
          SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);        //創(chuàng)建存儲數(shù)組
          Object[] elements = new Object[size];        //依次將數(shù)據(jù)讀出來并賦值
          for (int i = 0; i < size; i++) {
              elements[i] = s.readObject();
          }        //然后賦值給本類的全局變量
          elementData = elements;
      } else if (size == 0) {      //size為0代表空集合,那么就直接使用常量替換
          elementData = EMPTY_ELEMENTDATA;
      } else {      //非法的,出異常
          throw new java.io.InvalidObjectException("Invalid size: " + size);
      }
  }

• 好了到這我自己認(rèn)為比較重要的方法源碼就都列出來的,所以將ArrayList的介紹就告一段落了,那么到這我就只有一個(gè)疑問就是關(guān)于elementData在首次add時(shí)加載jar或者路徑是做什么用的,如果您知道,請?jiān)u論在下面,非常謝謝您

• 總結(jié)一下ArrayList,我們在分析源碼的時(shí)候,除了在首次add時(shí)會添加路徑之類的信息會設(shè)計(jì)到其他類的同步加載方法,但是本類的方法并沒有涉及同步,所以ArrayList并不是線程安全的,并且他是懶加載的,首次默認(rèn)初始化并不會就初始化為初始化容量,而是在之后才會初始化為初始化容量,這個(gè)類的核心就是System.arraycopy方法,所以以后我們在操作數(shù)組移動的時(shí)候,我們也可以使用這個(gè)native方法使得程序更加的快速準(zhǔn)確,在add和get的時(shí)候是相當(dāng)迅速而直接的,就是將制定位置元素后移并在此位置上插入元素,所以ArrayList的增加和查詢是很迅速的,但是我們也需要注意,當(dāng)ArrayList的元素滿的時(shí)候他是創(chuàng)建新數(shù)組進(jìn)行copy的,所以當(dāng)ArrayList的元素相當(dāng)大的時(shí)候,這無疑是一個(gè)恐怖的事情,所以ArrayList并不適合存儲很多元素

LinkedList

• 可以先參考一下這篇關(guān)于鏈表的文章,如果你有了解一點(diǎn)就可以不用看了 : 鏈表

• 這是一個(gè)鏈表實(shí)現(xiàn)的List的實(shí)現(xiàn)類,對于ArrayList這個(gè)類要并不存在擴(kuò)容copy的問題,如果你了解一點(diǎn)鏈表內(nèi)容就會知道,增加元素在鏈表中無非就是改變引用的事情,所以它并沒有這樣的問題,好了讓我們直接上源碼吧

• 依舊先看一下他的成員屬性

    //元素個(gè)數(shù)
    transient int size = 0;  //頭節(jié)點(diǎn)
    transient Node<E> first;  //尾節(jié)點(diǎn)
    transient Node<E> last;

• transient代表不會被序列化,那么Node是啥東西,看一下源碼

  private static class Node<E> {
      E item;  //本元素值
      Node<E> next; //前元素指向
      Node<E> prev; //后元素指向
      Node(Node<E> prev, E element, Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;
      }
  }

• 從中可以LinkedList實(shí)現(xiàn)是一個(gè)雙鏈表,我們接下來看看他的初始化方法的實(shí)現(xiàn)

  public LinkedList() {
  }

• 空參構(gòu)造什么都沒做,接下來看其他的初始化方法

  public LinkedList(Collection<? extends E> c) {    this();
      addAll(c);
  }

• 那么這個(gè)有參的構(gòu)造方法其實(shí)主要邏輯是addAll方法,我暫時(shí)先不說這個(gè)方法,那么我們先來看看其他的核心實(shí)現(xiàn)方法

add

• 源碼如下

  public boolean add(E e) {
      linkLast(e);  //添加到鏈表最后面
      return true;
  }void linkLast(E e) {  //將最后一個(gè)元素引用保留
      final Node<E> l = last;    //創(chuàng)建一個(gè)新的元素根據(jù)傳入的add參數(shù),新的對象的前一個(gè)元素的引用
      //就是之前的最后一個(gè)元素
      final Node<E> newNode = new Node<>(l, e, null);    //將最后的元素指針指向新元素
      last = newNode;    //如果之前的尾元素是空的代表是空鏈表,
      if (l == null)    //即首尾都是此元素
          first = newNode;    else
      //就不是空鏈表,那么倒數(shù)第二個(gè)的元素的下一個(gè)元素就是新元素
          l.next = newNode;
      size++;
      modCount++;
  }

• 還有一種是根據(jù)index位置插入的

  public void add(int index, E element) {  //是否越界
      checkPositionIndex(index);    //如果index等于元素個(gè)數(shù)
      if (index == size)    //那么就添加到尾部
          linkLast(element);    else
      //否則就按位置添加
      //node方法,傳入index,返回指定元素索引處的（非空）節(jié)點(diǎn)
          linkBefore(element, node(index));
  }void linkBefore(E e, Node<E> succ) {    //已經(jīng)確保了succ不為空,在上面node方法中確保的
      //取出指定index索引上的元素的前一個(gè)元素引用
      final Node<E> pred = succ.prev;    //創(chuàng)建新的元素,新元素的前一個(gè)元素就是目前指定index上的元素的前一個(gè)元素
      //下一個(gè)元素是index上面的元素
      final Node<E> newNode = new Node<>(pred, e, succ);    //將指定索引位置的原元素的前指針指向新元素
      succ.prev = newNode;    //如果是在頭部添加,那么當(dāng)前元素的前一個(gè)元素肯定為空
      if (pred == null)    //然后新元素就成為了頭元素
          first = newNode;    else
      //否則就將index-1位置的元素的后指針指向新元素
          pred.next = newNode;
      size++;
      modCount++;
  }

• 如果你熟悉鏈表,那么上面的代碼就很簡單就能理解了,如果看不懂,可以自己畫一下圖,瞬間明白

addAll

• 這也是構(gòu)造中調(diào)用的方法,我們來看一下實(shí)現(xiàn)

  public boolean addAll(Collection<? extends E> c) {    return addAll(size, c);
  }public boolean addAll(int index, Collection<? extends E> c) {    //檢查位置是否越界
      checkPositionIndex(index);    //集合轉(zhuǎn)數(shù)組
      Object[] a = c.toArray();    //確定集合元素個(gè)數(shù)
      int numNew = a.length;    //如果是空集合返回
      if (numNew == 0)        return false;    //記錄前指向和當(dāng)前節(jié)點(diǎn)
      Node<E> pred, succ;    //如果相等代表在最后追加
      if (index == size) {      //在最后追加,就不需要當(dāng)前元素了,因?yàn)閘ast已經(jīng)指向了
          succ = null;        //添加集合的時(shí)候的,集合中首個(gè)被添加的元素的前一個(gè)節(jié)點(diǎn)就是當(dāng)前鏈表中的最后一個(gè)節(jié)點(diǎn)
          pred = last;
      } else {        //到這就代表不是在尾部追加,而是將元素追加到鏈表中間位置
          //node方法之前說過就是根據(jù)index來返回index位置上的節(jié)點(diǎn)
          //node返回節(jié)點(diǎn)后保存引用
          succ = node(index);        //記錄當(dāng)前index節(jié)點(diǎn)的前節(jié)點(diǎn)的引用
          pred = succ.prev;        //到這就記錄好了當(dāng)前節(jié)點(diǎn)和前節(jié)點(diǎn)的引用
      }    //開始循環(huán)創(chuàng)建集合中的元素的節(jié)點(diǎn)了,然后修改相關(guān)指向
      for (Object o : a) {        //將集合元素強(qiáng)轉(zhuǎn)一下,泛型約束不會classcast
          E e = (E) o;        //創(chuàng)建節(jié)點(diǎn),此節(jié)點(diǎn)的前一個(gè)元素指向已經(jīng)確定
          Node<E> newNode = new Node<>(pred, e, null);        //代表從頭開始添加
          if (pred == null)        //新節(jié)點(diǎn)就是first節(jié)點(diǎn)
              first = newNode;        else
          //新節(jié)點(diǎn)前指向是pred,perd.next指向新元素,所以到這形成了前元素和新元素的雙向鏈接
              pred.next = newNode;        //到這就連接好了舊節(jié)點(diǎn)和新節(jié)點(diǎn),需要移動pred指向,指向新節(jié)點(diǎn)
          //然后將新節(jié)點(diǎn)當(dāng)做舊節(jié)點(diǎn),然后在于新創(chuàng)建的節(jié)點(diǎn)做雙向鏈接
          pred = newNode;
      }    //到這就把鏈表從頭到集合所有元素都連接完成了,需要處理集合的尾節(jié)點(diǎn)和鏈表的原index節(jié)點(diǎn)的鏈接問題了
      //如果原來的尾index節(jié)點(diǎn)沒有
      if (succ == null) {      //那么last就指向集合的尾節(jié)點(diǎn)
          last = pred;
      } else {      //代表之前的鏈表有index節(jié)點(diǎn),那么就修改index節(jié)點(diǎn)和集合的尾節(jié)點(diǎn)的鏈接
          pred.next = succ;
          succ.prev = pred;
      }    //做一些計(jì)數(shù)操作
      size += numNew;
      modCount++;    return true;
  }

• 到這其實(shí)add方法基本就解析完了,那么順便前面的構(gòu)造也就沒有問題了,下面是其他方法的源代碼

remove

• remove()

  public E remove() {    return removeFirst();
  }//可以看到默認(rèn)從頭開始刪除public E removeFirst() {    final Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return unlinkFirst(f);
  }private E unlinkFirst(Node<E> f) {    // assert f == first && f != null;
      //取出頭元素屬性值
      final E element = f.item;    //取出頭元素的下一個(gè)元素的引用
      final Node<E> next = f.next;    //將頭元素的屬性值置空
      f.item = null;
      f.next = null; // help GC
      //然后將first指針指向下一個(gè)元素
      first = next;    //如果存在就只有一個(gè)元素的情況
      if (next == null)    //first和last都是null
          last = null;    else
      //否則就將原來頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的前引用取消,因?yàn)椴淮嬖诹?自己已經(jīng)變成了頭結(jié)點(diǎn)
          next.prev = null;
      size--;
      modCount++;    return element;
  }

• remove(Object)

  public boolean remove(Object o) {  //遍歷,邏輯比較簡單,就不一句代碼一句代碼的說了
      if (o == null) {        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {
                  unlink(x);                return true;
              }
          }
      } else {        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {
                  unlink(x);                return true;
              }
          }
      }    return false;
  }  
  //整體邏輯就是:已經(jīng)獲得了一個(gè)node,那么node的前后引用關(guān)系就找到了,然后剩下的就是改引用關(guān)系E unlink(Node<E> x) {    // assert x != null;
      //取出元素的所有屬性值
      final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    //如果前引用是null,就代表是頭元素
      if (prev == null) {      //頭指針,指向下一個(gè)元素
          first = next;
      } else {        //那么前引用就不是空的
          //就將此元素的前元素的后指針指向此元素的后一個(gè)元素
          prev.next = next;        //此節(jié)點(diǎn)的前置引用可以取消了
          x.prev = null;
      }    //如果后置引用為空
      if (next == null) {      //代表是尾節(jié)點(diǎn),尾指針,指向前一個(gè)
          last = prev;
      } else {      //代表不是尾節(jié)點(diǎn),就將次元素的后一個(gè)元素的前引用指向次元素的前一個(gè)元素
          next.prev = prev;        //次元素的后置引用可以取消了
          x.next = null;
      }    //到這x節(jié)點(diǎn)已經(jīng)完全脫離鏈表,置空
      x.item = null;
      size--;
      modCount++;    return element;
  }

• removeFirst()

  public E removeFirst() {    final Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return unlinkFirst(f); //方法實(shí)現(xiàn)上面已經(jīng)寫出了}

• removeLast()

  public E removeLast() {    final Node<E> l = last;    if (l == null)        throw new NoSuchElementException();    return unlinkLast(l); // 跟之前的unlinkFirst類似就不再詳細(xì)說了}

• remove(int)

  public E remove(int index) {
      checkElementIndex(index);    return unlink(node(index)); //實(shí)現(xiàn)有說明在前面}

• removeFirstOccurrence&removeLastOccurrence

  • 其源碼就不去實(shí)現(xiàn)了,這個(gè)方法的作用是在于:如果指定的刪除元素在鏈表中就刪除,(區(qū)別:刪除最開始出現(xiàn)的&刪除最后一個(gè)出現(xiàn)的),如果不存在鏈表不變

Get

• getFirst() & getLast(),實(shí)現(xiàn)比較簡單就不注釋了

  public E getFirst() {    final Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return f.item;
  }public E getLast() {    final Node<E> l = last;    if (l == null)        throw new NoSuchElementException();    return l.item;
  }

• get(int),實(shí)現(xiàn)比較簡單就不注釋了

  public E get(int index) {
      checkElementIndex(index);    return node(index).item;
  }

set

• set(int,E)

  public E set(int index, E element) {  //檢查索引
      checkElementIndex(index);    //利用node方法取出index上的節(jié)點(diǎn)
      Node<E> x = node(index);    //保存作為返回
      E oldVal = x.item;    //替換
      x.item = element;    return oldVal;
  }

隊(duì)列操作

• 對于LinkedList還支持隊(duì)列操作,其實(shí)現(xiàn)也是比較簡單的,都是依靠于之前介紹的add方法和remove方法(unlink),所以不打算貼出源碼了,所支持的操作有類似peek,poll,push,pop等等,只了列舉部分

writeObject&readObject

• 至于LinkedList的序列化機(jī)制也是類似ArrayList的序列化方式和步驟,都是先將類中no-static和no-transient屬性寫到流中,然后寫size,然后依次寫元素,反序列化即相同步驟即可

• 總結(jié):我們可以看到LinkedList是雙向鏈表的實(shí)現(xiàn),并沒有首尾相連,所以也不是環(huán)形鏈表,并且其中不存在初始化容量概念,并且不存在ArrayList中的容量限制常量,所以說這個(gè)類可以做到理論上的無限大,并且從中沒發(fā)現(xiàn)同步代碼塊,所以這個(gè)類也不是同步的,需要我們在使用的時(shí)候注意使用場景,對于其他的操作就是常規(guī)的鏈表操作