1. 介绍
LinkedList 是 List 和 Deque 接口的双向链表的实现。实现了所有可选列表操作，并允许包括null值。
LinkedList 既然是通过双向链表去实现的，那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效，而随机访问效率比较低。
注意，此实现不是同步的。 如果多个线程同时访问一个 LinkedList 实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。这通常是通过同步那些用来封装列表的 对象来实现的。但如果没有这样的对象存在，则该列表需要运用 {@link Collections#synchronizedList Collections.synchronizedList} 来进行“包装”，该方法最好是在创建列表对象时完成，为了避免对列表进行突发的非同步操作。
List list = Collections.synchronizedList(new LinkedList(...));
类中的 iterator() 方法和 listIterator() 方法返回的 iterators 迭代器是 fail-fast 的：当某一个线程A通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出 ConcurrentModificationException异常，产生 fail-fast 事件。
1.1 数据结构
如上图所示，LinkedList底层使用的双向链表结构，有一个头结点和一个尾结点，双向链表意味着我们可以从头开始正向遍历，或者是从尾开始逆向遍历，并且可以针对头部和尾部进行相应的操作。
1.2 继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
2. 源码分析
2.1 节点 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;
}
}
2.2 主要属性
//实际元素个数
transient int size = 0;
//头节点
transient Node<E> first;
//尾节点
transient Node<E> last;
需要特别注意三个属性都是 transient，也意味着序列化时，三个属性都不会被序列化。
2.3 构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
会调用无参构造函数，并且会把集合中所有的元素添加到LinkedList中。
2.4 主要方法
2.4.1 boolean add(E e)
追加元素到到list尾部。
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++;
}
- 生成新的节点，并将它设置为
last。 - 如果列表为空，则将它设置为
first，否则需要设置与上一节点关系next。 -
size加一， 列表修改次数加一。
2.4.2 void add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size){
linkLast(element);
} else {
linkBefore(element, node(index));
}
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
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++;
}
- 检查位置索引是否合法。
- 如果索引值等于
size，则需要插到队尾。 - 如果小于
size，则需要插到队列中间，需调用linkBefore -
node(int index)中的小细节需要注意，作者做了判断，如果小于size/2，则从队首查找，否则从队尾查找。 - 创建新的节点，并设置
first与next -
size加一，列表修改次数加一。
2.4.3 boolean addAll(int index, Collection<? extends E> c)
由于 boolean addAll(Collection<? extends E> 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;
}
- 检查索引位置是否合法。
- 将集合
c转成数组，但是为什么要转化成数组呢？ - 获取
index索引位置的prev元素与当前元素。变量pred=index索引位置的prev元素, 变量succ=index索引位置元素。 - 遍历数组，创建新的节点，并与
pred建立链接，最终pred= 数组最后一元素节点。 - 设置队尾关系。设置
last、pred、succ之间的关系。 -
size加一，列表修改次数加一
2.4.4 E remove(int index)
删除该索引位置的元素
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;
}
- 检查索引位置合法性
- 减除列表与该索引位置元素的关系。注意细节：
x中的所有属性全部置空。
2.4.5 boolean remove(Object o)
从列表中删除该元素，因为可以存储null，所以必须判断 null。
等同于 boolean removeFirstOccurrence(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;
}
2.4.6 E removeFirst()
此方法等同于 E remove()，删除队首
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
2.4.6 E removeLast()
删除队尾
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
2.4.7 boolean removeLastOccurrence(Object o)
删除最后发现的这个元素。
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;
}
2.4.8 void clear()
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
2.4.9 E get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
2.4.10 E set(int index, E element)
切记：返回的是替换之前的值。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
