?

可增長數(shù)組結構

實現(xiàn)：
　　1. 內部采用數(shù)組的方式。
　　　　1.1 添加元素，會每次校驗容量是否滿足， 擴容規(guī)則是當前數(shù)組長度+當前數(shù)組長度的二分之一。容量上限是Integer.MAX_VALUE。 copy使用Arrays.copy的api
　　　　1.2 刪除元素
　　　　　　1.2.1 通過對象刪除。遍歷數(shù)組，刪除第一個匹配的對象
　　　　　　1.2.3 通過下標刪除。判斷下標是否越界。
　　　　　　　　使用 System.arraycopy進行copy, 并將元素的最后一位設置為null.供gc回收
　　2. 內部是同步[modCount]
　　　　2.1 ArrayList數(shù)據(jù)結構變化的時候，都會將modCount++。
　　　　2.2 采用Iterator遍歷的元素， next()會去檢查集合是否被修改[checkForComodification]，如果集合變更會拋出異常
　　　　類似于數(shù)據(jù)庫層面的 樂觀鎖 機制。 可以通過 Iterator的api去刪除元素
3. 數(shù)組結構，內部存儲數(shù)據(jù)是有序的，并且數(shù)據(jù)可以為null,支持添加重復數(shù)據(jù)

modCount作用：
https://www.cnblogs.com/zuochengsi-9/p/7050351.html

?

源碼分析

package xin.rtime.collections.list;import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;// 模擬ArrayList的實現(xiàn)
public class ArrayList<E> {private transient int modCount = 0;    // 修改次數(shù)private transient Object[] elementData; // 數(shù)據(jù)集合private static final Object[] EMPTY_ELEMENTDATA = {}; // 默認空數(shù)組private int size; // 數(shù)組實際個數(shù)private static final int DEFAULT_CAPACITY = 10; // 默認長度private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  // 數(shù)組最大長度// 默認構造函數(shù)public ArrayList() {elementData = EMPTY_ELEMENTDATA; // 默認等于空集合
    }// 初始化指定長度public ArrayList(int initialCapacity) {if (initialCapacity < 0) // 長度小于0 拋異常throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);this.elementData = new Object[initialCapacity]; // new一個指定長度的對象數(shù)組
    }// 添加元素public boolean add(E e) {ensureCapacityInternal(size + 1);elementData[size++] = e; // 放置添加的元素return true;}// 刪除元素public boolean remove(E e) {if (e == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {  // 刪除 null
                    fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (e.equals(elementData[index])) {   // eqals比較
                    fastRemove(index);return true;}}return false;}private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;      // 當前size - index - 1    數(shù)組從0開始if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);   // system arraycopyelementData[--size] = null; // clear to let GC do its work   gc回收
    }public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its workreturn oldValue;}// 獲取元素public E get(int index) {rangeCheck(index);   // index校驗return elementData(index);}@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private String outOfBoundsMsg(int index) {return "Index: "+index+", Size: "+size;}// 返回元素個數(shù)public int size() {return size;}// 判斷當前容量是否能否裝下元素private void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) // 空集合minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 10 傳入的
ensureExplicitCapacity(minCapacity);}// 提供外部遍歷public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E> {int cursor;       // index of next element to return    游標int lastRet = -1; // index of last element returned; -1 if no such    最后元素下標int expectedModCount = modCount;  // 當前數(shù)組修改次數(shù)public boolean hasNext() {return cursor != size;  // 當前游標是否等于size
        }@SuppressWarnings("unchecked")public E next() {checkForComodification();   // 檢查數(shù)組是否被操作過int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();  // 檢查集合是否被操作過try {ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}// 判斷容量 擴容private void ensureExplicitCapacity(int minCapacity) {modCount++;  // 修改+1if (minCapacity - elementData.length > 0) // 當前長度 大于 數(shù)組長度
            grow(minCapacity);}public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}private void rangeCheckForAdd(int index) {if (index > size || index < 0)   // index 超出 size  或者  index 小于0 ---> 數(shù)組越界throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}public E set(int index, E element) {rangeCheck(index);   // 校驗index是否滿足
E oldValue = elementData(index);elementData[index] = element;return oldValue;}/**<<      :     左移運算符，num << 1,相當于num乘以2>>      :     右移運算符，num >> 1,相當于num除以2>>>    :     無符號右移，忽略符號位，空位都以0補齊*/// 擴容private void grow(int minCapacity) {int oldCapacity = elementData.length; // 當前數(shù)組長度int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新容量大小 = 原來長度 + 原來長度 右移一位，除以2if (newCapacity - minCapacity < 0)  // 新長度 - 傳的長度 小于  0newCapacity = minCapacity;   //
        if (newCapacity - MAX_ARRAY_SIZE > 0)  // 當前長度超出最大容量newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);   // 拷貝原來數(shù)據(jù)
    }// 判斷容量private int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}}

?

轉載于:https://www.cnblogs.com/LuisYang/p/10034514.html

總結

以上是生活随笔為你收集整理的ArrayList源码学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。