java中ArrayList和LinkedList的區別詳解

Posted on by

ArrayList和LinkedList都實現瞭List接口，有以下的不同點：

1、ArrayList是基於索引的數據接口，它的底層是數組。它可以以O(1)時間復雜度對元素進行隨機訪問。與此對應，LinkedList是以元素列表的形式存儲它的數據，每一個元素都和它的前一個和後一個元素鏈接在一起，在這種情況下，查找某個元素的時間復雜度是O(n)。
2、相對於ArrayList，LinkedList的插入，添加，刪除操作速度更快，因為當元素被添加到集合任意位置的時候，不需要像數組那樣重新計算大小或者是更新索引。
3、LinkedList比ArrayList更占內存，因為LinkedList為每一個節點存儲瞭兩個引用，一個指向前一個元素，一個指向下一個元素。

ArrayList擴容：

總的來說就是分兩步：

1、擴容

把原來的數組復制到另一個內存空間更大的數組中

2、添加元素

把新元素添加到擴容以後的數組中
無參構造：

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

帶參構造：

public ArrayList(int initialCapacity) {
  if (initialCapacity >0) {
    this.elementData =new Object[initialCapacity];
  }else if (initialCapacity ==0) {
    this.elementData = EMPTY_ELEMENTDATA;
  }else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                      initialCapacity);
  }
}

在無參構造中，我們看到瞭在用無參構造來創建對象的時候其實就是創建瞭一個空數組，長度為0
在有參構造中，傳入的參數是正整數就按照傳入的參數來確定創建數組的大小，否則異常
接下來我們來看擴容，擴容的方法就是 add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;
    return true;
  }
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  }
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
  }
private void ensureExplicitCapacity(int minCapacity) {
   modCount++;

   // overflow-conscious code
   if (minCapacity - elementData.length > 0)
     grow(minCapacity);
 }
private void grow(int minCapacity) {
   // overflow-conscious code
   int oldCapacity = elementData.length;
   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);
 }

int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity >> 1 右移運算符 原來長度的一半 再加上原長度也就是每次擴容是原來的1.5倍
之前的所有都是確定新數組的長度，確定之後就是把老數組copy到新數組中，這樣數組的擴容就結束瞭
以上的一切都是ArrayList擴容的第一步，第二步就沒啥說的瞭，就是把需要添加的元素添加到數組的最後一位

以上就是java中ArrayList和LinkedList的區別詳解的詳細內容，更多關於java ArrayList和LinkedList的區別的資料請關註WalkonNet其它相關文章！

推薦閱讀：