1）本文章的jdk版本为jdk1.8，如果你使用的是其他版本，请参考你的java源码！
2）由于作者水平有限，本文只对部分的方法进行了分析。不足之处，希望大家指出，谢谢
3）如果你对java中的数组还没有理解，可以先学习数组及其在jvm中的存储方式，可以参考下面文章
java中数组在内存中的存放原理讲解
public class arraylist<e> extends abstractlist<e> implements list<e>, randomaccess, cloneable, java.io.serializable
我要评论private static final int default_capacity = 10;private static final object[] empty_elementdata = {};private static final object[] defaultcapacity_empty_elementdata = {};transient object[] elementdata;private int size;private static final int max_array_size = integer.max_value - 8;(integer.max_value = 0x7fffffff)-8//指定初始化容量的构造器，它通过判断int值大小来初始化elementdata
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)
/*类型判断，如果elementdata的类型不是object[]数组，则将其
*复制为object类型的数组，并且elementdata的大小小于size时，多于的位置
*填入null
if (elementdata.getclass() != object[].class)
elementdata = arrays.copyof(elementdata, size, object[].class);
} else {
// replace with empty array.
this.elementdata = empty_elementdata;
}
}
public void trimtosize() /**
* arraylist大小整理，在size < elementdata.length 且 size != 0时，
* elementdata将会被截断为size的长度！！！！
* elementdata将会被截断为size的长度！！！！
*/
public void trimtosize() {
modcount++;
if (size < elementdata.length) {
elementdata = (size == 0)
? empty_elementdata
: arrays.copyof(elementdata, size);
}
}
public void ensurecapacity(int mincapacity)及相关私有方法/**
* 增加数组的容量的判定，这个操作只有在 mincapacity>minexpand 时，
* 才能完成操作。
* 注意下面的三目运算符，minexpand的值取决于
* 你是否已经在你的arraylist对象中放入了值。
* @param mincapacity the desired minimum capacity
*/
public void ensurecapacity(int mincapacity) {
int minexpand = (elementdata != defaultcapacity_empty_elementdata)
// any size if not default element table
? 0
// larger than default for default empty table. it's already
// supposed to be at default size.
: default_capacity;
if (mincapacity > minexpand) {
ensureexplicitcapacity(mincapacity);
}
}
private void ensureexplicitcapacity(int mincapacity) {
modcount++;
// overflow-conscious code
if (mincapacity - elementdata.length > 0)
grow(mincapacity);
}
/* 核心方法，动态数组的增长实现
* 一般情况按oldcapacity的半数增长，但最大的size不能大于integer.max_value
* 原数组会被copy到一个新的数组(size=newcapacity)中，多于的位置填充null
*/
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);
}
private static int hugecapacity(int mincapacity) {
if (mincapacity < 0) // overflow
throw new outofmemoryerror();
return (mincapacity > max_array_size) ?
integer.max_value :
max_array_size;
}
grow()流程图：
public int indexof(object o)//返回指定元素第一次出现的索引，无则返回 -1
public int indexof(object o) {
if (o == null) {
for (int i = 0; i < size; i++)
//如果使用 o.equals()则会抛出空指针异常(null.equals()是错的)
if (elementdata[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//object类的equals90直接调用“==”
if (o.equals(elementdata[i]))
return i;
}
return -1;
}
public int lastindexof(object o)//返回指定元素最后一次出现的索引，无则返回 -1
//从尾部开始遍历
public int lastindexof(object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementdata[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementdata[i]))
return i;
}
return -1;
}
//（1）在尾部添加
public boolean add(e e) {
//确定是否需要扩容
ensurecapacityinternal(size + 1); // increments modcount!!
elementdata[size++] = e;
return true;
}
//（2）在指定位置添加
public void add(int index, e element) {
//判定是否索引越界
rangecheckforadd(index);
//确定是否需要扩容
ensurecapacityinternal(size + 1); // increments modcount!!
//从指定数组的指定开始位置到指定结束位置复制一个数组，在本节末尾给出了该方法的详细解释
system.arraycopy(elementdata, index, elementdata, index + 1,
size - index);
//将index位置的原element替换为新的element
elementdata[index] = element;
size++;
}
//（3）两个索引越界检查方法
private void rangecheck(int index) {
if (index >= size)
throw new indexoutofboundsexception(outofboundsmsg(index));
}
private void rangecheckforadd(int index) {
if (index > size || index < 0)
throw new indexoutofboundsexception(outofboundsmsg(index));
}
//索引越界信息
private string outofboundsmsg(int index) {
return "index: "+index+", size: "+size;
}
public static void arraycopy(object src, int srcpos,object dest, int destpos,int length)
从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 src 引用的源数组到 dest 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 length 参数。源数组中位置在 srcpos 到 srcpos+length-1 之间的组件被分别复制到目标数组中的 destpos 到 destpos+length-1 位置。
如果参数 src 和 dest 引用相同的数组对象，则复制的执行过程就好像首先将 srcpos 到 srcpos+length-1 位置的组件复制到一个带有 length 组件的临时数组，然后再将此临时数组的内容复制到目标数组的 destpos 到 destpos+length-1 位置一样。
这样一来，arraylist的插入就很好理解了，先将 __index 及其后__面的所有元素复制一份，然后从 index+1 处到destpos+length-1；然后将 index 处的元素替换为新的元素即可！。
在理解了add方法之后，remove方法就很好理解了。
//移除指定位置的元素
public e remove(int index) {
rangecheck(index);
modcount++;
e oldvalue = elementdata(index);
//所要移除元素的位置之所以不用 index - 1，
//是因为rangcheck()方法中是判断 index>size，而不是>=
int nummoved = size - index - 1;
if (nummoved > 0)
system.arraycopy(elementdata, index+1, elementdata, index,
nummoved);
//将最后一个元素置null，方便垃圾回收器回收
//至于为什么置null能方便gc回收，请阅读“对象生命周期”和jvm垃圾回收机制的相关书籍和文章
elementdata[--size] = null; // clear to let gc do its work
return oldvalue;
}
//注意for循环，是移除所有满足条件的obj
public boolean remove(object o) {
//空判断！集合框架中有大量空判断，自己在编程过程中也要注意空判断，
//以免抛出“空指针异常”
if (o == null) {
for (int index = 0; index < size; index++)
if (elementdata[index] == null) {
//不进行索引越界检查的快速remove
fastremove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementdata[index])) {
fastremove(index);
return true;
}
}
return false;
}
//跳过边界检查的私有移除方法，并且不返回删除的值。
//相比 remove 少了检查，和返回值，一个对象的创建
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
}
toarraypublic object[] toarray() {
return arrays.copyof(elementdata, size);
}
@suppresswarnings("unchecked")
public <t> t[] toarray(t[] a) {
if (a.length < size)
// make a new array of a's runtime type, but my contents:
return (t[]) arrays.copyof(elementdata, size, a.getclass());
system.arraycopy(elementdata, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
此方法担当基于数组的 api 和基于 collection 的 api 之间的桥梁。
public object clone()//返回这个arraylist实例的一个浅副本。（元素本身没有被复制。）
//它的modcount将会置0
//todo 不懂对象克隆的原理
public object clone() {
try {
arraylist<?> v = (arraylist<?>) super.clone();
v.elementdata = arrays.copyof(elementdata, size);
v.modcount = 0;
return v;
} catch (clonenotsupportedexception e) {
// this shouldn't happen, since we are cloneable
throw new internalerror(e);
}
}
未完待续...
如对本文有疑问， 点击进行留言回复！！
![[杭电多校2020]第一场 1004 Distinct Sub-palindromes](http://www.lhsxpumps.com/_images5/10qianwan/20200724/s_0_202007241733388592.png)
[杭电多校2020]第一场 1004 Distinct Sub-palindromes
Swift -- 将本地生成的UIImage进行持久化保存（存到文件中fileManager.createFile）
网友评论