更新時(shí)間:2020-07-08 來源:黑馬程序員 瀏覽量:
ArrayList底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組,查詢?cè)厮俣瓤?增刪速度稍慢
3.空參構(gòu)造方法初始化
public ArrayList() { //實(shí)際大小為{},長度為0的數(shù)組 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }說明: ArrayList無參構(gòu)造方法初始化時(shí),默認(rèn)大小是空數(shù)組,并不是大家常說的10,
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ù)組目前的長度就擴(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); //通過復(fù)制數(shù)組擴(kuò)容 elementData = Arrays.copyOf(elementData, newCapacity); }
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)的地址3.鏈表中的元素(節(jié)點(diǎn))叫做Node,是LinkedList集合的私有靜態(tài)內(nèi)部類,代碼如下:
private static class Node<E> { E item;//節(jié)點(diǎn)數(shù)據(jù) Node<E> next;//下一個(gè)節(jié)點(diǎn)的地址 Node<E> prev;//前一個(gè)節(jié)點(diǎn)的地址 //初始化參數(shù)順序是: 前一個(gè)節(jié)點(diǎn)地址,節(jié)點(diǎn)本身的數(shù)據(jù),后一個(gè)節(jié)點(diǎn)地址 Node(Node<E> prev, E element, Node<E> 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<E> 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)槭窃谀┪蔡砑? final Node<E> 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; }
Node<E> node(int index) { //如果index處于鏈表的前半部分,從頭開始查,size>>1 是 size/2的意思 if (index < (size >> 1)) { Node<E> x = first; //知道for循環(huán)到index的前一個(gè)node停止 for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index處于鏈表的后半部分,從尾開始查 Node<E> x = last; //知道for循環(huán)到index的后一個(gè)node停止 for (int i = size - 1; i > index; i--) x = x.prev; return x; } }