不多說国裳，直接上源碼

List接口:

JDK文檔中是這樣描述的

/**
 * An ordered collection (also known as a <i>sequence</i>).  The user of this
 * interface has precise control over where in the list each element is
 * inserted.  The user can access elements by their integer index (position in
 * the list), and search for elements in the list.<p>
 * Unlike sets, lists typically allow duplicate elements.  More formally,
 * lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt>
 * such that <tt>e1.equals(e2)</tt>, and they typically allow multiple
 * null elements if they allow null elements at all.  It is not inconceivable
 * that someone might wish to implement a list that prohibits duplicates, by
 * throwing runtime exceptions when the user attempts to insert them, but we
 * expect this usage to be rare.<p>
Note: While it is permissible for lists to contain themselves as elements,
 * extreme caution is advised: the <tt>equals</tt> and <tt>hashCode</tt>
 * methods are no longer well defined on such a list.
 */

• 我提取幾點比較重要的：
  • List是有序的
  • List可以通過index精確的控制elements
  • List是允許重復(fù)元素以及null（但是不同的實現(xiàn)可能有變化）
  • List允許將他自己作為element嚎莉，但是hashcode和equals不在有用（不要使用）
    關(guān)于接口中的方法不在詳細(xì)說幢踏，在具體實現(xiàn)中在談?wù)撓啦荩琇ist接口中提供了一個特殊的迭代器ListIterator惶洲，提供額外的元素替換恰起、添加惠赫、雙向訪問的方法赘娄，以及提供了一個用于獲取從指定位置開始迭代的迭代器的方法仆潮。

ArrayList

吐槽簡書，這段注釋不識別

  /**
   * Resizable-array implementation of the <tt>List</tt> interface.  Implements
   * all optional list operations, and permits all elements, including
   * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
   * this class provides methods to manipulate the size of the array that is
   * used internally to store the list.  (This class is roughly equivalent to
   * <tt>Vector</tt>, except that it is unsynchronized.)
   */

總結(jié)一下遣臼，文檔中描述的大概就是下面這些東西：

• 首先性置，ArrayList 是一個可變的集合類，它實現(xiàn)了List接口的所有方法揍堰，允許存在null（可以全是）鹏浅，提供了操作內(nèi)置數(shù)組大小的方法（大概相當(dāng)于vector嗅义，不過是非線程安全）
• size、isEmpty隐砸、get之碗、set、iterator季希、listIterator的操作時間是constant time褪那，意思就是說O（1），時間粗略的來說是一個常數(shù)式塌，比如add n個元素需要O（n）博敬，那add 1個就需要O（1），是一個線性的關(guān)系，而且常數(shù)因子對比LinkedList來說要低。
• ArrayList 是非線程安全的，你要用的話就用Collections.synchronizedList來包裝一下它，最好是new的時候访递，就像這樣 List list = Collections.synchronizedList(new ArrayList(...));
• 迭代器（Iterator和ListIterator是fail-fast機制的）： 在用迭代器遍歷一個集合對象時，如果遍歷過程中對集合對象的內(nèi)容進行了修改（增加盟萨、刪除圈纺、修改），則會拋出Concurrent Modification Exception默赂。整個集合框架中的集合類都是這樣的沛鸵，原理下面再說。但是不要認(rèn)為他可以保證并發(fā)時的安全
• ArrayList的基類和實現(xiàn)的接口
  • AbstractList：這玩意就不說了缆八，以最小化程度實現(xiàn)了List接口曲掰，是實現(xiàn)array以及l(fā)inked list應(yīng)該優(yōu)先使用的類，然后做了一些對不可修改集合和可修改集合的規(guī)定奈辰。
  • RandomAccess：RandomAccess 是一個標(biāo)記接口栏妖，用于標(biāo)明實現(xiàn)該接口的List支持快速隨機訪問，主要目的是使算法能夠在隨機和順序訪問的list中表現(xiàn)的更加高效奖恰。上一篇文章中吊趾，說過Collection中獲取不可修改的List和線程安全的List等等之類會判斷是否實現(xiàn)了這個接口，然后采用相應(yīng)的算法實現(xiàn)瑟啃。
  • Cloneable：Java 中 一個類要實現(xiàn)clone功能 必須實現(xiàn) Cloneable接口论泛，否則在調(diào)用 clone() 時會報 CloneNotSupportedException 異常。ArrayList#clone實現(xiàn)的是淺拷貝蛹屿，這里多說一點
    **數(shù)組拷貝System.arraycopy>Arrays.copyOf>clone>for（自己實現(xiàn)）都是淺拷貝 這是拷貝的效率屁奏，Arrays.copyOf內(nèi)部使用的是System.arraycopy實現(xiàn)，ArrayList中clone中使用的是Object.clone和Arrays.copyOf（進行元素填充）错负，網(wǎng)上很多錯誤的說法說是需要轉(zhuǎn)換類型坟瓢。勇边。。折联，這里貼一下源碼給你們看粒褒。

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

• ArrayList內(nèi)部數(shù)據(jù)結(jié)構(gòu)

    /**默認(rèn)容量大小
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**用于空實例的共享空數(shù)組實例（當(dāng)設(shè)置容量為0時或者使用collection來構(gòu)造時使用的數(shù)組實例）
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**默認(rèn)使用的數(shù)組實例
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**存儲ArrayList元素的數(shù)組緩沖區(qū)。ArrayList的容量等于這個數(shù)組緩沖區(qū)的長度崭庸。
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**數(shù)組元素的數(shù)量
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

總結(jié)一下：數(shù)組默認(rèn)容量為10怀浆，有兩個空數(shù)組的實例，一個數(shù)組緩沖區(qū)的引用怕享，會指向兩個空數(shù)組實例之一执赡，緩沖區(qū)的大小等于ArrayList的容量，以及數(shù)組元素的數(shù)量

• ArrayList數(shù)組擴容機制
  我們以默認(rèn)創(chuàng)建的ArrayList為例,

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

圖片.png

在list 初始化之后函筋，數(shù)組緩沖區(qū)的長度為0沙合，add一個元素之后，數(shù)組緩沖區(qū)的長度等于DEFAULT_CAPACITY =10跌帐，我們再來看一下首懈，繼續(xù)添加元素之后的擴容機制。

    private void ensureCapacityInternal(int minCapacity) {
          //如果是默認(rèn)創(chuàng)建的list谨敛，則最小容量等于DEFAULT_CAPACITY, minCapacity之間的最大值
         // 也就是說在數(shù)組元素的數(shù)量小于10的時候究履，最小容量=10，大于等于10的時候脸狸，最小容量為當(dāng)前size+1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }


    private void ensureExplicitCapacity(int minCapacity) {
        //修改次數(shù)+1最仑，用來實現(xiàn)迭代器是fail-fast機制(是在AbstractList中實現(xiàn)的。)炊甲，所有對集合的修改都會增加
        //在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount泥彤。
        //在迭代過程中，判斷 modCount 跟 expectedModCount 是否相等卿啡，如果不相等就表示已經(jīng)有其他線程修改了集合對象
        modCount++;

        // overflow-conscious code 考慮溢出的情況
        //上面代碼中minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);實際上
        //minCapacity有可能超過Integer.MAX_VALUE吟吝，發(fā)生了溢出  那么minCapacity 就會等于DEFAULT_CAPACITY，所以就不會繼續(xù)增加數(shù)組的容量颈娜，已經(jīng)是最大值了
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


  private void grow(int minCapacity) {
        // overflow-conscious code 考慮溢出
        //舊容量為當(dāng)前數(shù)組的長度剑逃，第一次添加為0
        int oldCapacity = elementData.length;
        //新的數(shù)組容量為原來的1.5倍 >>等于/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
        //如果小于最小容量則新的容量為最小容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //如果新的數(shù)組容量超過Integer.MAX_VALUE - 8
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

  private static int hugeCapacity(int minCapacity) {
        //對溢出進行檢測 ，結(jié)合下面敘述來看
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
  

上面的代碼 if (newCapacity - minCapacity < 0)以及 if (newCapacity - MAX_ARRAY_SIZE > 0) 這里很關(guān)鍵揭鳞，為啥不使用newCapacity < minCapacity 和newCapacity >MAX_ARRAY_SIZE來判斷 ,我們知道newCapacity 是有可能超過int的正數(shù)表示范圍的炕贵，那么就會溢出，成為一個負(fù)數(shù)野崇，而minCapacity是一個正數(shù)称开，負(fù)數(shù)<正數(shù)是恒成立true，而newCapacity - minCapacity，負(fù)數(shù)減正數(shù)是有可能是一個正數(shù)鳖轰，下面同理newCapacity 在MAX_VALUE -1到MAX_VALUE 之間或者newCapacity <-10 (如果溢出肯定小于)清酥，這個條件就會成立，如果使用newCapacity >MAX_ARRAY_SIZE蕴侣，則newCapacity 溢出的時候會恒不成立

• 手動擴容：
  上面的代碼中我們可以看到焰轻，數(shù)組以10為基礎(chǔ)，使用Arrays.copyOf(elementData, newCapacity)進行1.5倍的擴容昆雀，每次滿了就擴容辱志，
  　向數(shù)組中添加第一個元素時，數(shù)組容量為10.

　　向數(shù)組中添加到第10個元素時狞膘，數(shù)組容量仍為10.

　　向數(shù)組中添加到第11個元素時揩懒，數(shù)組容量擴為15.

　　向數(shù)組中添加到第16個元素時，數(shù)組容量擴為22.
這樣帶來了很大的性能問題挽封，所以有時候我們需要對數(shù)組進行手動擴容已球，避免數(shù)組大量的自動擴容
如果參數(shù)大于底層數(shù)組長度的1.5倍，那么這個數(shù)組的容量就會被擴容到這個參數(shù)值辅愿，
如果參數(shù)小于底層數(shù)組長度的1.5倍智亮，那么這個容量就會被擴容到底層數(shù)組長度的1.5倍。

    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *擴展數(shù)組容量点待，盡量使用最小容量
     * @param   minCapacity   the desired minimum capacity
     */
  public void ensureCapacity(int minCapacity) {
          //判斷l(xiāng)ist是否是默認(rèn)方式創(chuàng)建阔蛉，如果是則最小擴展量為DEFAULT_CAPACITY，如果不是則等于0
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        //如果參數(shù)大于底層數(shù)組長度的1.5倍癞埠，那么這個數(shù)組的容量就會被擴容到這個參數(shù)值馍忽，
        //如果參數(shù)小于底層數(shù)組長度的1.5倍，那么這個容量就會被擴容到底層數(shù)組長度的1.5倍燕差。
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

剩下的add（index）、addAll（index）坝冕、remove方法都是基于System.arraycopy（）來實現(xiàn)的不在多說徒探。
然后我們發(fā)現(xiàn)還有一個subList方法，這個方法是做什么的呢喂窟？

• List<E> subList(int fromIndex, int toIndex);
  • 該方法返回的是父list的一個視圖测暗，從fromIndex（包含），到toIndex（不包含）磨澡。fromIndex=toIndex 表示子list為空
  • 父子list做的非結(jié)構(gòu)性修改（non-structural changes）都會影響到彼此：所謂的“非結(jié)構(gòu)性修改”碗啄，是指不涉及到list的大小改變的修改。相反稳摄，結(jié)構(gòu)性修改稚字，指改變了list大小的修改。（比如add、remove）
  • 對于結(jié)構(gòu)性修改胆描，子list的所有操作都會反映到父list上瘫想。但父list的修改將會導(dǎo)致返回的子list失效（即修改原list,則sublist的所有操作會報錯）。
  • tips：如何刪除list中的某段數(shù)據(jù)：
    我們可以用這個方法來實現(xiàn)對指定范圍內(nèi)數(shù)據(jù)的清除昌讲，
    比如說list中有1/2/3/4/5五個元素
    我現(xiàn)在想刪除34怎么做呢

 public static void main(String[] args) {

    LinkedList<String> ll = new LinkedList<>();
    ll.add("1");
    ll.add("2");
    ll.add("3");
    ll.add("4");
    ll.add("5");
    List<String> l2 =  ll.subList(2, 4);
    l2.clear();
    System.out.println(ll);

  }

圖片.png

• List遍歷
  List中有四種遍歷方式：
  • for ：基于計數(shù)器国夜，遍歷者自己在集合外部維護一個計數(shù)器，然后依次讀取每一個位置的元素短绸，當(dāng)讀取到最后一個元素后车吹，停止。主要就是需要按元素的位置來讀取元素醋闭。
  • foreach : 根據(jù)反編譯的字節(jié)碼可以發(fā)現(xiàn)窄驹，foreach內(nèi)部也是采用了Iterator的方式實現(xiàn)，只不過Java編譯器幫我們生成了這些代碼目尖。
  • Iterator ： 每一個具體實現(xiàn)的數(shù)據(jù)集合馒吴，一般都需要提供相應(yīng)的Iterator。相比于傳統(tǒng)for循環(huán)瑟曲，Iterator取締了顯式的遍歷計數(shù)器饮戳。所以基于順序存儲集合的Iterator可以直接按位置訪問數(shù)據(jù)。而基于鏈?zhǔn)酱鎯系腎terator洞拨，正常的實現(xiàn)扯罐，都是需要保存當(dāng)前遍歷的位置。然后根據(jù)當(dāng)前位置來向前或者向后移動指針烦衣。
  • ListIterator ：Iterator實現(xiàn)了集合框架的Iterator接口可以應(yīng)用于所有的集合歹河，Set、List和Map和這些集合的子類型花吟。而ListIterator在實現(xiàn)了Iterator的基礎(chǔ)上實現(xiàn)了ListIterator接口秸歧，提供了額外的方法，只能用于List及其子類型衅澈。
    • ListIterator有add方法键菱，可以向List中添加對象，而Iterator不能今布。
    • ListIterator和Iterator都有hasNext()和next()方法经备，可以實現(xiàn)順序向后遍歷，但是ListIterator有hasPrevious()和previous()方法部默，可以實現(xiàn)逆向（順序向前）遍歷侵蒙。Iterator不可以。
    • ListIterator可以定位當(dāng)前索引的位置傅蹂，nextIndex()和previousIndex()可以實現(xiàn)纷闺。Iterator沒有此功能。
    • 都可實現(xiàn)刪除操作，但是ListIterator可以實現(xiàn)對象的修改急但，set()方法可以實現(xiàn)澎媒。Iterator僅能遍歷，不能修改

public class Test {

  public static void main(String[] args) {
    //  初始化鏈表5000個元素
    List<String> list_5000 = new ArrayList<String>(5000);
    List<String> list_10000 = new ArrayList<String>(10000);
    List<String> list_100000 = new ArrayList<String>(100000);
    for (int i = 0; i < 1000; i++) {
      list_5000.add("1");
      list_5000.add("2");
      list_5000.add("3");
      list_5000.add("4");
      list_5000.add("5");
    }
    for (int j = 0; j < 2000; j++) {
      list_10000.add("1");
      list_10000.add("2");
      list_10000.add("3");
      list_10000.add("4");
      list_10000.add("5");
    }
    for (int k = 0; k < 20000; k++) {
      list_100000.add("1");
      list_100000.add("2");
      list_100000.add("3");
      list_100000.add("4");
      list_100000.add("5");
    }
    //avgTime(list_5000);
    //avgTime(list_10000);
    avgTime(list_100000);
    //System.out.println(traverseByFor(list_100000));
  }

  public static void avgTime(List list) {
    long forAvgTime = 0;
    long foreachAbgTime = 0;
    long iteratorAvgTime = 0;
    long listIteratorAvgTime = 0;
    for (int i = 0; i < 20; i++) {
      forAvgTime += traverseByFor(list);
      foreachAbgTime += traverseByForeach(list);
      iteratorAvgTime += traverseByIterator(list);
      listIteratorAvgTime += traverseByListIterator(list);
    }
    System.out.println("使用for遍歷時間 ：" + forAvgTime );
    System.out.println("使用迭代器遍歷時間 ：" + iteratorAvgTime );
    System.out.println("使用List迭代器遍歷時間 ：" + listIteratorAvgTime );
    System.out.println("使用foreach遍歷時間 ：" + foreachAbgTime );
  }

  /**
   * 使用for遍歷
   */
  public static long traverseByFor(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
      String s = (String) list.get(i);
      //相應(yīng)的業(yè)務(wù)邏輯
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  /**
   * 使用迭代器遍歷
   */
  public static long traverseByIterator(List list) {
    long start = System.currentTimeMillis();

    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
      String s = (String) iterator.next();
      //相應(yīng)的業(yè)務(wù)邏輯
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  public static long traverseByListIterator(List list) {
    long start = System.currentTimeMillis();

    Iterator iterator = list.listIterator();
    while (iterator.hasNext()) {
      String s = (String) iterator.next();
      //相應(yīng)的業(yè)務(wù)邏輯
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

  /**
   * 使用foreach遍歷
   */
  public static long traverseByForeach(List<String> list) {
    long start = System.currentTimeMillis();
    for (String attribute : list) {
      //相應(yīng)的業(yè)務(wù)邏輯
    }
    long between = System.currentTimeMillis() - start;
    return between;
  }

}

• List遍歷的性能
  • for ：對于順序存儲波桩，因為讀取特定位置元素的平均時間復(fù)雜度是O(1)戒努，所以遍歷整個集合的平均時間復(fù)雜度為O(n)。而對于鏈?zhǔn)酱鎯Ω涠悖驗樽x取特定位置元素的平均時間復(fù)雜度是O(n)储玫，所以遍歷整個集合的平均時間復(fù)雜度為O(n2)（n的平方）。
    不過LinkedList做了一定優(yōu)化,查詢位置在鏈表前半部分萤皂，從鏈表頭開始查找,查詢位置在鏈表后半部分撒穷，從鏈表尾開始查找

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

Node<E> node(int index) {
    if (index < (size >> 1)) {   //查詢位置在鏈表前半部分，從鏈表頭開始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                     //查詢位置在鏈表后半部分裆熙，從鏈表尾開始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

• Iterator : 就性能而言端礼，對于RandomAccess類型的集合來說，與for對比并沒有太大意義入录，但是對于Sequential Access的集合來說蛤奥，就有很重大的意義了，因為Iterator內(nèi)部維護了當(dāng)前遍歷的位置僚稿，所以每次遍歷凡桥，讀取下一個位置并不需要從集合的第一個元素開始查找，只要把指針向后移一位就行了蚀同，這樣一來缅刽，遍歷整個集合的時間復(fù)雜度就降低為O(n)；但是使用迭代器主要是為了解耦合蠢络，它可以把訪問邏輯從不同類型的集合類中抽象出來衰猛，從而避免向客戶端暴露集合的內(nèi)部結(jié)構(gòu)。 例如刹孔，如果沒有使用Iterator腕侄，遍歷一個數(shù)組的方法是使用索引；而訪問一個鏈表（LinkedList）又必須使用while循環(huán)芦疏。
• foreach ： 分析Java字節(jié)碼可知，foreach內(nèi)部實現(xiàn)原理微姊，也是通過Iterator實現(xiàn)的酸茴，只不過這個Iterator是Java編譯器幫我們生成的，所以我們不需要再手動去編寫兢交。但是因為每次都要做類型轉(zhuǎn)換檢查薪捍，所以花費的時間比Iterator略長。時間復(fù)雜度和Iterator一樣。
  總的來說酪穿，還是推薦使用迭代器凳干，可以使代碼解耦合，也不必考慮集合內(nèi)部實現(xiàn)被济，降低了時間復(fù)雜度救赐，同時可以在遍歷的同時對集合進行操作。