什么是LinkedList

和ArrayList不同，LinkedList是基于链表实现的线性数据结构。节点之间访问不是通过下标进行，而是通过指针。同时，LinkedList实现了List接口和Deque接口。在Deque接口中提供了许多有用的方法，我们下面会选一些详细说。

这是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: 上一个节点

可以看到，LinkedList是双向链表，因为每个节点都有指向前驱后继节点的指针。

他的数据结构类似这样：

| prev | node1 | next | -> | prev | node2 | next | -> | prev | node3 | next | -> | prev | node4 | next |

LinkedList是基于链表实现的，因此我们的重点就是掌握节点之间是如何添加/删除的。掌握了节点是如何修改指针之后，无论是需要第一个元素，还是最后一个元素，还是要获取其中任意一个元素，我们都能够自己实现了。

LinkedList的add()

public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; // 1 final Node<E> newNode = new Node<>(l, e, null); // 2 last = newNode; // 3 if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } add() 方法调用 linkLast() 方法linkLast()方法分以下几步 让一个l 节点指向 last创建一个新的节点newNode，并且把前驱结点设置为 last让last 指向新创建的节点newNode设置 l.next 为新创建的节点

这就实现了把一个新的节点插入到链表末尾的功能。我们可以画图来表示：

| last.prev | last | null | - 这是last节点的数据结构| null | data | null | - 这是新节点的数据结构| last.prev| last | null | -> | last | data | null | - 把 e 的前驱节点设置为 last| last.prev| last | data | -> | last | data | null | - 把 l 的后继节点设置为 newNode

通过这4步，就成功的把两个节点连接在一起了，而且新创建的节点在last节点之后，成为新的尾节点

用文字来总结就是：

持有一个对last节点的引用创建新的节点新节点的前驱设置为lastlast节点的后继设置为新节点

注意：注释3这一步，last = newNode，其实在后面做也可以，只要保证last指向的是最后一个元素地址就可以了。

说完了添加操作，我们再来看看链表的移除。

LinkedList的remove()

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; } 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; }

从代码量来看，remove() 方法比add() 要复杂，实际上也确实是的。

想象一下，一条队伍里相邻的两个人互相手牵手，如果要在队尾加上一个人，那么只是最后一个人和新来的人牵手就可以了。

但是如果是中间某个人要离开队伍了，那么和他相邻的两个人（前驱后继）都会受到影响。在链表里面也是一样的，如果我们要进行中间元素的删除操作，那么需要修改的节点是3个。当然插入中间元素也是一样的意思。

下面进入源码分析阶段：

remove(): 遍历找到要删除的元素如果是null，那么找data == null的节点 (null 不能用equals())如果不为null，那么就找 data.equals(x.item) 的节点，反正是找到第一个值相等的元素

找到之后就进入unlink() 方法：

首先持有x节点的前驱后继节点的指针判断是不是头节点(没有prev)，是的话直接让 first 指向 x.next 就可以了不是头节点的话，让前驱节点的后继节点设为x的后继节点，也就是把x从前驱节点中去掉了再把x的前驱节点设为null，也就是松开自己和前面一个人的手(去掉自己的前驱节点)同样的方法处理后继节点

如果通过画图来展示的话就是：

第一种情况：头节点

| null | x | x.next | -> | x | a | a.next |

直接让first = x.next，也就是让 first 指向 a，完成 x 的删除操作

第二种情况：中间节点

| x | first | first.next | -> | first | x | x.next | -> | x | b | b.next |

首先让 first.next -> b ( x.next )，此时变成了

| x | first | b | -> | first | x | x.next | -> | x | b | b.next |

然后修改x的前驱为null，此时变成了

| x | first | b | -> | null | x | x.next | -> | x | b | b.next |

这就解除了和前驱结点之间的联系，然后相同的思路处理后继节点即可。

第三种情况：尾节点

| x.prev | x | null |

这种情况我们让last指向x.prev就可以了，尾节点就从x变成了它的前一个节点

LinkedList的一些细节

通过我们上面总结的添加和移除元素的思路，再配合Deque接口里面的许多方法，可以实现很多有意思的操作。

有意思的查找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; } }

虽然链表一般情况下来说通过下标来查找，时间复杂度为O(n)，但是LinkedList里面还是用了点小技巧进行优化，通过类似二分法的思想，把整个链表平分为两部分，判断传入的下标是在前半部分还是后半部分，如果是前半部分，那么从头开始找。如果是后半部分，那么就从尾开始找。这样做的好处是：

把O(n) 的时间复杂度缩短为O(n/2)利用了双向链表的优势，可以从前往后，也可以从后往前同样用了位运算来判断index的位置，优化计算效率

LinkedList如何通过下标插入？

LinkedList相比ArrayList的一个优势就是插入删除更加高效，因为只要修改相邻节点就可以了，但是ArrayList需要进行数组的复制移动。需要的内存和时间都更多。

而LinkedList不仅实现了在头/尾插入删除元素，还能指定下标进行添加/删除操作。具体是怎么做到的呢？

public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

核心方法其实就是上面说的node ，传入index然后返回找到的node，然后再通过我们在上面说的，修改前驱后继节点来实现插入操作。

Deque的peekFrist() 和 getFirst()有什么区别？

Deque里面这两个实现方法：

public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } public E element() { return getFirst(); } public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } peek(): 返回 null 或者 元素数据element(): 抛出NoSuchElementException() 或者 元素数据

也就是说，如果我们可以接受null的话，可以使用peekFirst()，类似的方法还有peekLast() 和 getLast()。

LinkedList的clear()

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++; }

为了能够让JVM进行GC，把所有的对象设置为null，包括first & last。

总结

LinkedList的操作都围绕着如果管理相邻节点的前驱后继指针。只要把这个弄清楚，那么无论是添加还是删除都是比较容易写出来的。如果大家觉得不好理解，可以在纸上把数据结构画出来，在每一步操作之后修改对应的节点指针，会好理解一点。

LinkedList实现的Deque接口，提供了许多有用的方法，如果我们需要进行频繁插入删除操作的话，可以优先考虑LinkedList而不是ArrayList，并且看看里面有没有我们需要的实现~

在这里也推荐一些链表相关的算法题，可以通过做题的方式检验一下自己是不是真的掌握了：

LeetCode.19 删除链表倒数第N位节点LeetCode.21 合并两个有序链表LeetCode.206 反转链表LeetCode.237 删除链表中的节点