ArrayList的结构属于线性表结构,基于数组实现,是一个动态的数组,容量能够自动的增长,支持序列化,但是不是线程安全的

ArrayList#add()

我们先从add()开始

ArrayList#add()

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

首先进入了ensureCapacityInternal(),然后将add的参数放到elementData数组的size++位置上,最后返回true。size是arrayList的集合数据数量,前面我们有说ArrayList是一个数组,具体表现为elementData,所以add()的后两句代码很清晰,将ArrayList的长度即elementData的长度size自增1,然后将要add的参数放入到elementData自增后的size位置上。
回过头来看ensureCapacityInternal(),入参为当前数组长度加一。

ArrayList#ensureCapacityInternal()

// 默认空数组实现  
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 // 默认数组容量 
 private static final int DEFAULT_CAPACITY = 10;
 
 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

里面有一个判断,如果elementData数组是一个默认的空数组,也就是刚初始化完毕或者clear之后的数组,一句话,此时的数组即集合是空的,没有任何数据在里面,此时会在默认数组长度以及首次添加数据时的size+1之间取最大值,所以minCapacity的值为10,最后进入到ensureExplicitCapacity()中。

ArrayList#ensureExplicitCapacity():

// 代表集合被修改的次数,主要是用于在检测在迭代集合的过程中,集合是否发生了变化,下面在说迭代的时候会说到
protected transient int modCount = 0;

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount自增1,然后判断当前数组是否还有多余的位置,即添加元素后的要求的数组长度是否大于数组的本身的长度,如果否的话,不进行任何操作,可以直接添加元素到数组之后只能怪,如果是的话则进入grow()进行扩容操作

ArrayList#grow():

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = 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);
    }

首先获取到数组的长度,此时的数组是长度为0默认空数组,即oldCapacity = 0,0右移一位还是0,所以newCapacity = 0,默认的数组长度即minCapacity = 10,所以第一个判断条件成立,此时的newCapacity = 10;第二个判断条件,MAX_ARRAY_SIZE是Integer.MAX_VALUE - 8,newCapacity - MAX_ARRAY_SIZE > 0即数组容量大于这个值,在Android中基本不存在这么大的数组,所以这里暂不考虑,最后一行拷贝旧数组并把数组长度传进去,生成 一个新的数组并赋值给elementData。
重新捋一下grow():

首先拿到当前数组的长度,并由此得到当前数组的长度的1.5倍数值,并赋予newCapacity,如果被要求的数组长度(size + 1)大于当前数组长度的1.5倍(1.5 * size),则将minCapacity(size + 1)作为被扩展的数组的目标长度,然后进行拷贝扩容;如果被要求的数组长度(size + 1)小于当前数组的1.5倍值(size * 1.5)则将当前数组长度的1.5倍值作为目标数组长度进行拷贝扩容操作

最后回到add()中,将要加入的add放入到新创建的elementData[]中

ArrayList#get(int Index)

get()没有什么可以说的内容,普通的数组取值

 public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

ArrayList#set(int index,E element)

set也没有什么可说的,注意的就是入参的index要小于数组中的元素数量size,因为set()主要的作用的元素替换,替换掉指定位置上的元素,并将传入的元素,赋予此位置,然后返回此位置上的原始元素。

 public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

ArrayList# remove(int index)

根据指定的下标删除该位置上的元素

  public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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 work

        return oldValue;
    }

首先获取到该位置上的元素,然后以此下标(index + 1)为节点,截取并重新拷贝生成一个新的数组(保证数组的连续性),元素数量减一(size--),此时数组的最后两个元素是相同的,只要将最后一个元素的值设置为空即可,最后返回原始元素

ArrayList#remove(Object o)

删除指定元素

  public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   }

   private void fastRemove(int index) {
       modCount++;
       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 work
   }

这里暂且不讨论为null的情况,首先遍历数组找到与指定元素相同的元素,并将下标传递给fastRemove(),此方法跟remove()基本一致,同样以该下标为节点,拷贝复制一份新的数组,并删除最后一个重复元素即可。
ps:

我们可以看到,删除指定元素的时候,只是遍历了一次,如果有就删除找到的第一个指定元素,然后返回,如果arryList中有多个重复元素的话,只能删除数组靠前的元素,其他元素则不变

关于其他的一些操作性的方法这里就不多说了,其实主要就是对数组的增删改查,通过上面几个方法的说明,可以看出,ArrayList本质就是一个数组,不过在数组长度不满足需求时,会自动的“扩容”,每次扩容是原容量的1.5倍(容量为1时例外,此时的容量为1 + 1 ),删除指定位置元素或指定元素以,都会重新的拷贝数组进而生成新的数组,所以在增删操作上相比于查询修改花费的时间要长一些

下面来说ArrayList的迭代器

Iterator

我们平获取迭代器的方法是ArrayList.iterator()
ArrayList#iterator()

public Iterator<E> iterator() {
        return new Itr(); //直接返回了一个Itr对象,Itr的实现就在ArrayList中
    }

Itr继承于Itorator,并重写了它的四个方法:

hasNext 判断当前迭代器还有下一个元素
next 获取到当前迭代器的下一个元素
remove 删除当前迭代器中所持有的元素
forEachRemaining 暂且不知

Itr中还有四个成员变量：

limit 当前ArrayList中的元素数量
cursor 遍历到的当前元素的下个元素的下标,主要用来与limit对比,如果比limit小,则说明当前的元素后面还有其他元素,否则的话说明当前元素为最后一个元素
lastRet 最后一次获取next值时的下标,即当前便利到的当前元素的下标
expectedModCount 前面我们再说ArrayList#add()时有一个遗留问题,即modCount的作用,主要是用来判断在迭代过程中,是否对集合进行了其他的操作,如果一致,则说明迭代过程中没有对集合进行其他的操作,否则会抛出异常

我们先来回忆下,平常迭代器的用法:

        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("chuan");
        arrayList.add("chuan");
        arrayList.add("chuan");
        Iterator<String> iterator = arrayList.iterator();
        while (iterator.hasNext()){
            String str = iterator.next();
            Log.i("chuan", str);
        }

ok,我们来看hasNext()以及next()

ArrayList#Itr#hasNext()

// 通过cursor与limit做对比,来判断是否有余下的元素
  public boolean hasNext() {
        return cursor < limit;
    }

ArrayList#Itr#next()

        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

首先对modeCount进行判断,是否在在获取到迭代器之后有其他的对集合的操作,如果有则抛出ConcurrentModificationException;然后对cursor进行判断,如果cursor >= limit则抛出NoSuchElementException,之后再获取到当前ArrayList的elementData数组,然后在原始cursor的值的基础上+1,获取到新的cursor的值,并将原始的cursor的值赋予lastRet,最后根据lastRet获取到elementData中的元素

仅仅从这两个方法来看,更像是一个普通的for循环,cursor为index值

继续往下看:
ArrayList#Itr#remove()

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
                limit--;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

前面的两个判断不再多说,这里会调用当前ArrayList的remove方法,入参为lastRet,同时会同步Itr的成员变量

cursor被赋值lastRet,因为是删除操作,所以cursor会减一,也就是lastRet
lastRet = -1,上面有一个判断,lastRet<0状态下,不能进行remove操作,也就是说每一次next只能进行一次Remove操作,即删除当前迭代到的元素
expectedModeCount重新赋值modeCount,前面有说,操作集合modeCount会发生变化,在迭代期间发生变化会抛出异常,所以这里要同步下expectedModeCount
limit代表数组的元素数量,删除之后需要减一

最后来看下forEachRemaining()
ArrayList#Itr#forEachRemaining()

         public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;

            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

这个方法其实跟for循环也是一样的,主要是中间的while循环,如果i != size && modeCount == expectedModCount就会通过Consumer.accept()将遍历到的数组元素回调给调用端,这个方法是可以仅仅用于遍历集合,如果需要对集合进行删除操作,那这个方法是不适用的,同时这个方法需要在Android N版本上使用,

    ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("chuan");
        arrayList.add("chuan");
        arrayList.add("chuan");
        Iterator<String> iterator = arrayList.iterator();
        if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.N) {
            iterator.forEachRemaining(new Consumer<String>() {
                @Override
                public void accept(String s) {
                    Log.i("wz", "accept: " + s);
                }
            });
        }
        
    输出为:26766-26766/com.chuan.jun I/wz: accept: chuan--1
    accept: chuan--2
    accept: chuan--3    

ListItr

listItr继承了Itr和ListIterator,ListIterator有插入和修改删除方法,同时还具有向前遍历的方法,所以ListIterator就具备了增删改查的功能,比Itr的功能更加齐全

        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("chuan--1");
        arrayList.add("chuan--2");
        arrayList.add("chuan--3");
        ListIterator<String> listIterator = arrayList.listIterator();
        while (listIterator.hasNext()){
            String str = listIterator.next();
            if(str.equals("chuan--2")){
                listIterator.set("chuan--3");
            }

        }
        Log.i("wz", "onResume: " + arrayList.toString());
        
        输出为:27152-27152/com.chuan.jun I/wz: onResume: [chuan--1, chuan--3, chuan--3]

下面来看下ListItr
ArrayList中初始化ListItr的方法有两个地方

   public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

一个需要传入一个下标值,一个则不需要,但是会默认传入0

ArrayList#ListItr#ListItr()

        ListItr(int index) {
            super();
            cursor = index;
        }

可以看到下标值赋予了cursor,因为ListItr继承于Itr所以,cursor即为Itr中的cursor,代表迭代到当前元素的下一个元素的下标值.
我们来看ListItr中重写的方法,主要是重写的ListIterator中的方法

hasPrevious 判断当前迭代到的元素前面是否还有其他的元素
nexIndex 获取到当前元素的下一个元素的下标值
prevoousIndex 获取到当前元素的前一个元素的下标值
previous 获取到当前迭代到的元素的上一个元素的值,与Itr中的next想对应
set 修改当前遍历的元素
add 在当前迭代到的元素位置插入一个新的元素

    // 判断是否还有上一个元素,如果当前元素为0,说明当前元素是首元素,即往前无元素
        public boolean hasPrevious() {
            return cursor != 0;
        }
    // 获取下/上一个或者当前元素的cursor值  如果调用了next()则cursor代表下一个元素的下标,如果调用了previous则代表上一个元素的下标,如果在next()/previous()之前调用 则代表当前元素的下标
        public int nextIndex() {
            return cursor;
        }
        // 获取当前元素下标的上一个元素下标
        public int previousIndex() {
            return cursor - 1;
        }

上面的三个方法比较简单,这里不再多说
ArrayList#ListItr#previous()

        public E previous() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

基本跟next()一样的道理,获取当前下标的上一个元素

ArrayList#ListItr#set()

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
                limit++;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

set() add()也是一样的道理
总的来说ListItr要比Itr的功能要强大一些

SubList

subList也是ArrayList的一个内部类,主要是为了做数组的截取使用,他持有外部ArrayList的一个引用,因此他拥有add() remove() get()等一些增删改查的功能,还拥有迭代器,不过操作的最终结果会影响到外部ArrayList的变动

        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("chuan--0");
        arrayList.add("chuan--1");
        arrayList.add("chuan--2");
        arrayList.add("chuan--3");
        arrayList.add("chuan--4");
        List<String> subList = arrayList.subList(1,3);
        Log.i("wz", "onResume: " + subList.toString());
        subList.remove(0);
        Log.i("wz", "onResume: " + arrayList.toString());
        
        输出为：
        28391-28391/com.chuan.jun I/wz: onResume: [chuan--1, chuan--2]
        onResume: [chuan--0, chuan--2, chuan--3, chuan--4]

可以看到得到的subList()返回的是一个List,然后对subList进行删除,原先的ArrayList也发生了变化