前言
在一開始基礎面的時候，很多面試官可能會問List集合一些基礎知識，比如：
-
ArrayList默認大小是多少，是如何擴容的？ -
ArrayList和LinkedList的底層數據結構是什麼？ -
ArrayList和LinkedList的區別？分別用在什麼場景？ -
為什麼說
ArrayList查詢快而增刪慢？ -
Arrays.asList方法后的List可以擴容嗎？ -
modCount在非線程安全集合中的作用？ -
ArrayList和LinkedList的區別、優缺點以及應用場景
ArrayList(1.8)
ArrayList是由動態再分配的Object[]數組作為底層結構，可設置null值，是非線程安全的。
ArrayList成員屬性
//默認的空的數組，在構造方法初始化一個空數組的時候使用 private static final Object[] EMPTY_ELEMENTDATA = {}; //使用默認size大小的空數組實例 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //ArrayList底層存儲數據就是通過數組的形式，ArrayList長度就是數組的長度。 transient Object[] elementData; //arrayList的大小 private int size;
那麼ArrayList底層數據結構是什麼呢？
很明顯，使用動態再分配的Object[]數組作為ArrayList底層數據結構了，既然是使用數組實現的，那麼數組特點就能說明為什麼ArrayList查詢快而增刪慢？
因為數組是根據下標查詢不需要比較，查詢方式為：首地址＋（元素長度＊下標），基於這個位置讀取相應的字節數就可以了，所以非常快；但是增刪會帶來元素的移動，增加數據會向後移動，刪除數據會向前移動，導致其效率比較低。
ArrayList的構造方法
-
帶有初始化容量的構造方法
-
無參構造方法
-
參數為
Collection類型的構造器
//帶有初始化容量的構造方法 public ArrayList(int initialCapacity) { //參數大於0，elementData初始化為initialCapacity大小的數組 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; //參數小於0，elementData初始化為空數組 } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; //參數小於0，拋出異常 } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } //無參構造方法 public ArrayList() { //在1.7以後的版本，先構造方法中將elementData初始化為空數組DEFAULTCAPACITY_EMPTY_ELEMENTDATA //當調用add方法添加第一個元素的時候，會進行擴容,擴容至大小為DEFAULT_CAPACITY=10 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
那麼ArrayList默認大小是多少？
從無參構造方法中可以看出，一開始默認為一個空的實例elementData為上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，當添加第一個元素的時候會進行擴容，擴容大小就是上面的默認容量DEFAULT_CAPACITY為10
ArrayList的Add方法
-
boolean add(E)：默認直接在末尾添加元素 -
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方法為確定容量大小方法。在添加元素之前需要確定數組是否能容納下，size是數組中元素個數，添加一個元素size+1。然後再數組末尾添加元素。
其中，ensureCapacityInternal方法包含了ArrayList擴容機制grow方法，當前容量無法容納下數據時1.5倍擴容，進行：
private void ensureCapacityInternal(int minCapacity) { //判斷當前的數組是否為默認設置的空數據，是否取出最小容量 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //包括擴容機制grow方法 ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { //記錄著集合的修改次數，也就每次add或者remove它的值都會加1 modCount++; //當前容量容納不下數據時（下標超過時），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是如何擴容的？
根據當前的容量容納不下新增數據時，ArrayList會調用grow進行擴容：
//相當於int newCapacity = oldCapacity + oldCapacity/2 int newCapacity = oldCapacity + (oldCapacity >> 1);
擴容原來的1.5倍。
void add(int，E)
public void add(int index, E element) { //檢查index也就是插入的位置是否合理,是否存在數組越界 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)：根據元素進行刪除，
-
clear()：將
elementData中每個元素都賦值為null，等待垃圾回收將這個給回收掉， -
removeAll(collection c)：批量刪除。
remove(int)
public E remove(int index) { //檢查下標是否超出數組長度，造成數組越界 rangeCheck(index); modCount++; E oldValue = elementData(index); //算出數組需要移動的元素數量 int numMoved = size - index - 1; if (numMoved > 0) //數組數據遷移，這樣會導致刪除數據時，效率會慢 System.arraycopy(elementData, index+1, elementData, index, numMoved); //將--size上的位置賦值為null，讓gc(垃圾回收機制)更快的回收它。 elementData[--size] = null; // clear to let GC do its work //返回刪除的元素 return oldValue; }
為什麼說ArrayList刪除元素效率低？
因為刪除數據需要將數據後面的元素數據遷移到新增位置的後面，這樣導致性能下降很多，效率低。
remove(Object)
public boolean remove(Object o) { //如果需要刪除數據為null時，會讓數據重新排序，將null數據遷移到數組尾端 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { //刪除數據，並遷移數據 fastRemove(index); return true; } } else { //循環刪除數組中object對象的值，也需要數據遷移 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的雙向鏈表。它也可以被當做堆棧、隊列或雙端隊列進行使用，而且LinkedList也為非線程安全， jdk1.6使用的是一個帶有 header節頭結點的雙向循環鏈表， 頭結點不存儲實際數據 ，在1.6之後，就變更使用兩個節點first、last指向首尾節點。
LinkedList的主要屬性
//鏈表節點的個數 transient int size = 0; //鏈表首節點 transient Node<E> first; //鏈表尾節點 transient Node<E> last; //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; } }
一旦變量被transient修飾，變量將不再是對象持久化的一部分，該變量內容在序列化后無法獲得訪問
LinkedList構造方法
無參構造函數， 默認構造方法聲明也不做，first和last節點會被默認初始化為null。
* /** Constructs an empty list. \*/* public LinkedList() {}
LinkedList插入
由於LinkedList由雙向鏈表作為底層數據結構，因此其插入無非由三大種
-
尾插：
add(E e)、addLast(E e)、addAll(Collection<? extends E> c)
-
頭插：
addFirst(E e) -
中插：
add(int index, E element)
可以從源碼看出，在鏈表首尾添加元素很高效，在中間添加元素比較低效，首先要找到插入位置的節點，在修改前後節點的指針。
尾插-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) { //尾節點 final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; //判斷是否是第一個添加的元素 //如果是將新節點賦值給last //如果不是把原首節點的prev設置為新節點 if (l == null) first = newNode; else l.next = newNode; size++; //將集合修改次數加1 modCount++; }
頭插-addFirst(E e)
public void addFirst(E e) { //在鏈表頭插入指定元素 linkFirst(e); } private void linkFirst(E e) { //獲取頭部元素,首節點 final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; //鏈表頭部為空，（也就是鏈表為空） //插入元素為首節點元素 // 否則就更新原來的頭元素的prev為新元素的地址引用 if (f == null) last = newNode; else f.prev = newNode; // size++; modCount++; }
中插-add(int index, E element)
當index不為首尾的的時候，實際就在鏈表中間插入元素。
// 作用：在指定位置添加元素 public void add(int index, E element) { // 檢查插入位置的索引的合理性 checkPositionIndex(index); if (index == size) // 插入的情況是尾部插入的情況：調用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; // 得到插入位置元素的前繼節點 final Node<E> newNode = new Node<>(pred, e, succ); // 創建新節點，其前繼節點是succ的前節點，後接點是succ節點 succ.prev = newNode; // 更新插入位置（succ）的前置節點為新節點 if (pred == null) // 如果pred為null，說明該節點插入在頭節點之前，要重置first頭節點 first = newNode; else // 如果pred不為null，那麼直接將pred的後繼指針指向newNode即可 pred.next = newNode; size++; modCount++; }
LinkedList 刪除
刪除和插入一樣，其實本質也是只有三大種方式，
-
刪除首節點:
removeFirst() -
刪除尾節點:
removeLast() -
刪除中間節點 ：
remove(Object o)、remove(int index)
在首尾節點刪除很高效，刪除中間元素比較低效要先找到節點位置，再修改前後指針指引。
刪除中間節點-remove(int index)和remove(Object o)
remove(int index)和remove(Object o)都是使用刪除指定節點的unlink刪除元素 public boolean remove(Object o) { //因為LinkedList允許存在null，所以需要進行null判斷 if (o == null) { //從首節點開始遍歷 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { //調用unlink方法刪除指定節點 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方法獲得指定位置的節點，再通過unlink方法刪除 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } //刪除指定節點 E unlink(Node<E> x) { //獲取x節點的元素，以及它上一個節點，和下一個節點 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //如果x的上一個節點為null，說明是首節點，將x的下一個節點設置為新的首節點 //否則將x的上一節點設置為next，將x的上一節點設為null if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //如果x的下一節點為null，說明是尾節點，將x的上一節點設置新的尾節點 //否則將x的上一節點設置x的上一節點，將x的下一節點設為null if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //將x節點的元素值設為null，等待垃圾收集器收集 x.item = null; //鏈表節點個數減1 size--; //將集合修改次數加1 modCount++; //返回刪除節點的元素值 return element; }
刪除首節點-removeFirst()
//刪除首節點 public E remove() { return removeFirst(); } //刪除首節點 public E removeFirst() { final Node<E> f = first; //如果首節點為null，說明是空鏈表，拋出異常 if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //刪除首節點 private E unlinkFirst(Node<E> f) { //首節點的元素值 final E element = f.item; //首節點的下一節點 final Node<E> next = f.next; //將首節點的元素值和下一節點設為null，等待垃圾收集器收集 f.item = null; f.next = null; // help GC //將next設置為新的首節點 first = next; //如果next為null，說明說明鏈表中只有一個節點，把last也設為null //否則把next的上一節點設為null if (next == null) last = null; else next.prev = null; //鏈表節點個數減1 size--; //將集合修改次數加1 modCount++; //返回刪除節點的元素值 return element; }
刪除尾節點-removeLast()
//刪除尾節點 public E removeLast() { final Node<E> l = last; //如果首節點為null，說明是空鏈表，拋出異常 if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } private E unlinkLast(Node<E> l) { //尾節點的元素值 final E element = l.item; //尾節點的上一節點 final Node<E> prev = l.prev; //將尾節點的元素值和上一節點設為null，等待垃圾收集器收集 l.item = null; l.prev = null; // help GC //將prev設置新的尾節點 last = prev; //如果prev為null，說明說明鏈表中只有一個節點，把first也設為null //否則把prev的下一節點設為null if (prev == null) first = null; else prev.next = null; //鏈表節點個數減1 size--; //將集合修改次數加1 modCount++; //返回刪除節點的元素值 return element; }
其他方法也是類似的，比如查詢方法 LinkedList提供了get、getFirst、getLast等方法獲取節點元素值。
modCount屬性的作用？
modCount屬性代表為結構性修改（ 改變list的size大小、以其他方式改變他導致正在進行迭代時出現錯誤的結果）的次數，該屬性被Iterator以及ListIterator的實現類所使用，且很多非線程安全使用modCount屬性。
初始化迭代器時會給這個modCount賦值，如果在遍歷的過程中，一旦發現這個對象的modCount和迭代器存儲的modCount不一樣，Iterator或者ListIterator 將拋出ConcurrentModificationException異常，
這是jdk在面對迭代遍歷的時候為了避免不確定性而採取的 fail-fast（快速失敗）原則：
在線程不安全的集合中，如果使用迭代器的過程中，發現集合被修改，會拋出ConcurrentModificationExceptions錯誤，這就是fail-fast機制。對集合進行結構性修改時，modCount都會增加，在初始化迭代器時，modCount的值會賦給expectedModCount，在迭代的過程中，只要modCount改變了，int expectedModCount = modCount等式就不成立了，迭代器檢測到這一點，就會拋出錯誤：urrentModificationExceptions。
總結
ArrayList和LinkedList的區別、優缺點以及應用場景
區別：
-
ArrayList是實現了基於動態數組的數據結構，LinkedList是基於鏈表結構。 -
對於隨機訪問的
get和set方法查詢元素，ArrayList要優於LinkedList，因為LinkedList循環鏈表尋找元素。 -
對於新增和刪除操作
add和remove，LinkedList比較高效，因為ArrayList要移動數據。
優缺點：
-
對
ArrayList和LinkedList而言，在末尾增加一個元素所花的開銷都是固定的。對ArrayList而言，主要是在內部數組中增加一項，指向所添加的元素，偶爾可能會導致對數組重新進行分配；而對LinkedList而言，這個開銷是 統一的，分配一個內部Entry對象。 -
在
ArrayList集合中添加或者刪除一個元素時，當前的列表移動元素後面所有的元素都會被移動。而LinkedList集合中添加或者刪除一個元素的開銷是固定的。 -
LinkedList集合不支持 高效的隨機隨機訪問（RandomAccess），因為可能產生二次項的行為。 -
ArrayList的空間浪費主要體現在在list列表的結尾預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗相當的空間
應用場景:
ArrayList使用在查詢比較多，但是插入和刪除比較少的情況，而LinkedList用在查詢比較少而插入刪除比較多的情況
各位看官還可以嗎？喜歡的話，動動手指點個，點個關注唄！！謝謝支持！
歡迎掃碼關注，原創技術文章第一時間推出
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※台北網頁設計公司全省服務真心推薦
※想知道最厲害的網頁設計公司"嚨底家"!
※推薦評價好的iphone維修中心