ArrayList源码
ArrayList()无参构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
翻译一下就是默认空元素数据大小，点进去看是多少呢？
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
发现是个空的ELEMENTDATA数组
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);
}
}
创建了一个指定大小的elementData数组
我们再来看看ArrayList是怎么添加数据的
add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
发现是一个boolean的方法，第一行是ensureCapacityInternal()方法，翻译一下就是确认容量大小，我们跟进
ensureCapacityInternal()方法
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
if语句中先确定ELEMENTDATA是否是空数组，如果是第一次添加，就赋予他一个最小容量minCapacity，minCapacity计算方法为取DEFAULT_CAPACITY和minCapacity两者的最小值，DEFAULT_CAPACITY的大小是多少呢？
private static final int DEFAULT_CAPACITY = 10;
可以看出大小为10，所以第一次扩容长度为10的数组，然后进入下一个ensureExplicitCapacity()方法
ensureExplicitCapacity()方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount++记录的是当前集合被修改的次数，防止多线程时很多线程共同操作，会抛异常
if语句中如果elementData的大小不够时，就调用grow()方法去扩容，即grow()方法才是真正的扩容代码
grow()方法
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);
}
先将elementData.length赋给oldCapacity，第2行oldCapacity>>1相当于除以2，加上oldCapacity即相当于扩容为原先的1.5 倍
第1个if语句中判断newCapacity和minCapacity的大小，第1次扩容时由于oldCapacity为0，所以扩容为原来的1.5倍还是0，也就是这里的小于minCapacity，索性就用minCapacity作为容量
第2个if语句里比较newCapacity和MAX_ARRAY_SIZE的大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
如果大于最大值，就调用hugeCapacity()方法进行处理，我们暂时先跳过，后面回来看这个方法
继续往下，发现最后就是一个数组的复制操作copyOf()，把原先的数据复制到新数组，完成这一步后，此时的数组为默认的10个null值，步步返回为最一开始的调用处
elementData[size++] = e;
此处将数据赋给数组，完成一次add操作
还记得刚刚的hugeCapacity()方法吗，现在来看看
hugeCapacity()方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
其实也很简单，如果minCapacity < 0，就报一个OutOfMemoryError异常，否则就返回一个三目运算符的结果，如果minCapacity > MAX_ARRAY_SIZE，就返回Integer的最大值，如果，minCapacity < MAX_ARRAY_SIZE，就返回MAX_ARRAY_SIZE作为数组容量大小
总结
image.png
Vector源码
Vector()的无参构造器
public Vector() {
this(10);
}
默认大小为10
Vecor()的有参构造器
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
赋值初始化Vector就用赋值的大小
看一下Vector的添加操作
add()方法
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
也有一个modCount++计算被修改次数，下一行ensureCapacityHelper()方法，跟进
ensureCapacityHelper()方法
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
和ArrayList几乎是一样的，跟进grow()
grow()方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
大部分和ArrayList一样，只有在newCapacity时用三目运算符来判断扩容大小，为假时相当于oldCapacity + oldCapacity，即扩容为原来的2倍
Vector就到这里，是古老的实现类了，现在基本都不用啦
LinkedList源码
LinkedList()的无参构造器
public LinkedList() {
}
我愿称之为：《啥 都 没 有》
看看LinkedList的添加操作
add()方法
public boolean add(E e) {
linkLast(e);
return true;
}
执行linkLast()方法，翻译一下就是挂在最后，跟进
linkLast()方法
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++;
}
第1个节点时，first和last都指向他，甚至newNode都指向他，第2个节点进入时，将last指向第2个节点，第2个节点的pre指向第1个节点，l指向第2个节点。
之后size++表示容量，modCount++同样表示被修改次数
看一下LinkedList的删除操作，默认的remove()方法删除当前链表的第1个节点，也可以指定删除某个节点
来看无参的remove()方法
remove()方法
public E remove() {
return removeFirst();
}
调用removeFirst()方法
removeFirst()方法
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
先让f指向first节点，防止删除空链表所以有判断f == null，会报异常，最后返回unLinkFirst()方法
unLinkFirst()方法
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
首先取出f.item即f的内容赋给element，然后把next指向下一个节点，之后把f.item和f.next置为null。因为next != null，所以走else把next.pre置为null，第一个节点失去引用，help GC帮助回收。
最后size--减少容量，modCount++修改次数 + 1，结束
参考：【韩顺平讲java】
欢迎指正。
网友评论