教育行業(yè)A股IPO第一股（股票代碼 003032）

全國(guó)咨詢/投訴熱線：400-618-4000

ArrayList集合源碼分析【java培訓(xùn)】

更新時(shí)間:2020年07月08日16時(shí)46分 來(lái)源:傳智播客 瀏覽次數(shù):

1、數(shù)據(jù)結(jié)構(gòu)特點(diǎn)

ArrayList底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組,查詢?cè)厮俣瓤?增刪速度稍慢  

2、幾個(gè)概念:
(1)DEFAULT_CAPACITY：表示數(shù)組的初始大小，默認(rèn)10
(2)size: 表示當(dāng)前數(shù)組的大小
(3)modCount: 統(tǒng)計(jì)當(dāng)前數(shù)組元素被修改的次數(shù),只要修改,就+1

3.空參構(gòu)造方法初始化

public ArrayList() {
 //實(shí)際大小為{},長(zhǎng)度為0的數(shù)組
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

說(shuō)明: ArrayList無(wú)參構(gòu)造方法初始化時(shí),默認(rèn)大小是空數(shù)組,并不是大家常說(shuō)的10,
10是在第一次add的時(shí)候擴(kuò)容的數(shù)組容量值.

4、第一次添加元素?cái)U(kuò)容原理

public boolean add(E e) {
 //確保數(shù)組大小是否足夠,不夠執(zhí)行擴(kuò)容,size為當(dāng)前數(shù)組的大小
       ensureCapacityInternal(size + 1);  // Increments modCount!!
 //直接把元素e保存到數(shù)組中
       elementData[size++] = e;
       return true;
   }

private void ensureCapacityInternal(int minCapacity) {
   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果是空數(shù)組{}
   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 //在最小容量minCapacity和DEFAULT_CAPACITY(10)選擇一個(gè)較大的值
       return Math.max(DEFAULT_CAPACITY, minCapacity);
   }
   return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
//記錄修改次數(shù)
   modCount++;
//如果我們期望的最小容量>數(shù)組目前的長(zhǎng)度就擴(kuò)容
   if (minCapacity - elementData.length > 0)
       grow(minCapacity);
}

private void grow(int minCapacity) {
   // overflow-conscious code
   int oldCapacity = elementData.length;
//oldCapacity >> 1: 是把oldCapacity/2的意思
   int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果擴(kuò)容后的值<我們期望的值,擴(kuò)容后的值等于我們期望的值
   if (newCapacity - minCapacity < 0)
       newCapacity = minCapacity;
//如果擴(kuò)容后的值>jvm所能分配的數(shù)組的最大值,那么就用Integer的最大值
   if (newCapacity - MAX_ARRAY_SIZE > 0)
       newCapacity = hugeCapacity(minCapacity);
   //通過(guò)復(fù)制數(shù)組擴(kuò)容
   elementData = Arrays.copyOf(elementData, newCapacity);
}

注意:
1.擴(kuò)容的規(guī)則并不是翻倍，是原來(lái)容量大小的1.5倍
2.ArrayList中數(shù)組的最大長(zhǎng)度是Integer.MAX_VALUE,超過(guò)這個(gè)值,JVM就不會(huì)給數(shù)組分配內(nèi)存空間了
3.新增元素時(shí)，并沒(méi)有對(duì)值進(jìn)行嚴(yán)格的校驗(yàn)，所以ArrayList是允許null值的

LinkeList集合

1.數(shù)據(jù)結(jié)構(gòu)特點(diǎn):

LinkedList底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)雙向鏈表,鏈表中的每個(gè)節(jié)點(diǎn)都可以查找前一個(gè)節(jié)點(diǎn)或者向后查找后一個(gè)節(jié)點(diǎn)

2.幾個(gè)概念:

(1)鏈表每個(gè)節(jié)點(diǎn)叫做Node,Node有prev屬性,代表前一個(gè)節(jié)點(diǎn)的地址,next屬性代表后一個(gè)節(jié)點(diǎn)的地址
(2)first是雙向鏈表的頭節(jié)點(diǎn),它的前一個(gè)節(jié)點(diǎn)是null
(3)last是雙向鏈表的尾節(jié)點(diǎn),它的后一個(gè)節(jié)點(diǎn)是null
(4)鏈表中如果沒(méi)有數(shù)據(jù),first和last都null
(5)因?yàn)槭请p向鏈表,只要內(nèi)存空間足夠大,鏈表的大小是沒(méi)有限制的

3.鏈表中的元素(節(jié)點(diǎn))叫做Node,是LinkedList集合的私有靜態(tài)內(nèi)部類(lèi)，代碼如下:

private static class Node {
       E item;//節(jié)點(diǎn)數(shù)據(jù)
       Node next;//下一個(gè)節(jié)點(diǎn)的地址
       Node prev;//前一個(gè)節(jié)點(diǎn)的地址
 //初始化參數(shù)順序是: 前一個(gè)節(jié)點(diǎn)地址,節(jié)點(diǎn)本身的數(shù)據(jù),后一個(gè)節(jié)點(diǎn)地址
       Node(Node prev, E element, Node next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }

4.add添加節(jié)點(diǎn)(從鏈表尾部添加)

public boolean add(E e) {
linkLast(e);
return true;//鏈表節(jié)點(diǎn)數(shù)據(jù)可以重復(fù),所以add方法始終返回true
}

//從尾部添加節(jié)點(diǎn)
void linkLast(E e) {
//把尾節(jié)點(diǎn)地址存儲(chǔ)在l中
   final Node l = last;
//創(chuàng)建新的節(jié)點(diǎn),參數(shù)含義如下
//l是新節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的地址,當(dāng)前值是尾節(jié)點(diǎn)地址值
//e是當(dāng)前新增節(jié)點(diǎn)中保存的數(shù)據(jù),當(dāng)前新增節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是null,因?yàn)槭窃谀┪蔡砑?br />    final Node newNode = new Node<>(l, e, null);
//last指向新增節(jié)點(diǎn)(新增節(jié)點(diǎn)作為尾節(jié)點(diǎn))
   last = newNode;
//如果鏈表為空(第一次添加節(jié)點(diǎn))(l是尾節(jié)點(diǎn),尾節(jié)點(diǎn)為空,鏈表即空),頭部和尾部都是指向同一個(gè)節(jié)點(diǎn),都是新建的節(jié)點(diǎn)
   if (l == null)
       first = newNode;
   else
 //鏈表不是空(非第一次添加節(jié)點(diǎn)),把添加新節(jié)點(diǎn)之前的尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新添加的節(jié)點(diǎn)
       l.next = newNode;
//節(jié)點(diǎn)數(shù)+1
   size++;
//鏈表的實(shí)際修改次數(shù)+1
   modCount++;
}

5.get(int index)查詢節(jié)點(diǎn)

public E get(int index) {
       checkElementIndex(index);//檢查索引值是否越界
       return node(index).item;
   }
private void checkElementIndex(int index) {
       if (!isElementIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }
private boolean isElementIndex(int index) {
       return index >= 0 && index < size;
   }


核心根據(jù)索引獲取節(jié)點(diǎn)數(shù)據(jù)的方法
鏈表查詢某個(gè)節(jié)點(diǎn)是比較慢的，需要挨個(gè)查找才可以

根據(jù)鏈表索引位置查詢?cè)?/span>

Node node(int index) {
   //如果index處于鏈表的前半部分,從頭開(kāi)始查,size>>1 是 size/2的意思
if (index < (size >> 1)) {
 
       Node x = first;
 //知道for循環(huán)到index的前一個(gè)node停止
       for (int i = 0; i < index; i++)    
           x = x.next;
       return x;
   } else {
 //如果index處于鏈表的后半部分,從尾開(kāi)始查
       Node x = last;
 //知道for循環(huán)到index的后一個(gè)node停止
       for (int i = size - 1; i > index; i--)
           x = x.prev;
       return x;
   }
}


從源碼中發(fā)現(xiàn),LinkedList并沒(méi)有采用從頭循環(huán)到尾的做法，而是采取了簡(jiǎn)單二分查找法，首先看index是在鏈表的左半部分還是右半部分。如果是在左半部分,就從左側(cè)開(kāi)始找，如果實(shí)在鏈表的有伴部分，就從右側(cè)開(kāi)始找。這種方式,循環(huán)的次數(shù)至少降低了一半，提高查詢性能。

猜你喜歡：

Java中級(jí)程序員課程

JSP是什么？JSP是怎么運(yùn)行的？

Java面向?qū)ο笫鞘裁匆馑?

JDK下載安裝與環(huán)境變量配置圖文教程【超詳細(xì)】

java遞歸是什么意思,怎么用

Java中switch條件語(yǔ)句的用法

正則化是什么意思?正則化技術(shù)解析

JDBC是什么?jdbc常用API有哪些?

什么是Java,Java有幾個(gè)技術(shù)平臺(tái)?

Java語(yǔ)言有什么特點(diǎn)?

0 分享到：
和我們?cè)诰€交談！