LinkedList 作为 List 的另一种实现，也非常的经典。与 ArrayList 不同，LinkedList 底层使用的是双向链表来实现的，具体类图如下：
相比于 ArrayList，LinkedList 继承了 AbstractSequentialList 类，而且实现了 Deque 接口，RandomAccess 接口就被没有实现。
但在实际的使用当中，LinkedList 使用的并没有 ArrayList 多，LinkedList 可以被当做队列和栈来使用，但是 BlockingQueue 使用的比它更为广泛，因为一般使用队列的地方都会涉及到比较高的并发，在高并发的情况下，BlockingQueue 比 LinkedList 更好用，BlockingQueue 以后会写专门的文章来介绍。
本文基于 JDK1.8
成员变量
LinkedList 的结构比 ArrayList 更简单，核心的成员变量如下，size 记录当前元素的个数，first 指向头结点，last 指向尾节点。
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Node 的代码如下，通过泛型来存储具体的元素，每个节点都可以获取前一个或者后一个节点，所以 LinkedNode 底层数据结构是双向链表。
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;
}
}
因为底层使用的双向链表，所以理论上来说 LinkedList 的容量是没有限制的，自然也没有了扩容的过程。
实例化过程
LinkedList 的实例化过程也相对简单，只提供了两个构造函数。
一个不带任何参数，也不需要做任何的数据初始化，头结点和尾节点的初始化都放在添加第一个元素的时候。
public LinkedList() {
}
第二个构造函数接收一个 Collection 类型的对象，会把对象中的所有元素都添加到当前 LinkedList 对象中。
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
具体实现
与 ArrayList 相比，LinkedList 有如下特点:
- 不能随机访问
- 容量无限
- 可以用作队列、双向队列和栈
因为 LinkedList 没有实现 RandomAccess 接口，再加上本身底层的数据结构是双向链表，所以对链表中的元素不能随机访问，只能按照顺序访问。
而且对于链表来说，元素时可以无限扩展（理论上）的，所以 LinkedList 的容量也没有上限。
从 JDK1.6 开始，LinkedList 实现了 Deque 接口，这就表明 LinkedList 可以用作队列或者双向队列。
增删改查方法
List 中有的方法，LinkedList 中都实现了。
可以添加元素：
public boolean add(E e) {
linkLast(e);
return true;
}
可以看到，添加元素的操作实际上是用 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++;
}
上面是把元素添加到链表的尾部，因为 LinkedList 还可以被用作队列和栈，因此还提供了从头部添加元素的方法：
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++;
}
既然有添加元素的操作，也有删除元素的操作，代码如下：
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
清空 LinkedList 就是把所有的元素置为 null:
public void clear() {
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++;
}
从以上代码可以发现，LinkedList 的操作都是对链表的操作。
用作队列和栈
做为普通队列时，可以在队列中进行入队和出队的操作。从队列头部获取一个元素，但是不删除元素 peek():
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
从队列头部获取一个元素并删除，poll():
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
在队列的尾部添加一个元素，offer():
public boolean offer(E e) {
return add(e);
}
普通队列只可以在一端入队，在另一端出队，但是对于双向队列，可以在两端执行入队和出队操作。
所以在在作为双向队列时，拿 peek 操作来说即可以 peekFirst() 也可以 peekLast()。其他的操作例如 offer、poll 同样类似。
LinkedList 中还有 push() 和 pop() 操作。被当做栈使用时，只需要对头部节点进行操作就行。
入栈操作:
public void push(E e) {
addFirst(e);
}
出栈操作:
public E pop() {
return removeFirst();
}
其他功能
LinkedList 中也实现了 ListIterator 和 Spliterator 接口。
所以 LinkedList 也可以从两端进行遍历。在遍历的时候，同样也有 fail-fast 机制来检查遍历的过程当中，容器中的元素是否被修改。
在实现 Spliterator 接口之后，也可以对容器中的元素进行分段，然后同时让多个线程同时进行处理，提高处理效率。分割 LinkedList 的代码如下：
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 20; i++) {
list.add(i);
}
Spliterator<Integer> splitor = list.spliterator();
Spliterator<Integer> s1 = splitor.trySplit();
Spliterator<Integer> s2 = s1.trySplit();
System.out.println(s1.estimateSize()); // 10
System.out.println(s2.estimateSize()); // 10
(完)
相关文章
关注微信公众号，聊点其他的
