面試:在面試中關於List(ArrayList、LinkedList)集合會怎麼問呢?你該如何回答呢?

前言

在一開始基礎面的時候,很多面試官可能會問List集合一些基礎知識,比如:

  • ArrayList默認大小是多少,是如何擴容的?

  • ArrayListLinkedList的底層數據結構是什麼?

  • ArrayListLinkedList的區別?分別用在什麼場景?

  • 為什麼說ArrayList查詢快而增刪慢?

  • Arrays.asList方法后的List可以擴容嗎?

  • modCount在非線程安全集合中的作用?

  • ArrayListLinkedList的區別、優缺點以及應用場景

 

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_CAPACITY10

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之後,就變更使用兩個節點firstlast指向首尾節點。

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構造方法

無參構造函數, 默認構造方法聲明也不做,firstlast節點會被默認初始化為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提供了getgetFirstgetLast等方法獲取節點元素值。

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是基於鏈表結構。

  • 對於隨機訪問的getset方法查詢元素,ArrayList要優於LinkedList,因為LinkedList循環鏈表尋找元素。

  • 對於新增和刪除操作addremoveLinkedList比較高效,因為ArrayList要移動數據。

優缺點:

  • ArrayListLinkedList而言,在末尾增加一個元素所花的開銷都是固定的。對ArrayList而言,主要是在內部數組中增加一項,指向所添加的元素,偶爾可能會導致對數組重新進行分配;而對LinkedList而言,這個開銷是 統一的,分配一個內部Entry對象。

  • ArrayList集合中添加或者刪除一個元素時,當前的列表移動元素後面所有的元素都會被移動。而LinkedList集合中添加或者刪除一個元素的開銷是固定的。

  • LinkedList集合不支持 高效的隨機隨機訪問(RandomAccess),因為可能產生二次項的行為。

  • ArrayList的空間浪費主要體現在在list列表的結尾預留一定的容量空間,而LinkedList的空間花費則體現在它的每一個元素都需要消耗相當的空間

應用場景:

ArrayList使用在查詢比較多,但是插入和刪除比較少的情況,而LinkedList用在查詢比較少而插入刪除比較多的情況

各位看官還可以嗎?喜歡的話,動動手指點個,點個關注唄!!謝謝支持!

歡迎掃碼關注,原創技術文章第一時間推出

 

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

※推薦評價好的iphone維修中心

您可能也會喜歡…