ArrayList 源码解析 底层容器 ArrayList
底层就是一个长度可以动态增长的Object数组,如下elementData
。
其中实现的接口中RandomAccess
、Cloneable
中都没有实现方法,更多的作为一种标识进行判断
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 COPY COPY public class ArrayList <E > extends AbstractList <E > implements List <E >, RandomAccess , Cloneable , java .io .Serializable { private static final long serialVersionUID = 8683452581122892189L ; private static final int DEFAULT_CAPACITY = 10 ; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; }
JDK1.7前,使用无参数构造方法创建ArrayList
对象时,默认底层数组长度是10。类似于单例的饿汉式
JDK1.8后,使用无参数构造方法创建ArrayList
对象时,默认底层数组长度是0,如下即指向了DEFAULTCAPACITY_EMPTY_ELEMENTDATA
。而当对数组进行添加元素操作后,才将数组扩容(第一次添加扩容为10),类似于单例的懒汉式
1 2 3 4 COPY COPY public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
ArrayList中提供了一个内部类Itr,实现了Iterator
接口,实现对集合元素的遍历
1 2 3 4 COPY COPY public Iterator<E> iterator () { return new Itr(); }private class Itr implements Iterator <E > { }
初始化 主要有三种初始化办法:无参初始化、指定初始化数组大小初始化、指定初始数据初始化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 COPY COPY private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }public ArrayList (Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0 ) { if (elementData.getClass() != Object[].class ) { elementData = Arrays.copyOf(elementData, size, Object[].class ) ; } } else { this .elementData = EMPTY_ELEMENTDATA; } }
需要注意,JDK 1.8之后:ArrayList 无参构造器初始化时,默认大小是空数组,当第一次add后才扩容为10
新增与扩容 新增 1 2 3 4 5 6 7 COPY COPY public boolean add (E e) { ensureCapacityInternal(size + 1 ); elementData[size++] = e; return true ; }
扩容 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 COPY COPY private void ensureCapacityInternal (int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }private void ensureExplicitCapacity (int minCapacity) { modCount++; 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 ) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0 ) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
注意:
扩容的规则并不是翻倍,而是扩为之前容量的1.5倍
ArrayList 中的数组的最大值是 Integer.MAX_VALUE
,超过这个值,JVM 就不会给数组分配内存空间了
新增时,并没有对值进行严格的校验,所以 ArrayList 是允许 null 值的
扩容的底层是通过 Arrays.copyOf(elementData, newCapacity);
实现的
LinkedList 源码解析 LinkedList
实现了Deque
接口,所以除了可以作为线性表来使用外,还可以当做队列和栈来使用
1 2 3 4 5 6 7 8 9 10 11 12 13 COPY COPY public class LinkedList <E > extends AbstractSequentialList <E > implements List <E >, Deque <E >, Cloneable , java .io .Serializable { transient int size = 0 ; transient Node<E> first; transient Node<E> last; public LinkedList () { } }
利用静态内部类Node
,表示双向链表的节点,如下:
1 2 3 4 5 6 7 8 9 10 11 COPY COPY private static class Node <E > { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this .item = element; this .next = next; this .prev = prev; } }