ArrayList
参考
前言
底层是 array 实现的。很像学 C 时老师会布置的那种作业,用数组实现一个 List…
类名
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
主要是实现 List 接口。
成员变量
/**
* 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空的对象数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认的空数组
* 无参构造函数创建的数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放数据的数组的缓存变量,不可序列化。
* 因为 elementData 的大小一般比 ArrayList 当前存放的数据个数要大,如果序列化的时候直接把整个 * elementData序列化了,会很浪费空间的,所以ArrayList并没有这么做,而是在writeObject和 * readObject中自定义序列化、反序列化的方法。
*/
transient Object[] elementData;
/**
* 元素数量
* @serial
*/
private int size;
为什么有一个 EMPTY_ELEMENTDATA
还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA
?
查看构造函数,发现 public ArrayList()
使用到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,而 public ArrayList(int initialCapacity)
使用到 EMPTY_ELEMENTDATA
。
这两个空数组虽然对应的都是空 ArrayList,但是具有不同的含义。
1. List<Integer> list = new ArrayList<Integer>();
2. List<Integer> list = new ArrayList<Integer>(0);
当使用 2. 这种构造方式时,就默认用户对定义的容器的大小是有预期的(虽然是 0)。
在执行 add()
方法时,会先进行对数组大小的判断,如果大小不足,会进行扩容。
public boolean add(E e) {
// 扩容 --不一定需要扩容嘛,有判断的过程
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将e赋值给elementData的size+1的位置
elementData[size++] = e;
return true;
}
在 ensureCapacityInternal()
方法的内部,有一个判断与扩容的过程。在第一次执行 add() 方法时,如果使用无参构造函数,会默认用户对容器的大小没有预期,所以把容器扩展为默认的 DEFAULT_CAPACITY
大小。
否则的话,就按照一般的增长方式来增长容器大小。
//为了得到最小的扩容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
transient Object[] elementData
中 transient 修饰符什么意思?
transient
表示在序列化的时候不会序列化该字段。
实现 Serializable 接口,就可以序列化,序列化是为了数据的传输。
平时使用情形:面对用户的敏感信息,银行账号等,不适合在网络上操作,就不序列化。
这里不序列化是为了优化空间使用,把序列化的操作放在了其他地方按情况操作。
总结
- ArrayList的无参数构造函数新建的长度为0,添加第一个元素后,长度为默认长度10
- ArrayList指定新建的长度为0,添加第一个元素后,长度为1,为正常增长结果
- ArrayList通过数组存放数据,成员是elementData
时间复杂度
- size,isEmpty 都由常量 size 维护,调用是常数时间
- get,set 由于底层使用 array,调用是常数时间
iterator 和 listIterator 的调用是常数时间的。(为什么?因为直接返回一个 iterator 和 listIterator 对象?)
插入,删除,查找的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。
很容易想象,在插入,删除,查找时都需要遍历,所以时间复杂度为 O(n),除此之外,插入和删除还会执行数组的拷贝,所以效率不高,还会造成内存浪费。
/**
* 在ArrayList的index位置,添加元素element,会检查添加的位置和容量
*
* @param index 指定元素将被插入的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 判断index是否越界
rangeCheckForAdd(index);
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
//src:源数组; srcPos:源数组要复制的起始位置; dest:目的数组; destPos:目的数组放置的起始位置; length:复制的长度
// 将elementData从index位置开始,复制到elementData的index+1开始的连续空间
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 在elementData的index位置赋值element
elementData[index] = element;
// ArrayList的大小加一
size++;
}
同理,在 remove() 中也涉及到 System.arraycopy()。
contains(Object o)
用 indexOf
构造方法
《java 编程思想》
所有的 Collection 子类型都有一个接受另一个 Collection 对象的构造器,用所接受的 Collection 对象中的元素来填充新的容器.
public boolean addAll(Collection<? extends E> c)
也是接受这样的对象。
/**
* 带参数Collection的构造方法
*
* 这个的意思就是构造时可以接受 Collection 的子类初始化
* 比如 接受 LinkedList 的实例
*
* 继承自 E 的任意类型
*
* @param c 其元素将被放入此列表中的集合
* @throws NullPointerException 如果指定的集合是空的
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {//这一段是为什么?
// c.toarray可能(错误地)不返回对象[](见JAVA BUG编号6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 使用空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
测试达到的效果:
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(2);
ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList);
System.out.println(arrayList1);
ArrayList<Integer> arrayList2 = new ArrayList<>(linkedList);
System.out.println(arrayList2);
输出
[1]
[2]