LinkedList
LinkedList 能解决什么问题？什么时候使用 LinkedList？
1）LinkedList 是实现了 List 接口和 Deque 接口的双向链表，允许使用任意对象及 null 值。
2）LinkedList 随机插入和删除时效率比 ArrayList 高，直接改变元素间的指针，而不需要做数据迁移。
3）LinkedList 基于索引的操作会从双向链表的头部或尾部开始遍历，通过二分确定遍历的起始位置，效率低。
4）LinkedList 支持 fast-fail 机制：LinkedList 返回的 iterator 和 listIterator 都是快速失败的，多线程并发读写 LinkedList 时将抛出 ConcurrentModificationException 异常。
单线程下可以通过 listIterator 迭代器增加、移除元素。
5）LinkedList 的内存消耗比 ArrayList 高，因为需要存储前后元素的指针，元素个数越多越明显。
如何使用 LinkedList？
1）需要提供频繁随机插入和删除元素时，建议使用 LinkedList
使用 LinkedList 有什么风险？
1）涉及到索引相关的操作，LinkedList 性能低于 ArrayList。
LinkedList 核心操作的实现原理？
// LinkedList 的元素个数
transient int size = 0;
/**
* 双向链表的头节点
*/
transient Node<E> first;
/**
* 双向链表的尾节点
*/
transient Node<E> last;
// 创建一个空的 LinkedList 实例
public LinkedList() {
}
/**
* 基于集合中的元素创建 LinkedList 实例
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 将集合中的元素添加到 LinkedList 尾部
*/
@Override
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 将集合中的元素添加到 LinkedList 的指定索引处
*/
@Override
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// 获取目标集合的对象数组
final Object[] a = c.toArray();
// 获取目标元素个数
final int numNew = a.length;
// 目标集合为空则直接返回
if (numNew == 0) {
return false;
}
Node<E> pred, succ;
// 目标索引和元素个数相等，则表示在尾部添加
if (index == size) {
succ = null; // 后置节点为 null
pred = last; // 尾部节点作为前置节点
} else {
// 获取指定索引处的节点
succ = node(index);
// 暂存目标节点的前置节点，目标节点将链接在所有集合元素的后面
pred = succ.prev;
}
for (final Object o : a) {
@SuppressWarnings("unchecked")
final E e = (E) o;
// 创建新的节点
final Node<E> newNode = new Node<>(pred, e, null);
if (pred == null) { // 如果是 LinkedList 为空
first = newNode; // 则新增节点设置为头结点
} else {
pred.next = newNode; // 新增节点链接到前置节点的尾部
}
pred = newNode; // 更新前置节点为新增节点
}
// 如果目标节点为尾节点，则更新 pred 为新的尾节点
if (succ == null) {
last = pred;
} else {
// 否则，更新链接
pred.next = succ;
succ.prev = pred;
}
// 更新元素个数
size += numNew;
// 更新并发修改计数器
modCount++;
return true;
}
/**
* 将目标元素添加到链表尾部，新增成功返回 true
*/
@Override
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 将元素 E 链接为尾部元素
*/
void linkLast(E e) {
// 旧尾部元素
final Node<E> l = last;
// 新值元素的前置节点为旧尾节点，后置节点为 null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 如果是第一个节点，则将头节点设置为新值节点
if (l == null) {
first = newNode;
} else {
// 否则将旧头结点的后置节点设置为新节点
l.next = newNode;
}
size++;
modCount++;
}
/**
* 将目标元素添加到链表尾部，无返回值
*/
@Override
public void addLast(E e) {
linkLast(e);
}
/**
* 将目标元素添加到链表头部
*/
@Override
public void addFirst(E e) {
linkFirst(e);
}
/**
* 将元素 E 链接为头节点
*/
private void linkFirst(E e) {
// 链表的当前头节点
final Node<E> f = first;
// 前置节点设置为 null，后置节点设置为当前头节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
// 如果是第一个元素，则将尾节点也设置为新增节点
if (f == null) {
last = newNode;
} else {
// 原头节点的前置节点设置为新节点
f.prev = newNode;
}
size++;
modCount++;
}
/**
* 将集合中的元素添加到 LinkedList 尾部
*/
@Override
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
- 读取头部节点，可能抛出 NoSuchElementException 异常
/**
* 获取链表的头结点元素，如果为空，则抛出 NoSuchElementException 异常
*/
@Override
public E getFirst() {
final Node<E> f = first;
if (f == null) {
throw new NoSuchElementException();
}
return f.item;
}
- 读取尾部节点，如果为空，则抛出 NoSuchElementException 异常
/**
* 获取链表的尾结点元素，如果为空，则抛出 NoSuchElementException 异常
*/
@Override
public E getLast() {
final Node<E> l = last;
if (l == null) {
throw new NoSuchElementException();
}
return l.item;
}
// 位置访问操作都是基于链表遍历实现的，效率不高
@Override
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
@Override
public E set(int index, E element) {
checkElementIndex(index);
final Node<E> x = node(index);
final E oldVal = x.item;
x.item = element;
return oldVal;
}
/**
* 获取并移除头结点元素，如果为空，则抛出 NoSuchElementException 异常
*/
@Override
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;
}
/**
* 获取并移除尾结点元素，如果为空，则抛出 NoSuchElementException 异常
*/
@Override
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;
}
- 从头遍历，移除第一个和目标元素相等的元素，移除成功返回 true
@Override
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* 移除第一个匹配的目标元素
*/
@Override
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;
}
- 从尾部遍历，移除第一个和目标元素相等的元素，移除成功返回 true
@Override
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
- 查看链表头部元素，链表为空返回 null【双端队列】
@Override
public E peekFirst() {
final Node<E> f = first;
return f == null ? null : f.item;
}
- 查看链表尾部元素，链表为空返回 null【双端队列】
@Override
public E peekLast() {
final Node<E> l = last;
return l == null ? null : l.item;
}
@Override
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
@Override
public boolean offerLast(E e) {
addLast(e);
return true;
}
@Override
public E pollFirst() {
final Node<E> f = first;
return f == null ? null : unlinkFirst(f);
}
@Override
public E pollLast() {
final Node<E> l = last;
return l == null ? null : unlinkLast(l);
}
@Override
public boolean offer(E e) {
return add(e);
}
@Override
public E poll() {
final Node<E> f = first;
return f == null ? null : unlinkFirst(f);
}
/**
* 查看链表头部元素，可能返回 null
*/
@Override
public E peek() {
final Node<E> f = first;
return f == null ? null : f.item;
}
@Override
public void push(E e) {
addFirst(e);
}
@Override
public E pop() {
return removeFirst();
}