前言
在官方jdk的文档中有这么一段话,大致的意思就是ArrayList是List接口的一种实现,该类是可调整大小的数组,并允许所有元素包括null值;这个类大致相当于Vector,只是它不是同步的(也就是存在在并发的情况下,会存在线程安全问题)。注:从上面文档中,可以证明ArrayList的数据结构是数组。
使用案例
public class ArrayListDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("123");
list.add("123");
list.add("124");
list.add("123");
list.forEach(System.out::println);
}
}
运行后的效果:
源码剖析
1、大致看一下该类所提供的一些方法
2、从我们demo中的案例进行源码解析,先看看add方法
//new ArrayList<>();创建个空的数组
public ArrayList() {
//transient Object[] elementData;
//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// java.util.ArrayList#add(E) add 添加元素
public boolean add(E e) {
// 修改次数,只要涉及到操作,都会对该对象的值+1
modCount++;
add(e, elementData, size);
return true;
}
//java.util.ArrayList#add(E, java.lang.Object[], int)
//
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
//调整数组,可能需要调整数组长度,然后再重新copy一份数组出来,然后重新指定
elementData = grow();
//将元素放在数组最后
elementData[s] = e;
size = s + 1;
}
//java.util.ArrayList#grow()
private Object[] grow() {
//size+1
return grow(size + 1);
}
//java.util.ArrayList#grow(int)
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
//新的容量,也就是重新定义数组大小,这里就会涉及到扩容,minCapacity=size+1
private int newCapacity(int minCapacity) {
// overflow-conscious code
//先获取elementData数组的长度
int oldCapacity = elementData.length;
//oldCapacity + oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
//private static final int DEFAULT_CAPACITY = 10;
//所以一开始默认的数据长度是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
//java.util.Arrays#copyOf(T[], int)
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
//java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
//通过jndi调用java虚拟机中的本地方法。src源对象,从src源srcPos位置开始,dest目标对象,destPos目标位置,copy的元素长度,也就是多少个元素
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
从上面可以知道,其实ArrayList就是个数组来的,该类只是帮我们封装好一些处理方法,让我们可以更便捷的使用。下面我们再看该类中的其他public方法。
3、trimToSize
//扩容后的多余未赋值的空间给去掉,简单的处理方法就是将实际存在的元素重新copy到另一个数据对象中,长度大小等于size
//这样的做法是为了减少没必要的内存空间
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
4、ensureCapacity
//确保容量
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
5、indexOf
//返回元素在数组中的下标,也就是元素在数组中的位置,如果该元素不存在则返回-1
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
// o需要查抄的对象,start起始位置,end结束位置
// 通过简单的遍历对比,时间复杂度为O(n)
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
6、contains
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
7、lastIndexOf
//查询元素存在数组中最末尾的位置,如果不存在则返回-1
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;
if (o == null) {
for (int i = end - 1; i >= start; i--) {
if (es[i] == null) {
return i;
}
}
} else {
for (int i = end - 1; i >= start; i--) {
if (o.equals(es[i])) {
return i;
}
}
}
return -1;
}
8、clone
//深度克隆一个对象
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);
}
}
9、toArray
//返回一个数据
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
10、get
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
11、set
//给某个位置的元素重新赋值,返回旧值
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
12、java.util.ArrayList#remove(int)
//删除index对应下标元素,返回以前的值,然后后面元素向前移
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
13、java.util.ArrayList#remove(java.lang.Object)
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
// found是break found的一个标识,也就是说break后,从found出去。
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
// 这里break后,就会跳到下面执行fastMove方法,而不是继续往下执行return false;句柄
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
上面是我们使用ArrayList对象常用的一些方法的简单解析。如果还有问题可以留言讨论