快捷導(dǎo)航

java中ArrayList和LinkedList的區(qū)別詳解

更新時間：2021年01月16日 11:55:34 作者：萌萌萌桃子

這篇文章主要介紹了java中ArrayList和LinkedList的區(qū)別詳解，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下

ArrayList和LinkedList都實現(xiàn)了List接口，有以下的不同點：

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

ArrayList擴容：

總的來說就是分兩步：

1、擴容

把原來的數(shù)組復(fù)制到另一個內(nèi)存空間更大的數(shù)組中

2、添加元素

把新元素添加到擴容以后的數(shù)組中
無參構(gòu)造：

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

帶參構(gòu)造：

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

在無參構(gòu)造中，我們看到了在用無參構(gòu)造來創(chuàng)建對象的時候其實就是創(chuàng)建了一個空數(shù)組，長度為0
在有參構(gòu)造中，傳入的參數(shù)是正整數(shù)就按照傳入的參數(shù)來確定創(chuàng)建數(shù)組的大小，否則異常
接下來我們來看擴容，擴容的方法就是 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倍
之前的所有都是確定新數(shù)組的長度，確定之后就是把老數(shù)組copy到新數(shù)組中，這樣數(shù)組的擴容就結(jié)束了
以上的一切都是ArrayList擴容的第一步，第二步就沒啥說的了，就是把需要添加的元素添加到數(shù)組的最后一位

以上就是java中ArrayList和LinkedList的區(qū)別詳解的詳細內(nèi)容，更多關(guān)于java ArrayList和LinkedList的區(qū)別的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: