LinkedList
LinkedList 和 ArrayList 一样，都实现了 List 接口，但其内部的数据结构有本质的不同。LinkedList 是基于链表实现的（通过名字也能区分开来），所以它的插入和删除操作比 ArrayList 更加高效。但也是由于其为基于链表的，所以随机访问的效率要比 ArrayList 差。
看一下 LinkedList 的类的定义：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
LinkedList 继承自 AbstractSequenceList，实现了 List、Deque、Cloneable、java.io.Serializable 接口。AbstractSequenceList 提供了List接口骨干性的实现以减少实现 List 接口的复杂度，Deque 接口定义了双端队列的操作。
在 LinkedList 中除了本身自己的方法外，还提供了一些可以使其作为栈、队列或者双端队列的方法。这些方法可能彼此之间只是名字不同，以使得这些名字在特定的环境中显得更加合适。
成员变量
LinkedList 是基于链表结构实现，所以在类中包含了 first 和 last 两个指针(Node)。Node 中包含了上一个节点和下一个节点的引用，这样就构成了双向的链表。每个 Node 只能知道自己的前一个节点和后一个节点。
transient int size = 0;
transient Node<E> first; //链表的头指针
transient Node<E> last; //尾指针
- 如果双端链表为空，则first和last都必须为null
- 如果链表不为空，那么first的前驱节点一定是null，first的item一定不为null，同理，last的后继节点一定是null，last的item一定不为null。
存储对象的结构 Node - LinkedList的内部类
LinkedList类中有一个内部私有类Node，这个类就代表双端链表的节点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;
}
}
双端链表由Node对象组成，每个节点有两个reference指向前驱节点和后继结点，第一个节点的前驱节点为null，最后一个节点的后继节点为null。
构造方法
构造方法1：构造一个空的LinkedList链表结构
public LinkedList() { }
构造方法2：构造一个包含指定元素的collection集合中元素的LinkedList
public LinkedList(Collection<? extends E> c) {
this();
//使用addAll方法，实际上就是使用遍历c并且采用头插法进行双向链表插入值。
addAll(c);
}
操作
增加元素
add(E e)
该方法是在链表的末端添加一个元素，该方法内部调用了自己的方法 linkLast(E e)。
- 该方法首先实例化了一个与待增加元素对应的 Node对象，并将当前链表中的最后一个元素，作为这个新实例的Node对象的前驱节点；
- 并把这个待增加元素对应的 Node对象，作为链表的尾元素；
- 如果在添加这个元素进入链表之前，链表中没有任何元素，则这个待增加元素也作为链表的头元素；否则，将这个待增加元素作为在添加这个元素进入链表之前链表中最后一个元素的后继结点。
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++;
}
addFirst(E e) 和 addLast(E e)
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
从源码中也可以看出，addfirst和addLast这两个方法内部就是直接调用了linkFirst和LinkLast。
linkBefore(E e, Node succ)
下面我们看一个linkBefore方法,从名字可以看出这个方法是在给定的节点前插入一个节点，可以说是linkFirst和linkLast方法的通用版。
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++;
}
add(int index, E element)
该方法是在指定 index 位置插入元素。如果 index 位置正好等于 size，则调用 linkLast(element) 将其插入末尾；否则调用 linkBefore(element, node(index))方法进行插入。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
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++;
}
LinkedList 的方法实在是太多，在这没法一一举例分析。但很多方法其实都只是在调用别的方法而已，所以建议大家将其几个最核心的添加的方法搞懂就可以了，比如 linkBefore、linkLast。其本质也就是链表之间的删除添加等。
删除节点
LinkedList中提供了两个方法删除节点，源码如下所示：
//方法1.删除指定索引上的节点
public E remove(int index) {
//检查索引是否正确
checkElementIndex(index);
//这里分为两步，第一通过索引定位到节点，第二删除节点
return unlink(node(index));
}
//方法2.删除指定值的节点
public boolean remove(Object o) {
//判断删除的元素是否为null
if (o == null) {
//若是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;
}
通过源码可以看出两个方法都是通过unlink()删除。
Node node(int index) 方法
值得一提的是，在 remove(int index) 方法中，调用了 Node<E> node(int index) 方法。
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的位置，是靠近first还是靠近last
- 若靠近first则从头开始查询，否则从尾部开始查询，可以看出这样做更好的利用了LinkedList双向链表的特征
注意，这里用到了移位运算符（»），这里的 size >> 1 等价于 size / 2。
unlink(Node x) 方法
下面是 unlink(Node x) 方法的源码，这个方法是删除节点最核心的方法。
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;
}
- 获取到需要删除元素当前的值，指向它前一个节点的引用，以及指向它后一个节点的引用；
- 判断当前要删除的节点是否为链表的第一个节点，若是则first向后移动，若不是则将当前节点的前一个节点next指向当前节点的后一个节点；
- 判断当前要删除的节点是否为链表的最后一个节点，若是则last向前移动，若不是则将当前节点的后一个节点的prev指向当前节点的前一个节点；
- 将当前节点的值置为null
- size减少并返回删除节点的值
实战
我们可以将LinkedList作为（单端）队列、双端队列或者栈来使用。下面我们分别进行讨论。
LinkedList作为（单端）队列
Queue是一个队列接口，而LinkedList类实现了Queue接口。
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
while (!queue.isEmpty()) {
Integer integer = queue.poll();
System.out.printf("%d ", integer);
}
LinkedList作为双端队列
Deque是一个双端队列接口，而LinkedList类实现了Deque接口。
Deque<Integer> deque = new LinkedList<>();
// 获取第一个元素
deque.getFirst();
// 获取最后一个元素
deque.getLast();
// 获取并移除第一个元素
deque.pollFirst();
// 获取并移除最后一个元素
deque.pollLast();
// 插入元素到头部
deque.addFirst(1);
// 插入元素到队尾
deque.addLast(2);
while (!deque.isEmpty()) {
Integer integer = deque.pollFirst();
System.out.printf("%d ", integer);
}
LinkedList作为栈
LinkedList<Integer> stack = new LinkedList<>();
// 获取栈顶元素
stack.peek();
// 栈顶元素出栈
stack.pop();s
// 栈顶元素入栈
stack.push(2);
Reference
- 《Data Structure And Algorithm Analysis in Java》
- LinkedList 的实现原理 - http://wiki.jikexueyuan.com/project/java-collection/linkedlist.html
- LinkedList实现原理分析（Java源码剖析） - https://www.jianshu.com/p/56c77c517e71
- JAVA学习-LinkedList详解 - https://www.jianshu.com/p/732b5294a985