前言

實習(xí)即將結(jié)束,要開始為之后的春招做準(zhǔn)備了,鞏固下基礎(chǔ).

LinkedList和ArrayList是開發(fā)中常見的集合類,今天我就從源碼分析一下兩者的優(yōu)缺點和不同之處.

正文

• 增:

  ArrayList

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
  
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
  
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity); 
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
  

我們發(fā)現(xiàn)ArrayList的add方法中調(diào)用了ensureCapacityInternal方法,最終調(diào)用了grow方法.我們都知道ArrayList的本質(zhì)其實還是對數(shù)組的操作,而數(shù)組的長度是不可改變的,當(dāng)我們加入的元素超出數(shù)組本身的長度,它會根據(jù)數(shù)組當(dāng)前長度的一半進行擴容,也就是grow方法,然后添加進數(shù)組.

grow通過下面這句代碼擴容,將舊數(shù)組通過copyof方法拷貝,并賦予一個新的長度newCapacity,生成一個新的數(shù)組.

elementData = Arrays.copyOf(elementData, newCapacity);
//將新增的元素加入數(shù)組
elementData[size++] = e;

LinkedList:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

LinkedList是一個雙鏈表模式的集合,而通過代碼,我們不難看出,每當(dāng)你為集合新增一個元素,它只需要將末端元素的next指向添加的元素即可.

我們不難看出,在增這一項上LinkedList在效率上無疑是大于ArrayList的,它不需要考慮長度不夠時的擴容,也不需要將舊數(shù)組拷貝賦予新數(shù)組,只需要將指針指向新的元素即可.

• 刪:

  ArrayList:

  public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    modCount++;
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    elementData[--size] = null;
    return oldValue;
  

  }

我們發(fā)現(xiàn),在判斷是否越界后,ArrayList通過拷貝將index后的所有元素提前一位,并將原數(shù)組的最后一個元素置空,方便虛擬機回收.

LinkedList:

 public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

通過代碼,我們發(fā)現(xiàn),LinkedList在刪除時,直接將要刪除的前一個元素指向要刪除的后一個元素,舉個栗子.共有1旦部、2黄鳍、3三個元素启妹，通過鏈表的表示方法是，1->2->3,我們刪除時,只需要將鏈表改為1->3,之后將2這個元素置空即可.并不需要像ArrayList那樣通過拷貝的方法去刪除.

所以,在刪除這個操作上,LinkedList在效率上無疑要大于ArrayList的.

• 改:

  ArrayList:

  public E set(int index, E element) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
    }
  

通過代碼我們發(fā)現(xiàn),ArrayList在改操作是非常簡單的,直接通過引用的方式替換.

LinkedList:

 public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

 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;
    }
}

相較于ArrayList來說,LinkedList無疑顯得非常的復(fù)雜,通過node方法查找元素,之后直接通過引用替換,但是在查找元素時無疑是非常耗時的,通過代碼我們發(fā)現(xiàn),它是通過遍歷鏈表一個一個對比.雖然做了一些優(yōu)化,在查找之前先判斷了index元素是屬于鏈表的前半?yún)^(qū),還是后半?yún)^(qū).但相對于ArrayList在效率上無疑是不如的.

• 查:

  ArrayList:

    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
        return (E) elementData[index];
    }
  

直接通過數(shù)組查找然后強轉(zhuǎn).

`LinkedList`:
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;
    }
}

之前在改操作的時候已經(jīng)分析了查找時的缺點,就不在分析了.

總得來說,ArrayList與LinkedList的優(yōu)缺點如下表:

通過表格我們可以看出2中集合的優(yōu)缺點,ArrayList更適用于大量改查操作的情況,而LinkedList更使用于大量增刪操作的情況.

結(jié)語

在分析的過程中,LinkedList感覺可以在查的時候進行優(yōu)化,通過算法去優(yōu)化LinkedList本身的不足,通過各種查找算法去優(yōu)化.