java集合之 ArrayList
通过本文你将了解到 ArrayList 的如下信息
目录
ArrayList 简介
ArrayList源码分析
重要成员变量
底层数据结构：数组
默认初始容量：10
当前元素个数
重要方法
add(E e): 添加一个元素
grow(int minCapacity)：扩容
batchRemove(Collection c, boolean complement)：保留或者删除 c 集合中所包含的元素
set(int index, E element)：修改指定位置的元素get(int index) ：查找指定位置的元素
遍历
总结
ArrayList 简介
ArrayList 是一个可存储包括 null 值的任意类型数据、支持动态扩容、有序（输入顺序与输出顺序一致）、查找效率高（时间复杂度O(1)）的一个集合。
ArrayList源码分析
重要成员变量
底层数据结构：数组
//存储元素transient Object[] elementData; // non-private to simplify nested class access
transient表示不允许被序列化
默认初始容量：10
private static final int DEFAULT_CAPACITY = 10;
当前元素个数
private int size;
重要方法
add(E e): 添加一个元素
public boolean add(E e) {//确保有足够的容量ensureCapacityInternal(size + 1); // Increments modCount!!//在 size 下标处添加一个元素elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//当前所需要的最小容量大于等于 10minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 当前存储空间（数组容量）不够了if (minCapacity - elementData.length > 0)grow(minCapacity);}
简单描述：空间是否足够存储—->如果不够就进行扩容—->存储数据到 size 处
grow(int minCapacity)：扩容
在没有达到边界值的情况下，扩容后的数组容量 = 旧数组容量+旧数组容量/2
private void grow(int minCapacity) {// overflow-conscious codeint 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);}
batchRemove(Collection<?> c, boolean complement)：保留或者删除 c 集合中所包含的元素
根据 complement 来决定是保留还是移除指定集合中存在的元素
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;int r = 0, w = 0;boolean modified = false;try {for (; r < size; r++)//complement为true：保留 elementData 和 c 中都存在的元素（相当于求交集）//complement为false：保留只存在于 elementaData 中，但是不存在于c中的元素if (c.contains(elementData[r]) == complement)elementData[w++] = elementData[r];} finally {// Preserve behavioral compatibility with AbstractCollection,// even if c.contains() throws.if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;}if (w != size) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}
set(int index, E element)：修改指定位置的元素
public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}
get(int index) ：查找指定位置的元素
public E get(int index) {rangeCheck(index);return elementData(index);}
遍历
ArrayList 内部实现了两种迭代器（Itr、ListItr）来遍历元素。本质都是根据数组下标来操作的
private class Itr implements Iterator<E> {int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();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();}}@Override@SuppressWarnings("unchecked")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 trafficcursor = i;lastRet = i - 1;checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}/*** An optimized version of AbstractList.ListItr*/private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super();cursor = index;}public boolean hasPrevious() {return cursor != 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();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];}public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void add(E e) {checkForComodification();try {int i = cursor;ArrayList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}}
总结
上面通过增删改查四个具有代表性的方法分析了ArrayList 源码，ArrayList中的其它方法其实也是类似的，所以没有罗列出来。想要表达的中心思想是：ArrayList 底层数据结构是采用的是数组，所以对于查询会很快（直接根据数组下标），删除会比较满（会涉及到元素的移动）。对于数组的遍历，建议直接使用 for 循环，根据数组下标直接获取。
谁借莪１个温暖的怀抱￠
Myth丶恋晨
我会带着你远行
小灰灰
还没有评论，来说两句吧...