list集合取值方法?ArrayList底層數據結構是一個數組,查詢元素速度快,增删速度稍慢，下面我們就來說一說關于list集合取值方法?我們一起去了解并探讨一下這個問題吧!

list集合取值方法

1.數據結構特點

ArrayList底層數據結構是一個數組,查詢元素速度快,增删速度稍慢

2.幾個概念:

(1)DEFAULT_CAPACITY: 表示數組的初始大小,默認10

(2)size: 表示當前數組的大小

(3)modCount: 統計當前數組元素被修改的次數,隻要修改,就 1

3.空參構造方法初始化

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

說明: ArrayList無參構造方法初始化時,默認大小是空數組,并不是大家常說的10,

10是在第一次add的時候擴容的數組容量值.

3.第一次添加元素擴容原理

​

public boolean add(E e) { //确保數組大小是否足夠,不夠執行擴容,size為當前數組的大小 ensureCapacityInternal(size 1); // Increments modCount!! //直接把元素e保存到數組中 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) { //在最小容量minCapacity和DEFAULT_CAPACITY(10)選擇一個較大的值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { //記錄修改次數 modCount ; //如果我們期望的最小容量>數組目前的長度就擴容 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所能分配的數組的最大值,那麼就用Integer的最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //通過複制數組擴容 elementData = Arrays.copyOf(elementData, newCapacity); }

注意:

1.擴容的規則并不是翻倍,是原來容量大小的1.5倍

2.ArrayList中數組的最大長度是Integer.MAX_VALUE,超過這個值,JVM就不會給數組分配内存空間了

3.新增元素時,并沒有對值進行嚴格的校驗,所以ArrayList是允許null值的

LinkeList集合

1.數據結構特點:

LinkedList底層數據結構是一個雙向鍊表,鍊表中的每個節點都可以查找前一個節點或者向後查找後一個節點

2.幾個概念:

(1)鍊表每個節點叫做node,Node有prev屬性,代表前一個節點的地址,next屬性代表後一個節點的地址

(2)first是雙向鍊表的頭節點,它的前一個節點是null

(3)last是雙向鍊表的尾節點,它的後一個節點是null

(4)鍊表中如果沒有數據,first和last都null

(5)因為是雙向鍊表,隻要内存空間足夠大,鍊表的大小是沒有限制的

3.鍊表中的元素(節點)叫做Node,是LinkedList集合的私有靜态内部類,代碼如下:

private static class Node<E> { E item;//節點數據 Node<E> next;//下一個節點的地址 Node<E> prev;//前一個節點的地址 //初始化參數順序是: 前一個節點地址,節點本身的數據,後一個節點地址 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

4.add添加節點(從鍊表尾部添加)

public boolean add(E e) { linkLast(e); return true;//鍊表節點數據可以重複,所以add方法始終返回true }

//從尾部添加節點 void linkLast(E e) { //把尾節點地址存儲在l中 final Node<E> l = last; //創建新的節點,參數含義如下 //l是新節點的前一個節點的地址,當前值是尾節點地址值 //e是當前新增節點中保存的數據,當前新增節點的下一個節點是null,因為是在末尾添加 final Node<E> newNode = new Node<>(l, e, null); //last指向新增節點(新增節點作為尾節點) last = newNode; //如果鍊表為空(第一次添加節點)(l是尾節點,尾節點為空,鍊表即空),頭部和尾部都是指向同一個節點,都是新建的節點 if (l == null) first = newNode; else //鍊表不是空(非第一次添加節點),把添加新節點之前的尾節點的下一個節點指向新添加的節點 l.next = newNode; //節點數 1 size ; //鍊表的實際修改次數 1 modCount ; }

5.get(int index)查詢節點

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; }

​核心根據索引獲取節點數據的方法

鍊表查詢某個節點是比較慢的,需要挨個查找才可以

根據鍊表索引位置查詢元素 Node<E> node(int index) { //如果index處于鍊表的前半部分,從頭開始查,size>>1 是 size/2的意思 if (index < (size >> 1)) { Node<E> x = first; //知道for循環到index的前一個node停止 for (int i = 0; i < index; i ) x = x.next; return x; } else { //如果index處于鍊表的後半部分,從尾開始查 Node<E> x = last; //知道for循環到index的後一個node停止 for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

從源碼中發現,LinkedList并沒有采用從頭循環到尾的做法,而是采取了簡單二分查找法,

首先看index是在鍊表的左半部分還是右半部分.如果是在左半部分,就從左側開始找,

如果實在鍊表的有伴部分,就從右側開始找.這種方式,循環的次數至少降低了一半,提高查詢性能.