简介
ArrayList是实现了List接口的集合，也是很常用的集合，是一个有序可重复的集合，是使用数组实现的，分析ArrayList源码实现，使用场景，自己实现一个ArrayList
原文地址：https://itzmn.github.io/2018/12/05/java%E9%9B%86%E5%90%88-ArrayList/
源码分析
底层实现
变量
// 集合的默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空实例的实例对象
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于存储默认构造的实例，在第一次添加的时候，区分数组的长度
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放集合元素的数组
transient Object[] elementData; // non-private to simplify nested class access
// 存储这个集合的数据数量
private int size;
构造方法
// 传入集合长度
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 默认构造函数
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 传入一个集合的构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
基础方法
size
public int size() {
return size;
}
返回集合内部的数据量
toArray
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
此方法会返回一个新的数组，创建一个新的，则对这个新的操作，不会 改变原来数组的值
toArray(T[] a)
public <T> T[] toArray(T[] a) {
if (a.length < size)
// 如果传入的数组长度小于集合长度，则拷贝集合中的数据，返回一个集合长度的数组
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 如果传入数组大于集合长度，则拷贝全部数据，未填满的赋值为null，
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
此方法会返回新数组
iterator
public Iterator<E> iterator() {
return new Itr();
}
此方法返回一个迭代器，这个是内部类
private class Itr implements Iterator<E> {
// 要返回的下一个节点的索引
int cursor; // index of next element to return
// 返回最后一个元素的索引，如果没有就是-1
int lastRet = -1; // index of last element returned; -1 if no such
// 被更改元素的数量
int expectedModCount = modCount;
Itr() {}
// 是否有下一个节点
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 traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
// 当集合的被修改次数，与保存的被修改次数不同的时候，说明在迭代数据的时候该集合被修改了，说明数据有可能不正常，抛出异常，快速失败
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
增删改查
添加
add方法,将数据添加到数组中
public boolean add(E e) {
// 校验数据
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
开始校验数据，
1.返回数组需要的长度
ensureCapacityInternal(int minCapacity)
// 返回数组需要的长度
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断，如果是默认构造方法，则返回一个默认的数组长度，
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回数组需要的长度
return minCapacity;
}
2.判断需要的数组是否越界
private void ensureExplicitCapacity(int minCapacity) {
// 修改集合的被修改次数
modCount++;
// 比较需要的长度与数组真正的长度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
3.如果越界，需要进行扩容
private void grow(int minCapacity) {
// 保存以前数组的长度
int oldCapacity = elementData.length;
// 对数组进行扩容，默认增加以前长度的一半 >> 1 相当于除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容之后的长度还是不够，则将长度设为需要的，在第一次扩容的时候使用
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果扩容长度大于最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 数组扩容之后，将原数组中的数据，拷贝到新数组,,
// 方法解释 Arrays.copyof(提供数据数组，数组长度) 返回一个数组长度的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
数据校验完毕，把数据添加到数组中，将集合size增加
add方法，在某个位置插入数据
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++;
}
1.校验索引
// 对传入的索引进行校验
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2.和另一add方法一样，校验数组长度
ensureCapacityInternal(size + 1); // Increments modCount!!
3.因为是在某个位置插入数据，也是进行数组拷贝，但是思路是，将这个位置的数据以及以后的数据都向后面挪一位
例如：
索引 1 2 3 4 5
值 a b c d e
在2插入x
变化 a b c d e
x
// 对数据进行拷贝 System.arraycopy（提供数据数组，从那个位置拷贝，拷贝数据数组，从哪个位置放，拷多长）
System.arraycopy(elementData, index, elementData, index + 1,size - index);
4.在对应位置放入值
5.增加size
addAll(Collection c)方法，将一个集合添加进来
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
- 首先将传入的集合转成数组，并且计算长度
- 返回需要的数组（校验数组长度够不够，是否扩容）
- 对数组进行拷贝，将传入的数据拷贝到真正的数组
- 增加集合的size
addAll(int i,Collection c) 在某个索引处，添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
// 校验索引
rangeCheckForAdd(index);
//2.将集合转成数组
Object[] a = c.toArray();
// 3.计算长度
int numNew = a.length;
// 4.得到需要的数组长度（内部判断，扩容）
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
// 5.拷贝数组
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
查找
根据索引位置查找数据
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
- 判断索引,校验是否越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} - 返回对应位置的数据
修改
根据索引位置，修改数据
public E set(int index, E element) {
// 1. 校验下标
rangeCheck(index);
// 2.得到数组对应下标的数据
E oldValue = elementData(index);
// 3.设置数组对应下标的数据为新值
elementData[index] = element;
// 4.返回以前的值
return oldValue;
}
删除
1.根据索引删除数据
public E remove(int index) {
// 1. 校验索引
rangeCheck(index);
// 2.修改集合类内部的修改值，用于统计集合被修改的此时
modCount++;
// 3. 得到该位置的值
E oldValue = elementData(index);
int numMoved = size - index - 1;
// 4. 对数组进行拷贝
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 5，对该位置赋值为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
2.删除某个元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
// 删除null节点
if (elementData[index] == null) {
// 查看下面详情1
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
}
总结
- 集合内部的数组默认长度为10， 扩容长度为原数组长度的一半
- 集合默认构造器，使用了默认的空数组，当在第一次添加数据的时候，会根据这个判断该如何扩容，如果判断是默认的构造器，则使用默认的数组长度，如果不是则对其处理
- 添加方法，首先校验索引，再者判断现有的数组长度是否是需要的数组 长度，如果不够，则进行扩容
- 在进行数组拷贝的时候，需要对某个位置之后的数据进行拷贝，则使用System.copy()，
自己实现
只实现了默认的增删改查方法
import java.util.Arrays;
import java.util.Collection;
/**
* @Author: 张梦楠
* @Date: 2018/12/5 19:33
* 简书：https://www.jianshu.com/u/d611be10d1a6
* 码云：https://gitee.com/zhangqiye
* @Description: 自定义的ArrayList
*/
public class QiYeArrayList<T> {
/**
* 存放数据的数组
*/
private Object[] data;
/**
* 空数组
*/
private Object[] empty = {};
/**
* 默认构造器的空数组，在添加的时候，判断，进行不同的构造
*/
private Object[] default_empty = {};
/**
* 集合的数据量
*/
private int size;
private static final int INITSIZE = 10;
public QiYeArrayList(){
this.data = this.default_empty;
}
public QiYeArrayList(int init) throws Exception {
if (init < 0){
throw new IllegalArgumentException("初始化参数错误: "+
init);
}else {
this.data = new Object[init];
}
}
public Object[] toArray(){
return Arrays.copyOf(data,size);
}
public int size(){
return size;
}
public boolean add(Object o){
// 1. 得到需要的数组
checkOldArray(data,size+1);
// 2. 将数据放在数组中
data[size++] = o;
return true;
}
private void checkOldArray(Object[] data, int i) {
// 2.返回需要的数组长度
int arrayLength = getArrayLength(data, i);
//3. 对校验两个数组是否匹配
checkOldArrayIsOK(arrayLength);
}
private void checkOldArrayIsOK(int arrayLength) {
if (arrayLength - data.length > 0){
// 需要的数组大于现在的数组长度，需要扩容
grow(arrayLength);
}
}
private void grow(int arrayLength) {
int oldLength = data.length;
int newLength = oldLength + oldLength >> 1;
// 如果扩容之后还是不够，则将数组指定为需要的数组长度
if (arrayLength > newLength){
newLength = arrayLength;
}
// 将原有数据拷贝过来，生成新的数组，
data = Arrays.copyOf(data, newLength);
}
private int getArrayLength(Object[] data,int i) {
return data == default_empty ? INITSIZE:i;
}
public boolean add(int index, Object o){
checkIndex(index);
// 1.得到需要的数组
checkOldArray(data,size+1);
// 2. 将原数据进行挪动 0 1 2 3 4 5
System.arraycopy(data,index,data,index+1,size-index);
// 3.添加新数据
data[index] = o;
size++;
return true;
}
private void checkIndex(int index) {
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("下标越界了index:"+index+",size:"+size);
}
}
public boolean addAll(Collection c){
Object[] objects = c.toArray();
int length = objects.length;
if (length == 0){
return true;
}
// 1.得到需要的数组
checkOldArray(data,size+length);
// 2.对数组进行数据的挪动
System.arraycopy(objects,0,data,size,length);
size += length;
return true;
}
public Object get(int index){
checkIndex(index);
Object datum = data[index];
return datum;
}
public Object set(int index,Object o){
checkIndex(index);
Object datum = data[index];
data[index] = o;
return datum;
}
public Object remove(int index){
checkIndex(index);
Object datum = data[index];
int moveSize = size - index - 1;
if (moveSize > 0){
// 1.对数据进行拷贝
System.arraycopy(data,index+1,data,index,size-index-1);
}
data[--size] = null;
return datum;
}
public boolean remove(Object o){
if (null == o){
for (int i=0;i<size;i++){
if (data[i] == null){
removeIndex(i);
return true;
}
}
}else {
for (int i=0;i<size;i++){
if (data[i] .equals(o)){
removeIndex(i);
return true;
}
}
}
return false;
}
private void removeIndex(int index) {
checkIndex(index);
// 1. 对数据进行拷贝
int moveSize = size - index - 1;
if (moveSize > 0){
// 1.对数据进行拷贝
System.arraycopy(data,index+1,data,index,size-index-1);
}
data[--size] = null;
}
}
