ArrayList 和 LinkedList都是基于List接口实现，本质是顺序表，提供增删改查数据的基本功能，但效率上各有优劣。接下来通过源码分别看下它们管理和操作数据的具体原理。
List接口
List接口定义了列表最基本的操作，如获取，查找，删除，更新，插入等。
public interface List<E> extends Collection<E> {
int size();//获取列表长度
void add(int index, E element); //插入
E get(int index); //访问
int indexOf(Object o); //查找
E remove(int index); //删除
E set(int index, E element); //更新
default void sort(Comparator<? super E> c) { //默认排序方法
Collections.sort(this, c);
}ArrayList
ArrayList是一个顺序表，内部使用数组保存数据，当容量不足时会自动扩容。
特点：访问某个元素的效率较高，但是查找元素或者在list中间插入元素时效率一般。
特性：
1. 允许重复元素
2. 元素是无序的
3. 操作都是基于普通数组
基本操作
插入，删除，修改，查找，获取操作如下：
1. 插入操作需要先检查是否需要扩容数组，如果数据是插入到尾部的则可直接赋值，否则插入到中部则需arraycopy移动数据腾出空间，再插入数据。
2. 删除操作直接通过arraycopy操作覆盖目标值的位置
3. 修改元素值只需要在数组中直接替换。
4. 查找操作是简单的遍历查找，因此效率可能不高
5. 获取元素操作通过index直接返回，比较高效。
插入数据
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
transient Object[] elementData;
//中间插入元素。
//1.先检查是否需要扩容
//2.移动数组元素腾出位置，然后插入元素
public void add(int index, E element) {
...
ensureCapacityInternal(size + 1); //判断是否需要扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
}访问和查找数据
//获取元素——直接返回数组项
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
//查找——遍历
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;
}删除数据
//删除，通过arraycopy操作，覆盖要删除的元素
public E remove(int 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 work
return oldValue;
}修改数据
//修改元素值
public E set(int index, E element) {
...
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}数组扩容
往ArrayList插入新元素时会判断当前数组长度是否足够，需要时将数据copy到更长的一个数组中，实现扩容。
private static final int DEFAULT_CAPACITY = 10; //每次默认扩展10
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == 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) {
// 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);
//数组扩展到新长度newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
LinkedList
LinkedList是一个双向链表，每个节点包含了上一个和下一个节点的信息，LinkedList只记录头尾2个节点作为成员变量。
对比ArrayList：
1. 优势在于删除和插入等操作，直接操作节点无需移动数据；
2. get和set操作的效率会比ArrayList低，因为ArrayList可以直接访问数组元素，而LinkedList多了寻找节点的过程。
3. 查找操作上LinkedList与ArrayList效率相当，因为它们的数据都是无序的，查找时都是简单的遍历。
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;
//节点类定义
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 void add(int index, E element) {
if (index == size)
linkLast(element); //插入到尾部
else
linkBefore(element, node(index)); //插入到中部
}
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++;
}访问或修改数据
通过指定index获取或修改该节点的数据。
//获取节点值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//修改节点值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//查找节点
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;
}
}查找元素位置
给出具体数据，查找该数据在链表中的位置。
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}删除节点
输入数据实例或者在链表中的下标值，删除该节点。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));//寻找节点后删除其与前后节点的关联
}
//删除节点
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;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}LinkedList的队列特性
LinkedList实现了Deque接口，因此也可以当做FIFO或LIFO的队列使用。
用作FIFO队列的方法：
public E poll() {//队头出列
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E peek() {//获取队头
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public boolean offer(E e) {//新数据排入队尾
return add(e);
}用作LIFO队列的方法：
public E pop() {
return removeFirst();
}
public void push(E e) {
addFirst(e);
}
综合对比
- ArrayList的操作数据都是通过普通的数组实现，随机访问和修改元素比较快，但插入/删除等操作需要移动较多数据，比较适合在访问数据比较频繁的场景使用
- LinkedList是双向链表，在随机访问和修改都需要先去查找节点，但是在插入/删除数据时不需要移动数据，比较适合用在插入/删除频繁的场景中。
- LinkedList还实现了队列接口，通过头或尾进行顺序访问的同时可以删除节点，充分发挥了链表的优势。
工具类Arrays
Arrays.java提供了很多静态方法用于操作数组，例如：复制 ， 填充， 查找， 排序， 数组转换成ArrayList等等。
public class Arrays {
//数组转换成ArrayList
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
//复制数组
public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
//填充数组
public static void fill(Object[] a, Object val) {
for (int i = 0, len = a.length; i < len; i++)
a[i] = val;
}
//二分查找
public static int binarySearch(Object[] a, int fromIndex, int toIndex,
Object key) {
rangeCheck(a.length, fromIndex, toIndex);
return binarySearch0(a, fromIndex, toIndex, key);
}
//排序
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}
}