Java基础—基于JDK1.8的LinkedList源码分析

源码解读

当我们一般提到ArrayList的话都会脱口而出它的几个特点：有序、可重复、查找速度快，但是插入和删除比较慢，线程不安全，那么现在阿呆哥哥就会有这些疑问：为什么说是有序的？怎么有序？为什么又说插入和删除比较慢？为什么慢？还有线程为什么不安全？所以带着这些问题，我们一一的来源码中来找找答案。

一般对于一个陌生的类，我们想使用它，都会先看它构造方法，再看它的属性和方法，那么我们也按照这种方式来读读ArrayList这个类，构造方法：

ArrayList<String> arrayList = new ArrayList();ArrayList<String> arrayList1 = new ArrayList(2);

一般来说我们常见使用ArrayList的创建方式是上面的这两种。

private static final int DEFAULT_CAPACITY = 10;private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};private static final Object[] EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size;public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}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);}}

上面是我们两个构造方法和我们类中基本的属性，从上面的代码上来看，在创建构造基本上都没有做，且定义了两个默认的空数组，默认容器的大小DEFAULT_CAPACITY为10，还有我们真正存储元素的地方elementData数组，所以这就是为什么说ArrayList存储集合元素的底层时是使用数组来实现，OK，上面的代码除了一个transient 修饰符之外我们同学们可能有点陌生之外，其余的应该都能看的懂，transient 有什么作用还有为什么用它修饰elementData字段，这个需要看完整个源码之后，我再来给大家解释的话比较合适，这里只需要留心一下。

还有一个不常用的构造方法：

public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}

第2行：利用Collection.toArray()方法得到一个对象数组，并赋值给elementData

第3行：size代表集合的大小，当通过别的集合来构造ArrayList的时候，需要赋值size

第5-6行：判断 c.toArray()是否出错返回的结果是否出错，如果出错了就利用Arrays.copyOf 来复制集合c中的元素到elementData数组中

第9行：如果c中元素数量为空，则将EMPTY_ELEMENTDATA空数组赋值给elementData

上面就是所有的构造函数的代码了，这里我们可以看到，当构造函数走完之后，会创建出数组elementData和初始化size，Collection.toArray()则是将Collection中所有元素赋值到一个数组，Arrays.copyOf()则是根据Class类型来决定是new还是反射来创造对象并放置到新的数组中，源码如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {@SuppressWarnings("unchecked")T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));return copy;}

这里面System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 这个方法在我们的后面会的代码中会出现，就先讲了，定义是：将数组src从下标为srcPos开始拷贝，一直拷贝length个元素到dest数组中，在dest数组中从destPos开始加入先的srcPos数组元素。相当于将src集合中的[srcPos,srcPos+length]这些元素添加到集合dest中去，起始位置为destPos

增加元素方法

一般经常使用的是下面三种方法

arrayList.add( E element);arrayList.add(int index, E element);arrayList.addAll(Collection<? extends E> c);

让我们一个个来看看

public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint 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);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}Integer. MAX_VALUE = 0x7fffffff;MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

第2行：调用ensureCapacityInternal()函数

第8-9行：判断当前是否是使用默认的构造函数初始化，如果是设置最小的容量为默认容量10，即默认的elementData的大小为10（这里是有一个容器的概念，当前容器的大小一般是大于当前ArrayList的元素个数大小的）

第16行：modCount字段是用来记录修改过扩容的次数，调用ensureExplicitCapacity()方法意味着确定修改容器的大小，即确认扩容

第26-30、35-44行：一般默认是扩容1.5倍，当时当发现还是不能满足的话，则使用size+1之后的元素个数，如果发现扩容之后的值大于我们规定的最大值，则判断size+1的值是否大于MAX_ARRAY_SIZE的值，大于则取值MAX_VALUE，反之则MAX_ARRAY_SIZE，也就数说容器最大的数量为MAX_VALUE

第32行：就是拷贝之前的数据，扩大数组，且构建出一个新的数组

第3行：这时候数组扩容完毕，就是要将需要添加的元素加入到数组中了

public void add(int index, E element) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));ensureCapacityInternal(size + 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1, size - index);elementData[index] = element;size++;}

第2-3行：判断插入的下标是否越界

第5行：和上面的一样，判断是否扩容

第6行：System.arraycopy这个方法的api在上面已经讲过了，这里的话则是将数组elementData从index开始的数据向后移动一位

第8-9行：则是赋值index位置的数据，数组大小加一

public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew); // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

第2行：将集合转成数组，这时候源码没有对c空很奇怪，如果传入的Collection为空就直接空指针了

第3-7行：获取数组a的长度，进行扩容判断，再将新传入的数组复制到elementData数组中去

所以对增加数据的话主要调用add、addAll方法，判断是否下标越界，是否需要扩容，扩容的原理是每次扩容1.5倍，如果不够的话就是用size+1为容器值，容器扩充后modCount的值对应修改一次

删除元素方法

常用删除方法有以下三种，我们一个个来看看

arrayList.remove(Object o);arrayList.remove(int index)arrayList.removeAll(Collection<?> c)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}

从上面源码可以看出，如果要移除的元素为null和不为空，都是通过for循环找到要被移除元素的第一个下标，所以这里我们就会思考，当我们的集合中有多个null的话，是不是调用remove(null)这个方法只会移除第一个出现的null元素呢？这个需要同学们下去验证一下。然后通过System.arraycopy函数，来重新组合elementData中的值，且elementData[size]置空原尾部数据 不再强引用， 可以GC掉。

public E remove(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));modCount++;E oldValue = (E) 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 workreturn oldValue;}

可以看到remove(int index)更简单了，都不需要通过for循环将要删除的元素下边确认下来，整体的逻辑和上面通过元素删除的没什么区别，再来看看批量删除

public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}public static <T> T requireNonNull(T obj) {if (obj == null)throw new NullPointerException();return obj;}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) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}

第2、6-10行：对传入集合c进行判空处理

第13-15行：定义局部变量elementData、r、w、modified elementData用来重新指向成员变量elementData，用来存储最终过滤后的元素，w用来纪录过滤之后集合中元素的个数，modified用来返回这次是否有修改集合中的元素

第17-19行：for循环遍历原有的elementData数组，发现如果不是要移除的元素，则重新存储在elementData，且w自增

第23-28行：如果出现异常，则会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。

第29-36行：判断如果w!=size，则表明原先elementData数组中有元素被移除了，然后将数组尾端size-w个元素置空，等待gc回收。再修改modCount的值，在修改当前数组大小size的值

修改元素方法

arrayList.set(int index, E element)

常见的方法也就是上面这一种，我们来看看它的实现的源码

public E set(int index, E element) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));E oldValue = (E) elementData[index];elementData[index] = element;return oldValue;}

源码很简单，首先去判断是否越界，如果没有越界则将index下表的元素重新赋值element新值，将老值oldValue返回回去

查询元素方法arrayList.get(int index);让我们看看源码：

public E get(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));return (E) elementData[index];}

源码也炒鸡简单，首先去判断是否越界，如果没有越界则将index下的元素从elementData数组中取出返回

清空元素方法arrayList.clear();常见清空也就这一个方法：

public void clear() {modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}

源码也很简单，for循环重置每一个elementData数组为空，修改size的值，修改modCount值

判断是否存在某个元素

arrayList.contains(Object o);arrayList.lastIndexOf(Object o);

常见的一般是contains方法，不过我这里像把lastIndexOf方法一起讲了，源码都差不多

public boolean contains(Object o) {return indexOf(o) >= 0;}public int indexOf(Object o) {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;}public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}

通过上面的源码，大家可以看到，不管是contains方法还是lastIndexOf方法，其实就是进行for循环，如果找到该元素则记录下当前元素下标，如果没找到则返回-1，很简单遍历ArrayList中的对象（迭代器）

Iterator<String> it = arrayList.iterator();while (it.hasNext()) {System.out.println(it.next());}

我们遍历集合中的元素方法挺多的，这里我们就不讲for循环遍历，我们来看看专属于集合的iterator遍历方法吧

public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E> {// Android-changed: Add "limit" field to detect end of iteration.// The "limit" of this iterator. This is the size of the list at the time the// iterator was created. Adding & removing elements will invalidate the iteration// anyway (and cause next() to throw) so saving this value will guarantee that the// value of hasNext() remains stable and won't flap between true and false when elements// are added and removed from the list.protected int limit = ArrayList.this.size;int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;public boolean hasNext() {return cursor < limit;}@SuppressWarnings("unchecked")public E next() {if (modCount != expectedModCount)throw new ConcurrentModificationException();int i = cursor;if (i >= limit)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}public void remove() {if (lastRet < 0)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();try {ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = modCount;limit--;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}

第1-3行：在获取集合的迭代器的时候，去new了一个Itr对象，而Itr实现了Iterator接口，我们主要重点关注Iterator接口的hasNext、next方法

第12-16行：定义变量，limit：用来记录当前集合的大小值；cursor：游标，默认为0，用来记录下一个元素的下标；lastRet：上一次返回元素的下标

第18-20行：判断当前游标cursor的值是否超过当前集合大小zise，如果没有则说明后面还有元素

第24-31行：在这里面做了不少线程安全的判断，在这里如果我们异步的操作了集合就会触发这些异常，然后获取到集合中存储元素的elemenData数组

第32-33行：游标cursor+1，然后返回元素 ，并设置这次次返回的元素的下标赋值给lastRet

看源码之前问题的反思

ok，上面的话基本上把我们ArrayList常用的方法的源码给看完了。这时候，我们需要来对之前的问题来一一进行总结了

①有序、可重复是什么概念？

public static void main(String[] args){ArrayList arrayList = new ArrayList();arrayList.add("1");arrayList.add("1");arrayList.add("2");arrayList.add("3");arrayList.add("1");Iterator<String> it = arrayList.iterator();while (it.hasNext()) {System.out.println(it.next());}}

输出结果

11231

可重复是指加入的元素可以重复，有序是指的加入元素的顺序和取出来的时候顺序相同，一般这个特点是List相对于Set和Map来比较出来的，后面我们把Set、Map的源码看了之后会更加理解这两个特点

②为什么说查找查找元素比较快，但添加和删除元素比较慢呢？

我们从上面的源码得到，当增加元素的时候是有可能会触发扩容机制的，而扩容机制会导致数组复制；删除和批量删除会导致找出两个集合的交集，以及数组复制操作；而查询直接调用return (E) elementData[index]; 所以说增、删都相对低效 而查找是很高效的操作。

③为什么说ArrayList线程是不安全

从上面的代码我们都知道，现在add()方法为例

public boolean add(E e) {//确定是否扩容，这里可以忽略ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true;}

这里我们主要看两点，第一点add()方法前面没有synchronized字段、第二点 elementData[size++] = e;这段代码可以拆开为下面两部分代码

elementData[size] = e;size++

也就是说整个add()方法可以拆为两步，第一步在elementData[Size] 的位置存放此元素，第二步增大 Size 的值。我们都知道我们的CUP是切换进程运行的，在单线程中这样是没有问题的，但是一般在我们项目中很多情况是在多线程中使用ArrayList的，这时候比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 ，所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。这样就会得到元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这样就造成了我们的线程不安全了。

大家可以写一个线程搞两个线程来试试，看看size是不是有问题，这里就不带大家一起写了。

④ transient 关键字有什么用？

唉，这个就有点意思了，这个是我们之前读源码读出来的遗留问题，那源码现在读完了，是时候来解决这个问题了，我们来看看transient官方给的解释是什么？

当对象被序列化时（写入字节序列到目标文件）时，transient阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。然后我们看一下ArrayList的源码中是实现了java.io.Serializable序列化了的，也就是transient Object[] elementData; 这行代码的意思是不希望elementData被序列化，那这时候我们就有一个疑问了，为什么elementData不进行序列化？这时候我去网上找了一下答案，觉得这个解释是最合理且易懂的

在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去,所以需要手动的序列化数组对象,所以使用了transient来禁止自动序列化这个数组

这时候我们是懂了为什么不给elementData进行序列化了，那当我们要使用序列化对象的时候，elementData里面的数据是不是不能使用了？这里ArrayList的源码提供了下面方法

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}}/** * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, * deserialize it). */private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData = EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityensureCapacityInternal(size);Object[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}}

通过writeObject方法将数据非null数据写入到对象流中，再使用readObject读取数据。

总结

上面我们写了这么一大篇，是时候该来总结总结一下了

①查询高效、但增删低效，增加元素如果导致扩容，则会修改modCount，删出元素一定会修改。 改和查一定不会修改modCount。增加和删除操作会导致元素复制，因此，增删都相对低效。而在我们常见的Android场景中，ArrayList多用于存储列表的数据，列表滑动时需要展示每一个Item（element）的数组，所以查询操作是最高频的，且增加操作只有在列表加载更多时才会用到 ，而且是在列表尾部插入，所以也不需要移动数据的操作。而删操作则更低频。 故选用ArrayList作为保存数据的结构

②线程不安全，这个特点一般会和Vector做比较，Vector的源码，内部也是数组做的，区别在于Vector在API上都加了synchronized所以它是线程安全的，以及Vector扩容时，是翻倍size，而ArrayList是扩容50%。Vector的源码大家可以在后面闲下来的时候看看，这里给大家留一个思考题：既然Vector是安全的，那为什么我们在日常开发Android中基本上没有用到Vector呢？大家可以闲下来的时候来寻找一下这个问题的答案

最后再啰嗦一句，写完全篇后发现 ，感觉好久没写博客手很生了，在写的过程总发现大体框架不对也在一点点的修复，后面争取坚持写下来，加油！！！