在List中，LinkedList也是一个非常常见的实现，LinkedList内部是一个双向链表。所有的元素都会以节点的形式保存在内存中，然后通过对链表的操作，来变动这个数据结构。
节点对象
上面提到所有的元素都会以节点的形式保存在内存中, 那么来观察这个内部的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;
}
}
由上述代码可以看出，这个节点拥有这样几个重要信息：
- item：当前元素值
- next：下一个节点
- prev：前一个节点
另外在这个类中，最重要的两个参数头节点和尾节点：
transient Node<E> first;
transient Node<E> last;
初始化
相比ArrayList,LinkedList只有两个构造方法：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c); // 将Collection利用添加元素的方法直接加入链表中
}
这两个构造函数都非常简单，几乎没有什么内容。
添加元素
LinkedList会通过add()方法完成最基本的插入操作：
public boolean add(E e) {
linkLast(e);
return true;
}
由上述可以看出，添加一个元素到LinkedList之中就是将元素添加到这个链表的尾部。详细地探究下linkLast()方法：
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++;
}
这里linkLast()函数会构建一个新的Node节点（如果first节点为空，会将这个节点设置成头节点），并将这个节点设置为last尾节点。将上一个尾节点的下一个节点设置为新的节点。
除此之外，还有addAll()函数：
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;
}
由以上可以看出addAll()函数会将c转换成数组，然后找到index元素的位置，将数组的元素循环添加到尾节点上。
删除节点
根据索引位置删除节点的位置：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
node()函数是一个查找元素的方法：
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;
}
}
这个函数先判断索引的位置在前半段还是后半段，然后通prev或者next遍历直到index的位置。
unlink()函数则将传入的节点从链表中移除，并将这个元素的前后元素链接起来：
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查询特别简单,就是利用了之前已经看过的node()方法：
public E get(int index) {
checkElementIndex(index); // 检查数组是否会越界
return node(index).item;
}
总结
很明显相比ArrayList，LinkedList在增加和删除的时候，不需要大动干戈，自然会节约很多资源（但依然没有办法避免GC），但是在查询元素上，LinkedList就会费劲很多，需要遍历整个链表才能找到数据。
