引言
Java
中的List
集合属于一种线性的数据结构,它继承了Collection
接口。常见的List
集合实现有ArrayList
以及LinkedList
,本文将从源码分析以及使用场景等方面对ArrayList
进行具体的阐述。
- 源码分析
- 使用场景
- 总结
一、源码分析
ArrayList介绍
ArrayList
继承了AbstractList
同时实现了List
接口,ArrayList
的类图如下所示:
ArrayList
部分源码如下所示:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... }
//初始化默认容量 private static final int DEFAULT_CAPACITY = 10; //底层实现为数组 transient Object[] elementData; //默认容量的空元素数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
由上可知,transient存储数据使用的是数组,同时使用transient进行修饰。我们都知道被transient修饰的属性在序列化对象时是不会被序列化到磁盘中,只存在于内存中。但是Object[] elementData是存储元素的,它被transient修饰是由于存储的特殊性。因为数组中存储元素的时候一般是留有余量空间的,如果容量不够会进行扩展,所以有些空间实际并没有存储元素,并不需要将其进行序列化。实际ArrayList中的writeObject方法以及readObject方法进行元素的序列化和反序列化。
//创建指定容量大小的ArrayList 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); } } //无参数构造方法,当元素被添加后,容量扩容为默认大小10 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } ... //判断ArrayList是否包含某元素 public boolean contains(Object o) { return indexOf(o) >= 0; } //获取元素的索引值 public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -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; } //返回数组 public Object[] toArray() { return Arrays.copyOf(elementData, size); } ... //获取指定索引对应的元素 public E get(int index) { rangeCheck(index); return elementData(index); } //设置指定索引位置的元素为element public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } //往集合中添加元素 public boolean add(E e) { //根据传入的最小需要容量minCapacity来和数组的容量长度对比,若minCapactity大于或等于数组容量,则需要进行扩容 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //在指定索引处添加元素 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++; } //删除指定索引的元素 public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); 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 return oldValue; } //删除指定集合元素 public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } //将集合c追加到ArrayList中去 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; } //java.io.Serializable的写入方法,将ArrayList的容量,所有的元素值都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // 写入数组的容量 s.writeInt(size); // 写入数组的每一个元素 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } //java.io.Serializable的读取方法:根据写入方式读出,先将ArrayList的容量读出,再将所有的元素值读出 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // 从输入流中读取ArrayList的容量 s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity ensureCapacityInternal(size); Object[] a = elementData; //从输入流中将所有的元素值读出 for (int i=0; i<size; i++) { a[i] = s.readObject(); } } } ...
二、使用场景
不同的数据结构适用的场景是不一样的,正确的在适合的场景下选用适合的数据结构可以使得程序更加优雅以及高性能。
ArrayList
适用场景:
在对数据进行进行添加以及删除的时候,如果对数据操作速度要求不高(插入和删除会涉及其他元素的移动),但是对数据的访问速度又有要求,建议使用ArrayList
。
三、总结
ArrayList底层是基于数组实现的,所以占据一块连续的内存空间,并且空间可以进行动态扩展,底层存储数据的数组为transient Object[] elementData,允许存储的元素为null,他是线程不安全的。
ArrayList的数据查询效率很高,时间复杂度为O(1),但是数据的插入和删除时间复杂度最坏为O(n)。