基于 jdk 1.8
List
ArrayList
ArrayList 字面理解就是由 array 组成的 List，相当于是个变长数组。它底层是个 Object 类型的数组，可放置 null 。
// ArrayList 真正存放值的元素
transient Object[] elementData;
构造函数
// 就是创建 ArrayList，长度为0
new ArrayList()
add
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 code
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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
分位两种情况：当前有值和空值：
- 空值：自动将
ArrayList的size扩展到10 - 有值：若当前长度还够则不扩容，否则扩容
1.5 倍，最大长度是Integer.MAX_VALUE；注意不要频繁扩容，因为扩容时涉及数组的复制影响性能；如果预料到要很大空间可以在一开始就开辟大空间
remove
分为两种情况：删 index 和 删 object
public E remove(int index) {
// 保证数组不越界
rangeCheck(index);
modCount++;
E oldValue = 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;
}
以上代码可知，删除 index 节点后，后面的节点需要往前拷贝，这很耗时。
public boolean remove(Object o) {
if (o == null) {
// ArrayList 可存储 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
}
删除 object 与 删除 index类似，先找到 object 的 index 然后再往前复制即可。指的注意的是，删除操作后都是往前复制，这在 递增 for 循环删除时会出错，最好是倒序循环。
迭代
ArrayList 可被迭代，类中有内部类 Itr
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
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];
}
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();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
这里需要注意一点：在迭代过程中，不能对当前 List 有增删操作，会导致 ConcurrentModificationException 异常；如果你想要在迭代中删除请使用 Itr 自带的 remove() 函数。这是源于 next() 都会去调用 checkForComodification() 来检查 modCount 和 expectedModCount 是否想等，而 List 的增删操作都会去增加 modCount (看上面对应的代码)。
- 优点：适合快速查找和修改，时间
O(1) - 缺点： 删除、指定
index插入性能很低，涉及数组的后续元素的移动
LinkedList
LinkedList 是由 node 连接而成的 list，通俗的说就是双向链表。它允许元素为null，元素是有序的，输出顺序与输入顺序一致； 链表结构如下：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
// 常用的 node 节点
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() {
}
// 通过集合 创建 LinkList
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, 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) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 双链表的插入操作
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 更新插入点的前后节点元素
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
查找
LinkedList 是不能直接通过下标取到值，需要去遍历
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 遍历操作
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;
}
}
可以看到需要遍历 index 才能找到对应的节点，很耗时；但这里做了小小的优化：先判断 index 是靠前还是靠后；如果是靠前从前往后否则从后往前(双向链表)。
add
添加大致可分为三种操作：首添加、中间插入、尾添加
// 首位添加
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
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++;
}
// 中间插入
public void add(int index, E element) {
// 确保数组不越界
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;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
// 尾添加
public boolean add(E e) {
linkLast(e);
return true;
}
public void addLast(E e) {
linkLast(e);
}
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++;
}
LinkedList 是没有空间概念，只有 size 属性和 prev、next 指针关联，所以在添加时没有扩容这种说法。
remove
删除同样可以分为删首位，删中间节点，删尾节点
// 删 firest
public E remove() {
return 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;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
// 删中间节点
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;
}
// 删尾节点
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;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
删除时需要维护的是 prev、next ，以保证双向链表的正常操作。
迭代
和 ArrayList 一样，但要注意删除时只能用迭代器的 remove() 方法。
- 优点：适合增删操作，只需修改相应节点的
prev、next节点的值即可，无需拷贝 - 缺点：不适合查询操作，需要遍历整个
List
