• 本文是根據源碼進行學習的,如果我有什么理解不對的地方請多指正,謝謝您

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

ArrayList

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

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

初始化

• ArrayList提供了三種構造方法,如下

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

• 空參 : 我們從第一個ArrayList的空參的構造方法介紹,下面是源碼的實現

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

• 怎么理解之前的代碼注釋當第一個元素被添加時,任何一個空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴展為DEFAULT_CAPACITY呢?ArrayList為空并且兩個屬性值相等的時候,說明是調用了無參構造,在構造執(zhí)行完的時候,并沒有被構造為默認大小,而是當第一個元素添加時候,判斷的條件成立即兩屬性值相等,才會進行擴展為默認大小

• 所以說當我們構建空參對象的時候,初始值數組長度是為0的,并沒有直接擴充為長度為10的數組,代碼驗證

  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//而當我們以0為初始化長度參數創(chuàng)建ArrayList的時候,其實就是告訴他我一個都不存,所以他就創(chuàng)建了一個0長度的數組,而當我們添加數據的時候,就會自動擴容一個//驗證 : 可以將初始化改成這樣        ArrayList<String> arrayList = new ArrayList<>(0);//然后輸出為 0 1//所以這也就是為什么要區(qū)分DEFAULTCAPACITY_EMPTY_ELEMENTDATA  與 EMPTY_ELEMENTDATA

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

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

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

  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其實已經想好了為我們的空集合做一個緩存,而當我們向空集合中添加數據的時候,elementData就會指向其他的對象,這個是add方法的源碼范圍,所以一會再說,到這第一個空參的構造方法已經介紹的差不多了,下面是有int類型參數的構造方法的源碼實現

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

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

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

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

add

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

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

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

• 然后當我debug step over到結束代碼的時候,程序跳到這這樣一個代碼

  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");
  }//還有很多...

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

• 經過后面再次實驗, 除了首次使用ArrayList的add方法會加載一些東西,當我們再次new出ArrayList的時候,首次使用add方法就不會再家在任何東西了,如下的測試代碼

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

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

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

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

• 這個方法中用到的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 ,即擴容1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);    //擴容后如果還比最小的容量小或者相等的話
      if (newCapacity - minCapacity <= 0) {      //判斷是否是初始化的情況
          if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)        //是的話就直接返回默認容量10,從這就可以看出來才剛開始初始化大小
              return Math.max(DEFAULT_CAPACITY, minCapacity);        if (minCapacity < 0) // overflow錯誤,最小值不可能是負數
              throw new OutOfMemoryError();        //如果不是初始化也不是參數錯誤,那么就返回最小的容量
          return minCapacity;
      }    //到這表示擴容后的容量比最小容量要大
      //是否達到了最大長度,如果沒到達就返回擴容后的長度,否則就調用hugeCapacity
      return (newCapacity - MAX_ARRAY_SIZE <= 0)
          ? newCapacity
          : hugeCapacity(minCapacity);
  }private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow錯誤
          throw new OutOfMemoryError();    //如果達到了規(guī)定的最大數組長度,那么就擴容到整數的最大長度,否則就是當前默認的數組最大長度
      return (minCapacity > MAX_ARRAY_SIZE)
          ? Integer.MAX_VALUE
          : MAX_ARRAY_SIZE;
  }private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 還有一個指定位置的add方法,下面是源碼實現

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

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

addAll

• 源碼實現

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

Get

• 源碼實現

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

• 很簡單就不說了

remove

• 源碼實現按照索引刪除

  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;    //去掉一個元素后的長度如果大于指定刪除的索引的位置
      if ((newSize = size - 1) > i)    //把刪除元素后面的元素往前挪一位
          System.arraycopy(es, i + 1, es, i, newSize - i);    //避免內存泄露
      es[size = newSize] = null;
  }

• 源碼實現按照對象刪除

  public boolean remove(Object o) {    final Object[] es = elementData;    final int size = this.size;    int i = 0;  //元素首次出現位置記錄
      //尋找元素的邏輯
      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;
      }    //找到了就按照下標刪除
      fastRemove(e  s, i);    return true;
  }

indexOf

• 源碼實現

  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) {              //尋找到首個想等元素的時候返回索引
                  return i;
              }
          }
      } else {        for (int i = start; i < end; i++) {            if (o.equals(es[i])) {              //尋找到首個想等元素的時候返回索引
                  return i;
              }
          }
      }    //未找到返回-1
      return -1;
  }

• 這個實現比較簡單,并且ArrayList的一些*indexOf*類似的方法的大致思路都是如此的

writeObject

• 這是序列化的方法

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

readObject

• 這是反序列化的方法

  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {    // 讀取大小和其他的內容
      s.defaultReadObject();    //讀取容量
      s.readInt();    //如果讀取到size>0
      if (size > 0) {        // 與clone()一樣,根據大小而非容量分配數組
          SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);        //創(chuàng)建存儲數組
          Object[] elements = new Object[size];        //依次將數據讀出來并賦值
          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);
      }
  }

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

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

LinkedList

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

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

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

    //元素個數
    transient int size = 0;  //頭節(jié)點
    transient Node<E> first;  //尾節(jié)點
    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實現是一個雙鏈表,我們接下來看看他的初始化方法的實現

  public LinkedList() {
  }

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

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

• 那么這個有參的構造方法其實主要邏輯是addAll方法,我暫時先不說這個方法,那么我們先來看看其他的核心實現方法

add

• 源碼如下

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

• 還有一種是根據index位置插入的

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

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

addAll

• 這也是構造中調用的方法,我們來看一下實現

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

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

remove

• remove()

  public E remove() {    return removeFirst();
  }//可以看到默認從頭開始刪除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;    //取出頭元素的下一個元素的引用
      final Node<E> next = f.next;    //將頭元素的屬性值置空
      f.item = null;
      f.next = null; // help GC
      //然后將first指針指向下一個元素
      first = next;    //如果存在就只有一個元素的情況
      if (next == null)    //first和last都是null
          last = null;    else
      //否則就將原來頭節(jié)點的下一個節(jié)點的前引用取消,因為不存在了,自己已經變成了頭結點
          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;
  }  
  //整體邏輯就是:已經獲得了一個node,那么node的前后引用關系就找到了,然后剩下的就是改引用關系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) {      //頭指針,指向下一個元素
          first = next;
      } else {        //那么前引用就不是空的
          //就將此元素的前元素的后指針指向此元素的后一個元素
          prev.next = next;        //此節(jié)點的前置引用可以取消了
          x.prev = null;
      }    //如果后置引用為空
      if (next == null) {      //代表是尾節(jié)點,尾指針,指向前一個
          last = prev;
      } else {      //代表不是尾節(jié)點,就將次元素的后一個元素的前引用指向次元素的前一個元素
          next.prev = prev;        //次元素的后置引用可以取消了
          x.next = null;
      }    //到這x節(jié)點已經完全脫離鏈表,置空
      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); //方法實現上面已經寫出了}

• removeLast()

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

• remove(int)

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

• removeFirstOccurrence&removeLastOccurrence

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

Get

• getFirst() & getLast(),實現比較簡單就不注釋了

  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),實現比較簡單就不注釋了

  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é)點
      Node<E> x = node(index);    //保存作為返回
      E oldVal = x.item;    //替換
      x.item = element;    return oldVal;
  }

隊列操作

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

writeObject&readObject

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

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