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

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

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

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

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

ArrayList擴(kuò)容：

總的來(lái)說(shuō)就是分兩步：

1、擴(kuò)容

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

2、添加元素

把新元素添加到擴(kuò)容以后的數(shù)組中
無(wú)參構(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);
  }
}

在無(wú)參構(gòu)造中，我們看到了在用無(wú)參構(gòu)造來(lái)創(chuàng)建對(duì)象的時(shí)候其實(shí)就是創(chuàng)建了一個(gè)空數(shù)組，長(zhǎng)度為0
在有參構(gòu)造中，傳入的參數(shù)是正整數(shù)就按照傳入的參數(shù)來(lái)確定創(chuàng)建數(shù)組的大小，否則異常
接下來(lái)我們來(lái)看擴(kuò)容，擴(kuò)容的方法就是 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 右移運(yùn)算符原來(lái)長(zhǎng)度的一半再加上原長(zhǎng)度也就是每次擴(kuò)容是原來(lái)的1.5倍
之前的所有都是確定新數(shù)組的長(zhǎng)度，確定之后就是把老數(shù)組copy到新數(shù)組中，這樣數(shù)組的擴(kuò)容就結(jié)束了
以上的一切都是ArrayList擴(kuò)容的第一步，第二步就沒(méi)啥說(shuō)的了，就是把需要添加的元素添加到數(shù)組的最后一位

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

您可能感興趣的文章: