去年去阿里面試叔壤，被問到ArrayList和LinkedList焕梅，我是這樣回答的！

前言

在一開始基礎(chǔ)面的時候蚓聘，很多面試官可能會問List集合一些基礎(chǔ)知識，比如：

ArrayList默認(rèn)大小是多少盟劫，是如何擴容的夜牡？
ArrayList和LinkedList的底層數(shù)據(jù)結(jié)構(gòu)是什么？
ArrayList和LinkedList的區(qū)別侣签？分別用在什么場景塘装？
為什么說ArrayList查詢快而增刪慢？
Arrays.asList方法后的List可以擴容嗎影所？
modCount在非線程安全集合中的作用蹦肴？
ArrayList和LinkedList的區(qū)別、優(yōu)缺點以及應(yīng)用場景

ArrayList(1.8)

ArrayList是由動態(tài)再分配的Object[]數(shù)組作為底層結(jié)構(gòu)猴娩，可設(shè)置null值阴幌，是非線程安全的。

ArrayList成員屬性

//默認(rèn)的空的數(shù)組卷中，在構(gòu)造方法初始化一個空數(shù)組的時候使用
private static final Object[] EMPTY_ELEMENTDATA = {};

//使用默認(rèn)size大小的空數(shù)組實例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList底層存儲數(shù)據(jù)就是通過數(shù)組的形式矛双，ArrayList長度就是數(shù)組的長度。
transient Object[] elementData; 

//arrayList的大小
private int size;

那么ArrayList底層數(shù)據(jù)結(jié)構(gòu)是什么呢仓坞？

很明顯背零，使用動態(tài)再分配的Object[]數(shù)組作為ArrayList底層數(shù)據(jù)結(jié)構(gòu)了，既然是使用數(shù)組實現(xiàn)的无埃，那么數(shù)組特點就能說明為什么ArrayList查詢快而增刪慢徙瓶？

因為數(shù)組是根據(jù)下標(biāo)查詢不需要比較，查詢方式為：首地址＋（元素長度＊下標(biāo)）嫉称，基于這個位置讀取相應(yīng)的字節(jié)數(shù)就可以了侦镇，所以非常快织阅；但是增刪會帶來元素的移動壳繁，增加數(shù)據(jù)會向后移動，刪除數(shù)據(jù)會向前移動，導(dǎo)致其效率比較低闹炉。

ArrayList的構(gòu)造方法

帶有初始化容量的構(gòu)造方法
無參構(gòu)造方法
參數(shù)為Collection類型的構(gòu)造器

//帶有初始化容量的構(gòu)造方法
public ArrayList(int initialCapacity) {
    //參數(shù)大于0蒿赢，elementData初始化為initialCapacity大小的數(shù)組
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    //參數(shù)小于0，elementData初始化為空數(shù)組
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    //參數(shù)小于0渣触，拋出異常
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//無參構(gòu)造方法
public ArrayList() {
    //在1.7以后的版本羡棵，先構(gòu)造方法中將elementData初始化為空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    //當(dāng)調(diào)用add方法添加第一個元素的時候，會進(jìn)行擴容,擴容至大小為DEFAULT_CAPACITY=10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

那么ArrayList默認(rèn)大小是多少嗅钻？

從無參構(gòu)造方法中可以看出皂冰，一開始默認(rèn)為一個空的實例elementData為上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，當(dāng)添加第一個元素的時候會進(jìn)行擴容养篓，擴容大小就是上面的默認(rèn)容量DEFAULT_CAPACITY為10

ArrayList的Add方法

boolean add(E)：默認(rèn)直接在末尾添加元素
void add(int秃流，E)：在特定位置添加元素，也就是插入元素
boolean addAll(Collection<? extends E> c)：添加集合
boolean addAll(int index, Collection<? extends E> c)：在指定位置后添加集合

boolean add(E)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

通過ensureCapacityInternal方法為確定容量大小方法柳弄。在添加元素之前需要確定數(shù)組是否能容納下舶胀，size是數(shù)組中元素個數(shù)，添加一個元素size+1语御。然后再數(shù)組末尾添加元素峻贮。

其中，ensureCapacityInternal方法包含了ArrayList擴容機制grow方法应闯，當(dāng)前容量無法容納下數(shù)據(jù)時1.5倍擴容，進(jìn)行：

private void ensureCapacityInternal(int minCapacity) {
    //判斷當(dāng)前的數(shù)組是否為默認(rèn)設(shè)置的空數(shù)據(jù)挂捻，是否取出最小容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //包括擴容機制grow方法
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
        //記錄著集合的修改次數(shù)碉纺，也就每次add或者remove它的值都會加1
        modCount++;

        //當(dāng)前容量容納不下數(shù)據(jù)時（下標(biāo)超過時），ArrayList擴容機制：擴容原來的1.5倍
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //ArrayList擴容機制：擴容原來的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList是如何擴容的刻撒？

根據(jù)當(dāng)前的容量容納不下新增數(shù)據(jù)時骨田，ArrayList會調(diào)用grow進(jìn)行擴容：

//相當(dāng)于int newCapacity = oldCapacity + oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);

擴容原來的1.5倍。

void add(int声怔，E)

public void add(int index, E element) {
    //檢查index也就是插入的位置是否合理,是否存在數(shù)組越界
    rangeCheckForAdd(index);
    //機制和boolean add(E)方法一樣
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

ArrayList的刪除方法

remove(int)：通過刪除指定位置上的元素态贤，
remove(Object)：根據(jù)元素進(jìn)行刪除，
clear()：將elementData中每個元素都賦值為null醋火，等待垃圾回收將這個給回收掉悠汽，
removeAll(collection c)：批量刪除。

remove(int)

public E remove(int index) {
    //檢查下標(biāo)是否超出數(shù)組長度芥驳，造成數(shù)組越界
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
    //算出數(shù)組需要移動的元素數(shù)量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //數(shù)組數(shù)據(jù)遷移柿冲，這樣會導(dǎo)致刪除數(shù)據(jù)時，效率會慢
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //將--size上的位置賦值為null兆旬，讓gc(垃圾回收機制)更快的回收它假抄。
    elementData[--size] = null; // clear to let GC do its work
    //返回刪除的元素
    return oldValue;
}

為什么說ArrayList刪除元素效率低？

因為刪除數(shù)據(jù)需要將數(shù)據(jù)后面的元素數(shù)據(jù)遷移到新增位置的后面，這樣導(dǎo)致性能下降很多宿饱，效率低熏瞄。

remove(Object)

public boolean remove(Object o) {
    //如果需要刪除數(shù)據(jù)為null時，會讓數(shù)據(jù)重新排序谬以，將null數(shù)據(jù)遷移到數(shù)組尾端
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //刪除數(shù)據(jù)巴刻，并遷移數(shù)據(jù)
                fastRemove(index);
                return true;
            }
    } else {
        //循環(huán)刪除數(shù)組中object對象的值，也需要數(shù)據(jù)遷移
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

可以看出蛉签，arrayList是可以存放null值胡陪。

LinkedList(1.8)

LinkedList是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)做堆棧碍舍、隊列或雙端隊列進(jìn)行使用柠座，而且LinkedList也為非線程安全， jdk1.6使用的是一個帶有 header節(jié)頭結(jié)點的雙向循環(huán)鏈表片橡，頭結(jié)點不存儲實際數(shù)據(jù) 妈经，在1.6之后，就變更使用兩個節(jié)點first捧书、last指向首尾節(jié)點吹泡。

LinkedList的主要屬性

//鏈表節(jié)點的個數(shù) 
transient int size = 0; 
//鏈表首節(jié)點
 transient Node<E> first; 
//鏈表尾節(jié)點
 transient Node<E> last; 
//Node節(jié)點內(nèi)部類定義
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;
        }
    }

一旦變量被transient修飾，變量將不再是對象持久化的一部分经瓷，該變量內(nèi)容在序列化后無法獲得訪問

LinkedList構(gòu)造方法

無參構(gòu)造函數(shù)爆哑，默認(rèn)構(gòu)造方法聲明也不做，first和last節(jié)點會被默認(rèn)初始化為null舆吮。

*
/** Constructs an empty list. \*/*

public LinkedList() {}

LinkedList插入

由于LinkedList由雙向鏈表作為底層數(shù)據(jù)結(jié)構(gòu)揭朝，因此其插入無非由三大種

尾插： add(E e)、addLast(E e)色冀、addAll(Collection<? extends E> c)
頭插： addFirst(E e)
中插： add(int index, E element)

可以從源碼看出潭袱，在鏈表首尾添加元素很高效，在中間添加元素比較低效锋恬，首先要找到插入位置的節(jié)點屯换，在修改前后節(jié)點的指針。

尾插-add(E e)和addLast(E e)

//常用的添加元素方法
public boolean add(E e) {
    //使用尾插法
    linkLast(e);
    return true;
}

//在鏈表尾部添加元素
public void addLast(E e) {
        linkLast(e);
    }

//在鏈表尾端添加元素
void linkLast(E e) {
        //尾節(jié)點
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        //判斷是否是第一個添加的元素
        //如果是將新節(jié)點賦值給last
        //如果不是把原首節(jié)點的prev設(shè)置為新節(jié)點
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        //將集合修改次數(shù)加1
        modCount++;
    }

頭插-addFirst(E e)

public void addFirst(E e) {
    //在鏈表頭插入指定元素
    linkFirst(e);
}

private void linkFirst(E e) {
            //獲取頭部元素,首節(jié)點
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        //鏈表頭部為空与学，（也就是鏈表為空）
        //插入元素為首節(jié)點元素
        // 否則就更新原來的頭元素的prev為新元素的地址引用
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        //
        size++;
        modCount++;
    }

中插-add(int index, E element)

當(dāng)index不為首尾的的時候彤悔，實際就在鏈表中間插入元素。

 // 作用：在指定位置添加元素
    public void add(int index, E element) {
        // 檢查插入位置的索引的合理性
        checkPositionIndex(index);

        if (index == size)
            // 插入的情況是尾部插入的情況：調(diào)用linkLast（）癣防。
            linkLast(element);
        else
            // 插入的情況是非尾部插入的情況（中間插入）：linkBefore
            linkBefore(element, node(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;  // 得到插入位置元素的前繼節(jié)點
        final Node<E> newNode = new Node<>(pred, e, succ);  // 創(chuàng)建新節(jié)點蜗巧，其前繼節(jié)點是succ的前節(jié)點，后接點是succ節(jié)點
        succ.prev = newNode;  // 更新插入位置（succ）的前置節(jié)點為新節(jié)點
        if (pred == null)
            // 如果pred為null蕾盯，說明該節(jié)點插入在頭節(jié)點之前幕屹，要重置first頭節(jié)點 
            first = newNode;
        else
            // 如果pred不為null蓝丙，那么直接將pred的后繼指針指向newNode即可
            pred.next = newNode;
        size++;
        modCount++;
    }

LinkedList 刪除

刪除和插入一樣，其實本質(zhì)也是只有三大種方式望拖，

刪除首節(jié)點:removeFirst()
刪除尾節(jié)點:removeLast()
刪除中間節(jié)點：remove(Object o)渺尘、remove(int index)

在首尾節(jié)點刪除很高效，刪除中間元素比較低效要先找到節(jié)點位置说敏，再修改前后指針指引鸥跟。

刪除中間節(jié)點-remove(int index)和remove(Object o)

remove(int index)和remove(Object o)都是使用刪除指定節(jié)點的unlink刪除元素

 public boolean remove(Object o) {
     //因為LinkedList允許存在null，所以需要進(jìn)行null判斷        
     if (o == null) {
         //從首節(jié)點開始遍歷
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 //調(diào)用unlink方法刪除指定節(jié)點
                 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;
 } 

//刪除指定位置的節(jié)點盔沫，其實和上面的方法差不多
    //通過node方法獲得指定位置的節(jié)點医咨，再通過unlink方法刪除
    public E remove(int index) {
        checkElementIndex(index);

        return unlink(node(index));
    }

 //刪除指定節(jié)點
    E unlink(Node<E> x) {
        //獲取x節(jié)點的元素，以及它上一個節(jié)點架诞，和下一個節(jié)點
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果x的上一個節(jié)點為null拟淮，說明是首節(jié)點，將x的下一個節(jié)點設(shè)置為新的首節(jié)點
        //否則將x的上一節(jié)點設(shè)置為next谴忧，將x的上一節(jié)點設(shè)為null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        //如果x的下一節(jié)點為null很泊，說明是尾節(jié)點，將x的上一節(jié)點設(shè)置新的尾節(jié)點
        //否則將x的上一節(jié)點設(shè)置x的上一節(jié)點沾谓，將x的下一節(jié)點設(shè)為null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //將x節(jié)點的元素值設(shè)為null委造，等待垃圾收集器收集
        x.item = null;
        //鏈表節(jié)點個數(shù)減1
        size--;
        //將集合修改次數(shù)加1
        modCount++;
        //返回刪除節(jié)點的元素值
        return element;
    }

刪除首節(jié)點-removeFirst()

//刪除首節(jié)點
public E remove() {
        return removeFirst();
    }
 //刪除首節(jié)點
 public E removeFirst() {
      final Node<E> f = first;
      //如果首節(jié)點為null，說明是空鏈表均驶，拋出異常
      if (f == null)
          throw new NoSuchElementException();
      return unlinkFirst(f);
  }
  //刪除首節(jié)點
  private E unlinkFirst(Node<E> f) {
      //首節(jié)點的元素值
      final E element = f.item;
      //首節(jié)點的下一節(jié)點
      final Node<E> next = f.next;
      //將首節(jié)點的元素值和下一節(jié)點設(shè)為null昏兆，等待垃圾收集器收集
      f.item = null;
      f.next = null; // help GC
      //將next設(shè)置為新的首節(jié)點
      first = next;
      //如果next為null，說明說明鏈表中只有一個節(jié)點辣恋，把last也設(shè)為null
      //否則把next的上一節(jié)點設(shè)為null
      if (next == null)
          last = null;
      else
          next.prev = null;
      //鏈表節(jié)點個數(shù)減1
      size--;
      //將集合修改次數(shù)加1
      modCount++;
      //返回刪除節(jié)點的元素值
      return element;
 }

刪除尾節(jié)點-removeLast()

    //刪除尾節(jié)點
    public E removeLast() {
        final Node<E> l = last;
        //如果首節(jié)點為null亮垫，說明是空鏈表，拋出異常
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
           //尾節(jié)點的元素值
        final E element = l.item;
        //尾節(jié)點的上一節(jié)點
        final Node<E> prev = l.prev;
        //將尾節(jié)點的元素值和上一節(jié)點設(shè)為null伟骨，等待垃圾收集器收集
        l.item = null;
        l.prev = null; // help GC
        //將prev設(shè)置新的尾節(jié)點
        last = prev;
        //如果prev為null，說明說明鏈表中只有一個節(jié)點燃异，把first也設(shè)為null
        //否則把prev的下一節(jié)點設(shè)為null
        if (prev == null)
            first = null;
        else
            prev.next = null;
        //鏈表節(jié)點個數(shù)減1
        size--;
        //將集合修改次數(shù)加1
        modCount++;
        //返回刪除節(jié)點的元素值
        return element;
    }

其他方法也是類似的携狭，比如查詢方法 LinkedList提供了get、getFirst回俐、getLast等方法獲取節(jié)點元素值逛腿。

modCount屬性的作用？

modCount屬性代表為結(jié)構(gòu)性修改（改變list的size大小仅颇、以其他方式改變他導(dǎo)致正在進(jìn)行迭代時出現(xiàn)錯誤的結(jié)果）的次數(shù)单默，該屬性被Iterator以及ListIterator的實現(xiàn)類所使用，且很多非線程安全使用modCount屬性忘瓦。

? 初始化迭代器時會給這個modCount賦值搁廓，如果在遍歷的過程中，一旦發(fā)現(xiàn)這個對象的modCount和迭代器存儲的modCount不一樣，Iterator或者ListIterator 將拋出ConcurrentModificationException異常境蜕，

這是jdk在面對迭代遍歷的時候為了避免不確定性而采取的 fail-fast（快速失旘　）原則：

在線程不安全的集合中，如果使用迭代器的過程中粱年，發(fā)現(xiàn)集合被修改售滤，會拋出ConcurrentModificationExceptions錯誤，這就是fail-fast機制台诗。對集合進(jìn)行結(jié)構(gòu)性修改時完箩，modCount都會增加，在初始化迭代器時拉队，modCount的值會賦給expectedModCount弊知，在迭代的過程中，只要modCount改變了氏仗，int expectedModCount = modCount等式就不成立了吉捶，迭代器檢測到這一點，就會拋出錯誤：urrentModificationExceptions皆尔。

總結(jié)

ArrayList和LinkedList的區(qū)別呐舔、優(yōu)缺點以及應(yīng)用場景

區(qū)別：

ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList是基于鏈表結(jié)構(gòu)慷蠕。
對于隨機訪問的get和set方法查詢元素珊拼，ArrayList要優(yōu)于LinkedList，因為LinkedList循環(huán)鏈表尋找元素流炕。
對于新增和刪除操作add和remove澎现，LinkedList比較高效，因為ArrayList要移動數(shù)據(jù)每辟。

優(yōu)缺點：

對ArrayList和LinkedList而言剑辫，在末尾增加一個元素所花的開銷都是固定的。對ArrayList而言渠欺，主要是在內(nèi)部數(shù)組中增加一項妹蔽，指向所添加的元素，偶爾可能會導(dǎo)致對數(shù)組重新進(jìn)行分配挠将；而對LinkedList而言胳岂，這個開銷是統(tǒng)一的，分配一個內(nèi)部Entry對象舔稀。
在ArrayList集合中添加或者刪除一個元素時乳丰，當(dāng)前的列表移動元素后面所有的元素都會被移動。而LinkedList集合中添加或者刪除一個元素的開銷是固定的内贮。
LinkedList集合不支持高效的隨機隨機訪問（RandomAccess）产园，因為可能產(chǎn)生二次項的行為汞斧。
ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當(dāng)?shù)目臻g

應(yīng)用場景:

ArrayList使用在查詢比較多淆两，但是插入和刪除比較少的情況断箫，而LinkedList用在查詢比較少而插入刪除比較多的情況

去年去阿里面試熙含，被問到ArrayList和LinkedList，我是這樣回答的艇纺！

去年去阿里面試怎静，被問到ArrayList和LinkedList，我是這樣回答的黔衡！

前言