ArrayList,List 接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
可以看到成员变量为一个Object[] (Object数组)，Object[] obj这样的形式，就是一个Object数组构成的参数形式。说明这个方法的参数是固定的，是一个Object数组，至于这个数组中存储的元素，可以是继承自Object的所有类的对象。
至于 ‘ transien’关键词，我也不太了解，只知道与反序列化有关，这个暂时不做了解；
size代表这个链表所包含元素的个数；
方法剖析：
1、get()方法
得到下标为index的值；
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
// cheackIndex 是判断索引下标是否超过了容器；
2、set() 方法
public E set(int index, E element) {
Objects.checkIndex(index, size); //越界检查
E oldValue = elementData(index);
elementData[index] = element; //可以看到复制的仅仅是引用；
return oldValue;
}
3、add() 方法
private void add(E e, Object[] elementData, int s) {
//按照顺序在尾部加入，故时间复杂度为O（1）
if (s == elementData.length)
elementData = grow(); //grow() 函数即为扩容过程；
elementData[s] = e;
size = s + 1;
}
public void add(int index, E element) {
//向指定位置增加元素，故时间复杂度为O（n）,其它元素向后平移；
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
-----------
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
//扩容后，数组长度加1；
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//可以看到，新的数组的长度为旧数组长度的1.5倍，右移运算；
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
---------
// copyof arrays类
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength]; //创建了一个新的数组
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
-----
//systems类
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
所以ArrayList的扩容方法如下：
1、数组内增加一个元素，若超过其容器长度，则容器长度自动扩大1.5倍，插入元素后，其数组长度加1；
2、过程如下图：
自动扩容
插入元素
[注图片转自 http://www.cnblogs.com/CarpenterLee/p/5419880.html]
4、addAll()方法
addAll()方法能够一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的addAll(Collection<? extends E> c)方法，一个是从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容（扩容为，两者和的 1.5倍）；如果从指定位置插入，也会存在移动元素的情况。
addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
//扩容为，两者和的 1.5倍；
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
5、remove() 方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException(); //抛出异常
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
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
}
public void clear() { //清空
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null; // 每个都赋值为null
}
关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
6、contains() 方法
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* {@code Objects.equals(o, get(i))},
* or -1 if there is no such index.
*/
public int indexOf(Object o) { //时间复杂度为O(n)
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;
}
网友评论