几个遗留的问题：
- 迭代器没加进来，还在研究中
- ArrayList 继承关系没说明，后期专门写一篇博客
import java.util.Collection;
/**
* 手写arrayList,内部实现：数组
* 操作，对每个节点的增删改查
* <p>
* 构造方法
*/
public class ArrayList<E> {
/**
* 集合的属性
* 1.大小
* 2.节点
* 3.
*/
//大小
// transient关键字解释：被该关键字修饰的变量只保存在内存中，不会被写到磁盘中，影响变量的生命周期
private int size;
//数组默认长度
private static final int DEFAULT_CAPACITY = 10;
//数组中的元素
private Object[] array;
//空参构造方法
public ArrayList() {
array = new Object[0];
}
//带参构造方法
public ArrayList(int capacity) {
//如果数组长度小于0，抛出异常
if (capacity < 0) {
throw new IllegalArgumentException("list size must be positive ,current size is " + capacity);
}
array = new Object[capacity];
}
//参数是一个集合的构造方法
public ArrayList(Collection<? extends E>/*E或者E的子类*/ c) {
//先把集合转换成数组，然后再一个个装到已有的数组中
Object[] a = c.toArray();
//三种获取字节码文件的方法，这里出现了两种
if (a.getClass() != Object[].class) {//由于继承引起的多态，表明o不是E类型的数组
//如果c不是E类型，而是E的子类，就不能简单的将c赋值给array，因为会改变array的数据类型
Object[] newArray = new Object[a.length];
/**
* 数组复制，参数说明
* 参数1：原数组
* 参数2：原数组起始位置
* 参数3：目标数组
* 参数4：目标数组起始位置
* 参数5：需要复制的数组的长度
*/
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
/**
* 扩容：为什么要扩容：arrayList是用数组实现的，数组是有长度的，当数组的长度不够时，就需要增加数组的长度，即扩容
*
* @param currCapacity 当前数组的容量
* @return 扩容后的数组长度
*/
private static int newCapacity(int currCapacity) {
/**
*需要增加的长度
* 举例：如果currCapacity=4，增加的长度为DEFAULT_CAPACITY即10，
* 如果currCapacity=6，增加的长度为currCapacity >> 1即5
* 这样做是为了无论在哪种情况下，保证数组的长度不会出现太大的变化
*/
int increment = (currCapacity < DEFAULT_CAPACITY / 2) ? DEFAULT_CAPACITY : currCapacity >> 1;
return currCapacity + increment;
}
/**
* 添加
*
* @param e 要添加的元素
* @return 是否添加成功
*/
public boolean add(E e) {
/**
* 这里将array 赋值给局部变量，然后操作局部变量
* 原因：
* 1.线程安全考虑，防止两个线程同时操作array出现bug，赋值给局部变量后，各自操作的是各自的局部变量，规避了风险
* 2.数组是引用数据类型，操作a，就相当于操作了array,
* 通过局部变量就达到了修改成员变量的值的目的，而且a,s使用完成后就被回收，不会占用内存
* note：这里就是一个很重要的思想，先将成员变量赋值给<>局部变量</>，通过操作局部变量来达到修改成员变量值的目的
*/
Object[] a = array;
int s = size;
if (s == a.length) {
//扩容
int newLength = newCapacity(s);
//创建新的数据
Object[] newArray = new Object[newLength];
//赋值
System.arraycopy(a, 0, newArray, 0, a.length);
//改变整个数组的长度
array = a = newArray;
}
//将要添加的元素加进来
a[s] = e;
size = s + 1;
return true;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;//注意size和length的区别
}
/**
* 根据元素查找元素对应的下表
* todo 这里有个疑惑：源码中的参数是Object类型，但是arrayList是E类型,这里为什么要放object类型,而不是E类型
* 先按照源码来写，有懂的朋友回复一下
*/
public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
//数组里面可以存null，比如二维数组
for (int i = 0; i < s; i++) {
if (null == a[i]) {
return i;
}
}
}
return -1;
}
/**
* 某元素最后一次出现的角标
*
* @return
*/
public int lastIndexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = s; i > 0; i--) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = s; i > 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
/**
* 删除某个元素
*
* @return
*/
public E remove(int index) {
Object[] a = array;
int s = size;
//边界检测
if (index < 0) {
throw new IllegalArgumentException();
}
if (index >= s) {//这里加不加“=”都不会报错，因为当index==a.length时进行了扩容，存在这个角标，size角标的元素实际上为null，我自己喜欢加上，为了统一记忆
throw new ArrayIndexOutOfBoundsException();
}
E e = (E) a[index];
/**
* 为什么是s-1,而不是s
* 举例：size=5,index=2;
* 此时需要将index=3和4的元素前移一个位置，此时要移动的元素的长度为2=5-1-2,即length=s-1-index;
* 本质上是因为数组角标是从0开始导致的。
*/
System.arraycopy(a, index + 1, a, index, s - 1 - index);
a[s] = null;//将最后一个角标的元素置空
s--;
size = s;
return e;
/**
* 上面几行代码写法二：
* System.arraycopy(a, index + 1, a, index, --s - index);
* a[s] = null;//将最后一个角标的元素置空
* size = s;
* return e;
*/
}
public E remove(Object object) {
int index = indexOf(object);
E e = remove(index);
return e;
}
public E set(int index, E e) {
Object[] a = array;
int s = size;
if (index >= s) {
throw new IndexOutOfBoundsException();
}
//源码中没加，自己加的判断
if (index < 0) {
throw new IllegalArgumentException();
}
E oldE = (E) a[index];
a[index] = e;
return oldE;
}
public void set(E e) {
Object[] a = array;
int s = size;
if (e == null) {
throw new IllegalArgumentException();
}
if (s == a.length) {
//扩容
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, a.length);
newArray[a.length] = e;
array = a = newArray;
size++;
} else {
a[s] = e;
size++;
}
}
public E get(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throw new IndexOutOfBoundsException();
}
E e = (E) a[index];
return e;
}
}
