欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

ArrayList和LinkedList的區(qū)別、擴容機制以及底層的實現(xiàn)方式

 更新時間:2023年03月31日 08:59:57   作者:WINGZINGLIU  
這篇文章主要介紹了ArrayList和LinkedList的區(qū)別、擴容機制以及底層的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教

ArrayList和LinkedList區(qū)別、擴容機制及底層實現(xiàn)

ArrayList

ArrayList的底層實現(xiàn)為數(shù)組存儲在內(nèi)存中,線程不同步。可通過數(shù)組下標的形式進行查找,所以在查詢方面的效率較為出色,常用在查詢較多的情景下。

LinkedList

LinkedList的底層實現(xiàn)為鏈表形式,也為線程不同步。而鏈表的底層也決定了它在查詢方面不如數(shù)組底層的ArrayList而在指定位置插入等修改操作下,性能優(yōu)于ArrayList。

Vestor

另外還有Vestor,Vestor也是和ArrayList、LinkedList一樣實現(xiàn)了java.util.List接口。最大的區(qū)別在于Vestor是線程同步的,所以在效率方面不如另外兩者,適用于多線程項目中。

ArrayList的擴容機制

/**
? ? ?* Constructs an empty list with the specified initial capacity.
? ? ?*/
? ? public ArrayList(int initialCapacity) {
? ? super();
? ? ? ? if (initialCapacity < 0)
? ? ? ? ? ? throw new IllegalArgumentException("Illegal Capacity: "+
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?initialCapacity);
? ? this.elementData = new Object[initialCapacity];
? ? }

? ? /**
? ? ?* Constructs an empty list with an initial capacity of ten.
? ? ?*/
? ? public ArrayList() {
? ? this(10);
? ? }

翻閱源碼會發(fā)現(xiàn)ArrayList初始化如果不指定大小的時候 初始大小為10。

? ? public void ensureCapacity(int minCapacity) {
? ? modCount++;
? ? int oldCapacity = elementData.length;
? ? if (minCapacity > oldCapacity) {
? ? ? ? Object oldData[] = elementData;
? ? ? ? int newCapacity = (oldCapacity * 3)/2 + 1;
? ? ? ? ? ? if (newCapacity < minCapacity)
? ? ? ? newCapacity = minCapacity;
? ? ? ? ? ? // minCapacity is usually close to size, so this is a win:
? ? ? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity);
? ? }
? ? }

擴容的規(guī)則也在源碼中有體現(xiàn),擴容后的大小= 原始大小+原始大小/2 + 1。在進行插入等操作的時候,如果判斷出大小不夠,會依據(jù)此方法進行擴容。(以上是JDK1.6版本的源碼,在JDK1.7中擴容規(guī)則進行了修改,改為了擴容后的大小= 原始大小+原始大小/2)

LinkedList的擴容機制

由于它的底層是用雙向鏈表實現(xiàn)的,沒有初始化大小,也沒有擴容的機制。

ArrayList和LinkedList(常用方法、底層結構及擴容機制)

1.ArrayList解說

ArrayList初始長度為0(這里以jdk1.8為例),是一個Object類型的空數(shù)組,如下

當?shù)谝淮握{(diào)用add后,長度變?yōu)?0

當數(shù)組首次擴容的10個空間用完需要擴容后,會第二次走grow方法來擴容(每次擴容為1.5倍)

總的來說:

ArrayList初始大小為10,每次1.5倍進行擴容;它的底層是用數(shù)組實現(xiàn)的,所以查詢速度相對LinkedList要快。

2.LinkedList解說

(1)

* LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。

* LinkedList 實現(xiàn) List 接口,能對它進行隊列操作。

* LinkedList 實現(xiàn) Deque 接口,即能將LinkedList當作雙端隊列使用。

* LinkedList 實現(xiàn)了Cloneable接口,即覆蓋了函數(shù)clone(),能克隆。

* LinkedList 實現(xiàn)java.io.Serializable接口,這意味著LinkedList支持序列化,能通過序列化去傳輸。

* LinkedList 是非同步的。

由于它的底層是用雙向鏈表實現(xiàn)的,所以它對元素的增加、刪除效率要比ArrayList好;它是一個雙向鏈表,沒有初始化大小,也沒有擴容的機制,就是一直在前面或者后面新增就好。

(2)LinkedList底層的數(shù)據(jù)結構是基于雙向循環(huán)鏈表的,且頭結點中不存放數(shù)據(jù),如下:

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

header是雙向鏈表的頭節(jié)點,它是雙向鏈表節(jié)點所對應的類Entry的實例。Entry中包含成員變量: previous, next, element。其中,previous是該節(jié)點的上一個節(jié)點,next是該節(jié)點的下一個節(jié)點,element是該

節(jié)點所包含的值。size是雙向鏈表中節(jié)點實例的個數(shù)。

總之,addBefore(E e,Entry<E> entry)實現(xiàn)在entry之前插入由e構造的新節(jié)點。而add(E e)實現(xiàn)在header節(jié)點之前插入由e構造的新節(jié)點。為了便于理解,下面給出插入節(jié)點的示意圖。

總結

以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關文章

  • java文件下載設置中文名稱的實例(response.addHeader)

    java文件下載設置中文名稱的實例(response.addHeader)

    下面小編就為大家分享一篇java文件下載設置中文名稱的實例(response.addHeader),具有很好的參考價值,希望對大家有所幫助
    2017-12-12
  • Java基礎教程之Map遍歷的5種方式

    Java基礎教程之Map遍歷的5種方式

    Map作為Java中的一種集合,以鍵值對的形式存放一批數(shù)據(jù),經(jīng)常會被我們應用在項目中,這篇文章主要給大家介紹了關于Java基礎教程之Map遍歷的5種方式,需要的朋友可以參考下
    2024-01-01
  • 常用的java日期比較和日期計算方法小結

    常用的java日期比較和日期計算方法小結

    這篇文章主要為大家詳細總結了常用的java日期比較和日期計算方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-09-09
  • Spring?this調(diào)用當前類方法無法攔截的示例代碼

    Spring?this調(diào)用當前類方法無法攔截的示例代碼

    這篇文章主要介紹了Spring?this調(diào)用當前類方法無法攔截,通過debug 查看這個proxyService1 和this的區(qū)別,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-03-03
  • Java完整實現(xiàn)記事本代碼

    Java完整實現(xiàn)記事本代碼

    這篇文章主要介紹了Java實現(xiàn)的簡易記事本,較為詳細的分析了基于java實現(xiàn)記事本程序的完整過程,具有一定參考借鑒價值,需要的朋友可以參考下
    2022-06-06
  • response.setHeader各種用法詳解

    response.setHeader各種用法詳解

    本文主要介紹了response.setHeader各種用法。具有很好的參考價值,下面跟著小編一起來看下吧
    2017-03-03
  • IntelliJ IDEA中使用mybatis-generator的示例

    IntelliJ IDEA中使用mybatis-generator的示例

    這篇文章主要介紹了IntelliJ IDEA中使用mybatis-generator,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-04-04
  • Java面試題 從源碼角度分析HashSet實現(xiàn)原理

    Java面試題 從源碼角度分析HashSet實現(xiàn)原理

    這篇文章主要介紹了Java面試題 從源碼角度分析HashSet實現(xiàn)原理?,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07
  • Java批量向PDF文件中添加圖像水印實現(xiàn)細節(jié)

    Java批量向PDF文件中添加圖像水印實現(xiàn)細節(jié)

    這篇文章主要為大家介紹了Java批量向PDF文件中添加圖像水印實現(xiàn)細節(jié),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-05-05
  • java中生產(chǎn)者消費者問題和代碼案例

    java中生產(chǎn)者消費者問題和代碼案例

    大家好,本篇文章主要講的是java中生產(chǎn)者消費者問題和代碼案例,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-02-02

最新評論