ArrayList和LinkedList源码解读

ArrayList

List<String> list = new ArrayList<>();
list.add("zly");
list.add("coding");
list.add("菜鸟阶段！");

底层是数组：transient Object[] elementData;

构造方法： 一个是支持自定义大小的，一个是直接赋值成{}

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// 如果用户指定了初始容量this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {// 如果用户指定了初始容量为0，就赋值成一个{}this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}
}
/*** Constructs an empty list with an initial capacity of ten.*/
public ArrayList() {// DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个默认大小为0的数组this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

add方法：

public boolean add(E e) {// 确保容量足够，判断是否需要扩容ensureCapacityInternal(size + 1);  // Increments modCount!!// 插入数据elementData[size++] = e;return true;
}

对于扩容的解释：

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// 1.5倍进行扩容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);
}

带索引的add方法：

public void add(int index, E element) {// 检查索引是否合法！rangeCheckForAdd(index);// 判断是否需要扩容ensureCapacityInternal(size + 1);  // Increments modCount!!// 将index和之后的数据都后移一位System.arraycopy(elementData, index, elementData, index + 1,size - index);// 插入元素                 elementData[index] = element;size++;
}

get方法

public E get(int index) {// 检查索引是否合法rangeCheck(index);// 根据索引从object[] 获取数据return elementData(index);
}

set方法

将某个index的数据修改成指定的元素。

public E set(int index, E element) {rangeCheck(index);// 旧数据E oldValue = elementData(index);// 更新成新数据elementData[index] = element;// 返回旧数据return oldValue;
}

remove方法

public E remove(int index) {rangeCheck(index);// 修改次数+1modCount++;// 获取原先的值E oldValue = elementData(index);// 计算往前移动的下标int numMoved = size - index - 1;if (numMoved > 0)// 移动数据System.arraycopy(elementData, index+1, elementData, index,numMoved);// 将最后一个树设置为nullelementData[--size] = null; // clear to let GC do its workreturn oldValue;
}

remove某个元素

// 删除第一个匹配的值
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
}

迭代器iterator

在ArrayList中自己实现了一个Itr迭代器，由于ArrayList是线程不安全的，所以在并发删除的时候，通过会报错Exception in thread "main" java.util.ConcurrentModificationException，并发修改错误。

因为在javac后面，增强for会被编译成iterator的形式，删除调用的是ArrayList的remove方法，而next方法是iterator内的，所以我们可以看iterator内的next方法，然后就大致知道为什么会报这个错了。

public E next() {// check是否有并发修改checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];
}
// modCount在ArrayList的fastRemove已经修改了
final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

那为什么使用iterator器为什么就可以安全删除呢？

public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {// 虽然这里也修改了ArrayList.this.remove(lastRet);cursor = lastRet;lastRet = -1;// 假修改了expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}
}

elementData被transient修饰

ArrayList本身是支持序列化的，为什么存储的元素用transient修饰呢，其实在ArrayList也提供了序列化的方式，提供了readObject和writeObject两种方法。

// 序列化
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();}
}
// 反序列化
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 capacityint capacity = calculateCapacity(elementData, size);SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);ensureCapacityInternal(size);Object[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}
}

LinkedList

双向链表结构

LinkedList实现了List、Deque

// 链表的元素个数
transient int size = 0;// 链表的头节点
transient Node<E> first;// 链表的尾节点
transient Node<E> last;

我们都说LinkedList是通过双向链表实现的，那它的链表节点的结构长什么样呢？其实相信大家数据结构有了解的话，肯定也知道会有一个前缀节点和指向的下一个节点和指向的数据

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;}
}

构造函数

public LinkedList() {
}public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

那常用的方法会有哪些呢？

public E getFirst();
public E getLast();
public E removeFirst();
public E removeLast();
public void addFirst(E e) ;
public void addLast(E e);
public E get(int index);
public E set(int index, E element);

上面的方法都可以看到提供了添加和删除的方法以及获取链表头尾节点的方法，当然这里面也有迭代器的实现，下面我们再一个个开它们源码的实现。

add(E e)

首先我们先来看不指定插入头尾的方法，可以看到默认采用的是尾插法。

public boolean add(E e) {// 插入到尾部linkLast(e);return true;
}
void linkLast(E e) {final Node<E> l =  ;final Node<E> newNode = new Node<>(l, e, null);last = newNode;// 尾插法if (l == null)first = newNode;elsel.next = newNode;// 元素个数+1size++;// 修改次数+1，来自AbstractList中modCount++;
}

当然看完上面这个方法后，再看addLast应该就是同理了，

addLast(E e)

public void addLast(E e) {linkLast(e);
}

addFirst(E e)

这个很明显采用的就是头插法了，每次将新插入的节点更新为新的头节点。

public void addFirst(E e) {linkFirst(e);
}
// null<-e->f
private void linkFirst(E e) {// 先copy一份当前的头节点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++;
}

add(int index, E element)

在指定位置插入元素，在LinkedList里面有一个default node()方法，用于查询指定索引的节点，根据位置位于大小中间左边还是右边确定用头节点还是尾节点进行遍历查询。

public void add(int index, E element) {// 检查索引是否合法，是否在[0,size]之间;checkPositionIndex(index);// 如果需要在最末尾进行插入if (index == size)linkLast(element);else// node(index)先查询这个索引下对应的节点linkBefore(element, 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;// 如果pred为null，证明该节点是头节点if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;
}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;}
}

remove(E e)

移除指定元素，在删除的时候需要维护first和last节点，并且只会删除第一个匹配到的元素。

public boolean remove(Object o) {// 移除第一个匹配上的元素if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;
}E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;// 如果prev为null, 说明是头节点，需要更新头节点，直接删除即可if (prev == null) {first = next;} else {//  不是头节点，将前缀节点的next指向删除节点的下一个节点prev.next = next;// GCx.prev = null;}// 判断是否是尾节点，是的话，更新last节点if (next == null) {last = prev;} else {// 不是，将删除节点的next节点的前缀节点改成删除节点的前缀节点next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}

removeFirst()

移除链表的第一个节点，更新新的头节点

public E removeFirst() {// 链表头节点final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;// 将原先的头节点的数据和指向的下一个节点置nullfinal Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;else// 将新头节点的前缀节点置nullnext.prev = null;size--;modCount++;return element;
}

removeLast()

删除链表的尾节点

public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {// assert l == last && l != null;// 将原先链表的尾节点的值和前缀节点都置nullfinal E element = l.item;final Node<E> prev = l.prev;l.item = null;l.prev = null; // help GClast = prev;// 如果前缀节点为null,说明链表只有一个元素，删除后为nullif (prev == null)first = null;else//  将原尾节点的下一个节点置nullprev.next = null;size--;modCount++;return element;
}

set(index, Element e)

public E set(int index, E element) {// 检查节点的索引是否位于[0,size)checkElementIndex(index);// 获取index的节点Node<E> x = node(index);// 更新值E oldVal = x.item;x.item = element;return oldVal;
}

get(int index)

获取指定位置的节点的信息

public E get(int index) {checkElementIndex(index);return node(index).item;
}