LinkedList
LinkedList 的底层就是一个链表线性结构了，链表除了要有一个节点对象外，根据单向链表和双向链表的不同，还有一个或者两个指针。那么 LinkedList 是单链表还是双向链表呢？
LinkedList 存储结构
依旧深入 LinkedList 源码一探究竟，可以看到 LinkedList 无参构造里没有任何操作，不过我们通过查看变量 first、last 可以发现它们就是存储链表第一个和最后 一个的节点。
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; /** * Constructs an empty list. */ public LinkedList() { }
变量 first 和 last 都是 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; } }
可以看到这就是一个典型的双向链表结构，item 用来存放元素值；next 指向下一个 node 节点，prev 指向上一个 node 节点。
双向链表（图片来自 appcoda.com）
LinkedList 数据获取
链表不像数组是连续的内存地址，链表是通过next 和 prev 指向记录链接路径的，所以查找指定位置的 node 只能遍历查找，查看源码也是如此。
public E get(int index) { checkElementIndex(index); return node(index).item; } /** * Returns the (non-null) Node at the specified element index. */ // 遍历查找 index 位置的节点信息 Node<E> node(int index) { // assert isElementIndex(index); // 这里判断 index 是在当前链表的前半部分还是后半部分，然后决定是从 // first 向后查找还是从 last 向前查找。 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; } }
查找指定位置的 node 对象，这个部分要注意的是，查找会首先判断 index 是在当前链表的前半部分还是后半部分，然后决定是从 first 向后查找还是从 last 向前查找。这样可以增加查找速度。从这里也可以看出链表在查找指定位置元素时，效率不高。
LinkedList 数据新增
因为 LinkedList 是链表，所以 LinkedList 的新增也就是链表的数据新增了，这时候要根据要插入的位置的区分操作。
- 尾部插入
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; // 新节点，prev 为当前尾部节点，e为元素值，next 为 null， final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else // 目前的尾部节点 next 指向新的节点 l.next = newNode; size++; modCount++; }
- 默认的 add 方式就是尾部新增了，尾部新增的逻辑很简单，只需要创建一个新的节点，新节点的 prev 设置现有的末尾节点，现有的末尾 Node 指向新节点 Node，新节点的 next 设为 null 即可。
- 中间新增
下面是在指定位置新增元素，涉及到的源码部分。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) // 如果位置就是当前链表尾部，直接尾插 linkLast(element); else // 获取 index 位置的节点，插入新的元素 linkBefore(element, node(index)); } /** * Inserts element e before non-null Node succ. */ // 在指定节点处新增元素，修改指定元素的下一个节点为新增元素，新增元素的下一个节点是查找到得 node 的next节点指向， // 新增元素的上一个节点为查找到的 node 节点，查找到的 node 节点的 next 指向 node 的 prev 修改为新 Node 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++; }
- 可以看到指定位置插入元素主要分为两个部分，第一个部分是查找 node 节点部分，这部分就是上面介绍的 LinkedList 数据获取部分，
第二个部分是在查找到得 node 对象后插入元素。主要就是修改 node 的 next 指向为新节点，新节点的 prev 指向为查找到的 node 节点，新节点的 next 指向为查找到的 node 节点的 next 指向。查找到的 node 节点的 next 指向的 node 节点的 prev 修改为新节点。
LinkedLst 插入元素
LinkedList 数据删除
依旧查看源码进行分析，源码中看到如果节点是头结点或者尾节点，删除比较简单。我们主要看删除中间一个节点时的操作
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } /** * Unlinks non-null 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; }
node(index) 方法依旧是二分查找目标位置，然后进行删除操作。比如要删除的节点叫做 X，删除操作主要是修改 X 节点的 prev 节点的 next 指向为 X 节点的 next 指向，修改 X 节点的 next 节点的 prev 指向为 X 节点的 prev 指向，最后把 X 节点的 prev 和 next 指向清空。如果理解起来有点费劲，可以看下面这个图，可能会比较明白。
LinkedList 删除数据
扩展
你以为 LinkedList 只是一个 List，其他它不仅实现了 List 接口，还实现了 Deque ，所以它表面上是一个 List，其实它还是一个队列。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
体验一下先进先出的队列。
Queue<String> queue = new LinkedList<>(); queue.add("a"); queue.add("b"); queue.add("c"); queue.add("d"); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); // result： // a // b // c // d
同学可以思考一下这个队列是怎么实现的，其实很简单对不对，就是先进先出嘛，poll 时删除 first 节点不就完事了嘛。
总结
不管是 ArrayList 还是 LinkedList 都是开发中常用的集合类，这篇文章分析了两者的底层实现，通过对底层实现的分析我们可以总结出两者的主要优缺点。
- 遍历，ArrayList 每次都是直接定位，LinkedList 通过 next 节点定位，不相上下。这里要注意的是 LinkedList 只有使用迭代器的方式遍历才会使用 next 节点。如果使用
get，则因为遍历查找效率低下。 - 新增，ArrayList 可能会需要扩容，中间插入时，ArrayList 需要后移插入位置之后的所有元素。LinkedList 直接修改 node 的 prev, next 指向，LinkedList 胜出。
- 删除，同 2.
- 随机访问指定位置，ArrayList 直接定位，LinkedList 从头会尾开始查找，数组胜出。
综上所述，ArrayList 适合存储和访问数据，LinkedList 则更适合数据的处理，希望你以后在使用时可以合理的选择 List 结构。
