JavaEE
鴻蒙應用開發(fā)
HTML&JS+前端
Python+大數(shù)據(jù)開發(fā)
人工智能開發(fā)
電商視覺設計
軟件測試
新媒體+短視頻
集成電路應用開發(fā)
C/C++
狂野架構師
IP短視頻
ArrayList集合源碼分析【java培訓】
更新時間:2020年07月08日16時46分 來源:傳智播客 瀏覽次數(shù):
1、數(shù)據(jù)結構特點
(1)DEFAULT_CAPACITY：表示數(shù)組的初始大小，默認10
(2)size: 表示當前數(shù)組的大小
(3)modCount: 統(tǒng)計當前數(shù)組元素被修改的次數(shù),只要修改,就+1
//實際大小為{},長度為0的數(shù)組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
說明: ArrayList無參構造方法初始化時,默認大小是空數(shù)組,并不是大家常說的10,
10是在第一次add的時候擴容的數(shù)組容量值.
//確保數(shù)組大小是否足夠,不夠執(zhí)行擴容,size為當前數(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)選擇一個較大的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//記錄修改次數(shù)
modCount++;
//如果我們期望的最小容量>數(shù)組目前的長度就擴容
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);
//如果擴容后的值<我們期望的值,擴容后的值等于我們期望的值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果擴容后的值>jvm所能分配的數(shù)組的最大值,那么就用Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//通過復制數(shù)組擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
注意:
1.擴容的規(guī)則并不是翻倍，是原來容量大小的1.5倍
2.ArrayList中數(shù)組的最大長度是Integer.MAX_VALUE,超過這個值,JVM就不會給數(shù)組分配內存空間了
3.新增元素時，并沒有對值進行嚴格的校驗，所以ArrayList是允許null值的
(2)first是雙向鏈表的頭節(jié)點,它的前一個節(jié)點是null
(3)last是雙向鏈表的尾節(jié)點,它的后一個節(jié)點是null
(4)鏈表中如果沒有數(shù)據(jù),first和last都null
(5)因為是雙向鏈表,只要內存空間足夠大,鏈表的大小是沒有限制的
{
E item;//節(jié)點數(shù)據(jù)
Node next;//下一個節(jié)點的地址
Node prev;//前一個節(jié)點的地址
//初始化參數(shù)順序是: 前一個節(jié)點地址,節(jié)點本身的數(shù)據(jù),后一個節(jié)點地址
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
linkLast(e);
return true;//鏈表節(jié)點數(shù)據(jù)可以重復,所以add方法始終返回true
} //從尾部添加節(jié)點
void linkLast(E e) {
//把尾節(jié)點地址存儲在l中
final Node l = last;
//創(chuàng)建新的節(jié)點,參數(shù)含義如下
//l是新節(jié)點的前一個節(jié)點的地址,當前值是尾節(jié)點地址值
//e是當前新增節(jié)點中保存的數(shù)據(jù),當前新增節(jié)點的下一個節(jié)點是null,因為是在末尾添加
final Node newNode = new Node<>(l, e, null);
//last指向新增節(jié)點(新增節(jié)點作為尾節(jié)點)
last = newNode;
//如果鏈表為空(第一次添加節(jié)點)(l是尾節(jié)點,尾節(jié)點為空,鏈表即空),頭部和尾部都是指向同一個節(jié)點,都是新建的節(jié)點
if (l == null)
first = newNode;
else
//鏈表不是空(非第一次添加節(jié)點),把添加新節(jié)點之前的尾節(jié)點的下一個節(jié)點指向新添加的節(jié)點
l.next = newNode;
//節(jié)點數(shù)+1
size++;
//鏈表的實際修改次數(shù)+1
modCount++;
}
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é)點數(shù)據(jù)的方法
鏈表查詢某個節(jié)點是比較慢的，需要挨個查找才可以 根據(jù)鏈表索引位置查詢元素
Node node(int index) {
//如果index處于鏈表的前半部分,從頭開始查,size>>1 是 size/2的意思
if (index < (size >> 1)) {
Node x = first;
//知道for循環(huán)到index的前一個node停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index處于鏈表的后半部分,從尾開始查
Node x = last;
//知道for循環(huán)到index的后一個node停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
從源碼中發(fā)現(xiàn),LinkedList并沒有采用從頭循環(huán)到尾的做法，而是采取了簡單二分查找法，首先看index是在鏈表的左半部分還是右半部分。如果是在左半部分,就從左側開始找，如果實在鏈表的有伴部分，就從右側開始找。這種方式,循環(huán)的次數(shù)至少降低了一半，提高查詢性能。
猜你喜歡：
ArrayList底層數(shù)據(jù)結構是一個數(shù)組,查詢元素速度快,增刪速度稍慢
2、幾個概念:(1)DEFAULT_CAPACITY：表示數(shù)組的初始大小，默認10
(2)size: 表示當前數(shù)組的大小
(3)modCount: 統(tǒng)計當前數(shù)組元素被修改的次數(shù),只要修改,就+1
3.空參構造方法初始化
public ArrayList() {//實際大小為{},長度為0的數(shù)組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
說明: ArrayList無參構造方法初始化時,默認大小是空數(shù)組,并不是大家常說的10,
10是在第一次add的時候擴容的數(shù)組容量值.
4、第一次添加元素擴容原理
public boolean add(E e) {//確保數(shù)組大小是否足夠,不夠執(zhí)行擴容,size為當前數(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)選擇一個較大的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//記錄修改次數(shù)
modCount++;
//如果我們期望的最小容量>數(shù)組目前的長度就擴容
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);
//如果擴容后的值<我們期望的值,擴容后的值等于我們期望的值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果擴容后的值>jvm所能分配的數(shù)組的最大值,那么就用Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//通過復制數(shù)組擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
注意:
1.擴容的規(guī)則并不是翻倍，是原來容量大小的1.5倍
2.ArrayList中數(shù)組的最大長度是Integer.MAX_VALUE,超過這個值,JVM就不會給數(shù)組分配內存空間了
3.新增元素時，并沒有對值進行嚴格的校驗，所以ArrayList是允許null值的
LinkeList集合
1.數(shù)據(jù)結構特點:
LinkedList底層數(shù)據(jù)結構是一個雙向鏈表,鏈表中的每個節(jié)點都可以查找前一個節(jié)點或者向后查找后一個節(jié)點
2.幾個概念:
(1)鏈表每個節(jié)點叫做Node,Node有prev屬性,代表前一個節(jié)點的地址,next屬性代表后一個節(jié)點的地址(2)first是雙向鏈表的頭節(jié)點,它的前一個節(jié)點是null
(3)last是雙向鏈表的尾節(jié)點,它的后一個節(jié)點是null
(4)鏈表中如果沒有數(shù)據(jù),first和last都null
(5)因為是雙向鏈表,只要內存空間足夠大,鏈表的大小是沒有限制的
3.鏈表中的元素(節(jié)點)叫做Node,是LinkedList集合的私有靜態(tài)內部類，代碼如下:
private static class NodeE item;//節(jié)點數(shù)據(jù)
Node
Node
//初始化參數(shù)順序是: 前一個節(jié)點地址,節(jié)點本身的數(shù)據(jù),后一個節(jié)點地址
Node(Node
this.item = element;
this.next = next;
this.prev = prev;
}
}
4.add添加節(jié)點(從鏈表尾部添加)
public boolean add(E e) {linkLast(e);
return true;//鏈表節(jié)點數(shù)據(jù)可以重復,所以add方法始終返回true
} //從尾部添加節(jié)點
void linkLast(E e) {
//把尾節(jié)點地址存儲在l中
final Node
//創(chuàng)建新的節(jié)點,參數(shù)含義如下
//l是新節(jié)點的前一個節(jié)點的地址,當前值是尾節(jié)點地址值
//e是當前新增節(jié)點中保存的數(shù)據(jù),當前新增節(jié)點的下一個節(jié)點是null,因為是在末尾添加
final Node
//last指向新增節(jié)點(新增節(jié)點作為尾節(jié)點)
last = newNode;
//如果鏈表為空(第一次添加節(jié)點)(l是尾節(jié)點,尾節(jié)點為空,鏈表即空),頭部和尾部都是指向同一個節(jié)點,都是新建的節(jié)點
if (l == null)
first = newNode;
else
//鏈表不是空(非第一次添加節(jié)點),把添加新節(jié)點之前的尾節(jié)點的下一個節(jié)點指向新添加的節(jié)點
l.next = newNode;
//節(jié)點數(shù)+1
size++;
//鏈表的實際修改次數(shù)+1
modCount++;
}
5.get(int index)查詢節(jié)點
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é)點數(shù)據(jù)的方法
鏈表查詢某個節(jié)點是比較慢的，需要挨個查找才可以 根據(jù)鏈表索引位置查詢元素
Node
//如果index處于鏈表的前半部分,從頭開始查,size>>1 是 size/2的意思
if (index < (size >> 1)) {
Node
//知道for循環(huán)到index的前一個node停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index處于鏈表的后半部分,從尾開始查
Node
//知道for循環(huán)到index的后一個node停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
從源碼中發(fā)現(xiàn),LinkedList并沒有采用從頭循環(huán)到尾的做法，而是采取了簡單二分查找法，首先看index是在鏈表的左半部分還是右半部分。如果是在左半部分,就從左側開始找，如果實在鏈表的有伴部分，就從右側開始找。這種方式,循環(huán)的次數(shù)至少降低了一半，提高查詢性能。
猜你喜歡：
最新資訊
0
分享到：
文章列表.jpg)
據(jù)學科列表頁右側.png)
江蘇傳智播客教育科技股份有限公司 版權所有Copyright 2006-2024 All Rights Reserved 蘇ICP備16007882號營業(yè)執(zhí)照增值電信業(yè)務經(jīng)營許可證出版物經(jīng)營許可證
蘇公網(wǎng)安備 32132202001156號