ArrayList集合
1.數(shù)據(jù)結(jié)構(gòu)特點
ArrayList底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組,查詢元素速度快,增刪速度稍慢
2.幾個概念:
??? (1)DEFAULT_CAPACITY:??? 表示數(shù)組的初始大小,默認(rèn)10
??? (2)size:表示當(dāng)前數(shù)組的大小
??? (3)modCount:統(tǒng)計當(dāng)前數(shù)組元素被修改的次數(shù),只要修改,就+1
3.空參構(gòu)造方法初始化???
public ArrayList() {
??????? //實際大小為{},長度為0的數(shù)組
??????? ??? this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
??? ?}
說明: ArrayList無參構(gòu)造方法初始化時,默認(rèn)大小是空數(shù)組,并不是大家常說的10,10是在第一次add的時候擴(kuò)容的數(shù)組容量值.
4.第一次添加元素擴(kuò)容原理
java
public boolean add(E e) {
??????? //確保數(shù)組大小是否足夠,不夠執(zhí)行擴(kuò)容,size為當(dāng)前數(shù)組的大小
???????ensureCapacityInternal(size + 1);?// Increments modCount!!
??????? //直接把元素e保存到數(shù)組中
???????elementData[size++] = e;
??????? returntrue;
??? }
java
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)選擇一個較大的值
??????? returnMath.max(DEFAULT_CAPACITY, minCapacity);
??? }
??? returnminCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
??? //記錄修改次數(shù)
??? modCount++;
??? //如果我們期望的最小容量>數(shù)組目前的長度就擴(kuò)容
??? if(minCapacity - elementData.length > 0)
?? ?????grow(minCapacity);
}
private void grow(int minCapacity) {
??? //overflow-conscious code
??? intoldCapacity = elementData.length;
??? //oldCapacity>> 1:是把oldCapacity/2的意思
??? intnewCapacity = oldCapacity + (oldCapacity >> 1);
??? //如果擴(kuò)容后的值<我們期望的值,擴(kuò)容后的值等于我們期望的值
??? if(newCapacity - minCapacity < 0)
???????newCapacity = minCapacity;
??? //如果擴(kuò)容后的值>jvm所能分配的數(shù)組的最大值,那么就用Integer的最大值
??? if(newCapacity - MAX_ARRAY_SIZE > 0)
???????newCapacity = hugeCapacity(minCapacity);
??? //通過復(fù)制數(shù)組擴(kuò)容
??? elementData= Arrays.copyOf(elementData, newCapacity);
}
注意:
??? 1.擴(kuò)容的規(guī)則并不是翻倍,是原來容量大小的1.5倍
??? 2.ArrayList中數(shù)組的最大長度是Integer.MAX_VALUE,超過這個值,JVM就不會給數(shù)組分配內(nèi)存空間了
??? 3.新增元素時,并沒有對值進(jìn)行嚴(yán)格的校驗,所以ArrayList是允許null值的
LinkeList集合
1.數(shù)據(jù)結(jié)構(gòu)特點:
LinkedList底層數(shù)據(jù)結(jié)構(gòu)是一個雙向鏈表,鏈表中的每個節(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)因為是雙向鏈表,只要內(nèi)存空間足夠大,鏈表的大小是沒有限制的
3.鏈表中的元素(節(jié)點)叫做Node,是LinkedList集合的私有靜態(tài)內(nèi)部類,代碼如下:
java
private static class Node {
??????? Eitem;//節(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;
??????? }
??? }
4.add添加節(jié)點(從鏈表尾部添加)
java
public boolean add(E e) {
??? linkLast(e);
??? returntrue;//鏈表節(jié)點數(shù)據(jù)可以重復(fù),所以add方法始終返回true
}
java
//從尾部添加節(jié)點
void linkLast(E e) {
??? //把尾節(jié)點地址存儲在l中
??? finalNode l = last;
??? //創(chuàng)建新的節(jié)點,參數(shù)含義如下
??? //l是新節(jié)點的前一個節(jié)點的地址,當(dāng)前值是尾節(jié)點地址值
??? //e是當(dāng)前新增節(jié)點中保存的數(shù)據(jù),當(dāng)前新增節(jié)點的下一個節(jié)點是null,因為是在末尾添加
??? finalNode 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++;
}
5.get(int index)查詢節(jié)點
java
??? public Eget(int index) {
???????checkElementIndex(index);//檢查索引值是否越界
??????? returnnode(index).item;
??? }
??? private voidcheckElementIndex(int index) {
???? ???if (!isElementIndex(index))
???????????throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
??? }
??? privateboolean isElementIndex(int index) {
??????? returnindex >= 0 && index < size;
??? }
??? 核心根據(jù)索引獲取節(jié)點數(shù)據(jù)的方法
??? 鏈表查詢某個節(jié)點是比較慢的,需要挨個查找才可以
java
根據(jù)鏈表索引位置查詢元素
Node node(int index) {
??? //如果index處于鏈表的前半部分,從頭開始查,size>>1 是 size/2的意思
??? if (index< (size >> 1)) {
???????Node x = first;
??????? //知道for循環(huán)到index的前一個node停止
??????? for (inti = 0; i < index; i++)????????????
?????????? ?x = x.next;
??????? returnx;
??? } else {
??????? //如果index處于鏈表的后半部分,從尾開始查
???????Node x = last;
??????? //知道for循環(huán)到index的后一個node停止
??????? for (inti = size - 1; i > index; i--)
??????????? x =x.prev;
??????? returnx;
??? }
}
從源碼中發(fā)現(xiàn),LinkedList并沒有采用從頭循環(huán)到尾的做法,而是采取了簡單二分查找法,
首先看index是在鏈表的左半部分還是右半部分.如果是在左半部分,就從左側(cè)開始找,
如果實在鏈表的有伴部分,就從右側(cè)開始找.這種方式,循環(huán)的次數(shù)至少降低了一半,提高查詢性能.
