ArrayList与LinkedList源码分析-从源码角度分析
ArrayList与LinkedList都是线性表，是可以储存具有相同特性的数据元素的有限序列。但它们内部实现是截然不同的，分别代表了数组和链表的两种实现，这也注定了它们算法的时间复杂度与空间复杂度是不一样的，需要择优使用在不同的场景。接下来将源码（JDK1.8）细节去分析它们的差异。
ArrayList源码分析
- 无参构造函数
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
elementData是一个Object数组，使用transient关键字修饰,transient关键字与Serializable接口配合使用，使用transient关键字修饰的变量不会被序列化。
- int参数构造
private static final Object[] 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);
}
}
当传入的initialCapacity大于0时，初始化一个长度为initialCapacity的Object数组
- Collection参数构造
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;
}
}
public interface Collection<E> extends Iterable<E> {
Object[] toArray();
<T> T[] toArray(T[] a);
}
Collection是一个接口，List、Set、Queue接口继承自Collection接口，所以这里的参数c可以是List、Set、Queue的实现类。toArray()方法有两个，分别返回Object数组和泛型数组。如果toArray()是泛型数组，则拷贝一份到Object数组中并返回。
- add(E e)方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
//如果实际存储数组 是空数组，则最小需要容量就是默认容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//结构改变次数
//如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容
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);
}
ArrayList在没指定initialCapacity时就是相当于会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10；之后扩容增加数组的size>>1的长度,也就是会按照 1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15；当添加第16个数据时，继续扩容变为15 * 1.5 =22个。
- add(int index, E element)
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // 扩容，和add(E e)一样
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
System.arraycopy()方法是一个原生的静态方法，用于从源数组拷贝元素到目标数组中
System.arraycopy() 方法如下:
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,
int length);
src: 源数组 .
srcPos: 源数组中开始拷贝的索引值
dest: 目标数组
destPos: 拷贝到目标数组开始的索引值
length: 拷贝元素的个数
add(int index, E element)就是将index后面的数组copy了一份，并将索引值加1，然后将数组index索引赋值。
- E get(int index)
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
- E 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;
}
- E remove(int index)
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;
return oldValue;
}
numMoved表示要左移的元素，是否是大于0，大于0则将index后的元素左移一个位置，并将最后一个索引的最后一个元素置空。如果等于0，说明是index最后一个元素的索引，不需要左移，直接将最后一个索引置空。
- boolean remove(Object o)
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;
}
判断要移除的object是否为空，为空则移除第一个为null的元素。不为空时则用equals进行比较，如果元素没有重写equals方法，就比较内存地址，有重写就比较定义的equals规则，移除第一个内存地址相同或equals规则相同的元素。
ArrayList总结
- 1.底层数组实现，使用默认构造方法初始化出来的容量是10
- 2.扩容的长度是在原长度基础上加上>>1
- 3.底层是数组，get获取元素性能很好
- 4.线程不安全，所有的方法均不是同步方法也没有加锁，因此多线程下慎用
- 5.添加删除和插入需要复制数组 性能较低
LinkedList源码分析
- 无参构造
public LinkedList() {
}
- Collection参数构造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//将c中的元素都添加到链表中
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);//添加到链表尾部
}
//在序号为index处，添加c中所有的元素到当前链表中（后向添加）
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//检查索引是否合法
Object[] a = c.toArray();//将集合转换为数组
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {//构造方法会走这里，如果index为元素个数，即index个结点为尾结点
succ = null;
pred = last;//前指向指向尾结点，构造方法last这里是null
} else {
succ = node(index);
pred = succ.prev;
}
//for循环结束后，数组a里面的元素都添加到当前链表里面，后向添加
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//新生成一个结点，结点的前向指针指向pred,后向指针为null
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
//如果pred为null，则succ为当前头结点,构造方法会走这里
first = newNode;
else
pred.next = newNode;
pred = newNode;//pred移动到新结点
}
if (succ == null) {
last = pred;//succ为null，这表示index为尾结点之后，构造方法会走这里
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;//元素个数+num
modCount++;//修改次数+1
return true;
}
Collection参数的构造方法将Collection转成数组，并循环遍历数组长度创建Node节点，并将双向链表前后指针赋值。
- add(E e) 、offer(E e)
public boolean offer(E e) {
return add(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
add(E e)调用linkLast(E e)方法把元素添加到尾部，添加到尾部时创建新的节点，prev指针指向最后一个节点，next指针指向null。当最后一个节点为空，说明当前linkedlist元素为空，把新节点作为第一个节点。否则将原来的最后节点的next指针指向新节点。
- add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Node<E> node(int 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;
}
}
void linkBefore(E e, Node<E> succ) {
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++;
}
当add(int index, E element)传入索引==size,调用linkLast(element)添加到后面，在add(E e)中已经分析。不等于size,调用linkBefore(element, node(index))添加到中间或最前面，node(index)方法获取原Node节点，因为采用双向链表的设计，获取原Node节点只需遍历一半，将时间复杂度O(n)变成了O(n/2)，这也是双向链表比单向链表的优点。继续回到linkBefore(E e, Node<E> succ)分析，首先获取原索引Node节点的prev指针，创建新节点，新节点的prev指向原Node的prev，next指针指向原Node。当原节点不为空，将原Node的next指针指向新Node，如果原节点为空，首节点赋值为新Node。
- E remove(int index)
public E remove(int index) {
checkElementIndex(index);//检查索引是否合法
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;//后一个节点
final Node<E> prev = x.prev;//前一个节点
if (prev == null) {//移除的是第一个节点
first = next;
} else {
prev.next = next;//前一个节点的next指针指向后一个节点
x.prev = null;//移除原节点的prev指针指向
}
if (next == null) {//如果移除的是最后一个节点
last = prev;//将最后的last赋值为前一个节点
} else {
next.prev = prev;//将后一个节点的prev指针指向前一个节点
x.next = null;//移除原节点的next指针指向
}
x.item = null;//置空原节点
size--;
modCount++;
return element;
}
E remove(int index)调用E unlink(Node<E> x)方法，获取索引Node的item，和前后节点，将前后节点的prev和next指针对应指向，并断开了原节点prev和next指向，并置空原索引节点，返回原节点item。
- boolean remove(Object o)
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;
}
boolean remove(Object o)比E remove(int index)多了一步，需要先遍历获取索引，然后再调用unlink(Node<E> x)方法，，其他和E remove(int index)一样。
LinkedList总结
- 1.
LinkedList的实现是基于双向链表的，且头结点中不存放数据。 - 2.无参构造方法直接建立一个仅包含
head节点的空链表；包含Collection的构造方法，先调用无参构造方法建立一个空链表，而后将Collection中的数据加入到链表的尾部后面 。 - 3.在查找和删除某元素时，源码中都划分为该元素为
null和不为null两种情况来处理，LinkedList中允许元素为null。 - 4.
LinkedList是基于链表实现的，不存在容量不足的问题，所以没有扩容的方法。 - 5.
Node node(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<(size<<1)，就只从位置0往后遍历到位置index处，而如果index>(size<<1)，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率。 - 6.
LinkedList是基于链表实现的，插入删除效率高，查找效率低。
