ArrayList指单链表分析，arraylist指单链
ArrayList指单链表分析，arraylist指单链
原理分析
ArrayList是以数组为基础，通过动态扩容的方式，来实现了一个链表的操作，下面就对其源码讲解和分析。
集合的元素和大小
/**
* 默认的数组的大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空的数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存放元素的数组集合
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 数组中元素的个数
*
* @serial
*/
private int size;
内部通过数组的形式来实现链表，其中size是元素的个数，由于是数组，因此元素的索引也是从0开始的。
添加元素
/**
* 在末尾添加一个元素
* @param e
* @return
*/
public boolean add(E e) {
//进行判断是否需要扩容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 在某个位置添加一个元素
* @param index
* @param element
*/
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 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;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}下面就来看一下添加单个元素的具体实现
1. 首先调用了ensureCapacityInternal(size+1),之后将元素的索引赋给elementData[size] = e，然后size自增。例如初始化时，size为0，那么添加一个元素后，elementData[0]=e,size自增后变为了1，下面主要来看一下ensureCapacityInternal(size+1)是如何实现的
/**
* 来对数组元素进行扩容操作
*
* @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 ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果size+1后，仍然大于数组的长度的话
if (minCapacity - elementData.length > 0)
//动态进行扩容操作
grow(minCapacity);
}
private void grow(int minCapacity) {
/**
* 获取旧的数组的长度
* 对旧的数组的长度进行扩容
*/
int oldCapacity = elementData.length;
//扩容后的数组的大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容完后，仍然不够的话
if (newCapacity - minCapacity < 0)
//就以minCapacity为数组的长度
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);
}首先看里面有一个modCount，这个参数用来保存，list结构被改变的次数，也就是每次扩容的时候，都把该元素进行自增。
然后进行扩容判断操作，因此ensureCapacity至少将elementData的容量增加1，所以elementData[size]不会出现越界的情况。
注意事项： 容量的拓展将导致数组元素的复制，多次拓展容量将执行多次整个数组内容的复制。若提前能大致判断list的长度，调用ensureCapacity调整容量，将有效的提高运行速度。
remove操作
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;
}
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
}
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
1.首先看一下remove(index)操作，仍然是首先检查元素是否越界，然后modeCount++，因为list中的数据结构会改变，保留将要被移除的元素，将移除位置之后的元素向前挪动一个位置，将list末尾元素置空（null），返回被移除的元素。
2. remove(object)的操作， 当移除成功后返回true，否则返回false。remove(Object o)中通过遍历element寻找是否存在传入对象，一旦找到就调用fastRemove移除对象。为什么找到了元素就知道了index，不通过remove(index)来移除元素呢？因为fastRemove跳过了判断边界的处理，因为找到元素就相当于确定了index不会超过边界，而且fastRemove并不返回被移除的元素。下面是fastRemove的代码，基本和remove(index)一致。
clear方法操作
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}clear的时候并没有修改elementData的长度（好不容易申请、拓展来的，凭什么释放，留着搞不好还有用呢。这使得确定不再修改list内容之后最好调用trimToSize来释放掉一些空间），只是将所有元素置为null，size设置为0。
trimsize释放空间
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}由于elementData的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但elementData.length很大的情况，将出现空间的浪费。trimToSize将返回一个新的数组给elementData，元素内容保持不变，length很size相同，节省空间。
参考：http://blog.csdn.net/jzhf2012/article/details/8540410
相关文章
- 暂无相关文章
用户点评