分类： Java
2015-09-28 16:08:34
ArrayList 内部是以数组进行存储，新创建一个对象，如果没指定大小，默认大小为10。 当add 一个新元素，会将加入后的大小与目前list的大小进行比较，如果不足，会立即扩容到1.5 倍的空间大小。具体部分说明及代码见下：
参数：
初始化存放元素的类型为 Object 数组
private transient Object[] elementData;
transient 关键字，用来表示一个域不是该对象串化的一部分。当对象被串化候，被transient 关键字修饰的变量是不会包含在该串化对象中的。
private int size; arrayList 的大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
最大允许的容量大小，int 最大为：2147483647
构造方法：
public ArrayList() {
this(10);
}
从 此方法来看，默认设置的大小为10.
public ArrayList(Collection<? extends E> c)
此构造方法，是直接根据 collection 对象来定义的。
方法与代码：
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
此方法是被掉于
public boolean removeAll(Collection<?> c) 方法中，删除所有包含Collection C 的元素，此方法还是多有意思！
if (minCapacity - elementData.length > 0)
grow(minCapacity);
此代码是检测容量，容量大于elementData 的大小，就直接扩容。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
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);
}
code 为 oldCapacity >> 1 表明新增扩容量为之前大小的一半。
再 elementData = Arrays.copyOf(elementData, newCapacity); 将数据拷贝。
linkedList
node 被定义为双向node，包含pref 以及 next， 即该链表就为双向链表。
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
将新node 插入到链表头
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
将新node插入到链表尾
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
此方法是从链表中取出指定位置的node。
算法大致为：判断index 与 链表中间值的比较，根据结果在前半段或者后半段中进行遍历和判断。
linkBefore(element, node(index));将node插入到指定index的位置
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
