[TOC] ## LinkedList :-:  ### 1\. 概览 **LinkedList 底层是基于双向链表实现的**，也是实现了 List 接口，所以也拥有 List 的一些特点 (JDK1.7/8 之后取消了循环，修改为双向链表) 。 LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来， LinkedList 简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用 LinkedList ，一方面是因为 Java 官方已经声明不建议使用 Stack 类，更遗憾的是，Java里根本没有一个叫做 Queue 的类（它是个接口名字）。 关于栈或队列，现在的首选是 ArrayDeque，它有着比 LinkedList （当作栈或队列使用时）有着更好的性能。 基于双向链表实现，内部使用 Node 来存储链表节点信息。 ~~~java private static class Node<E> { E item; Node<E> next; Node<E> prev; } ~~~ 每个链表存储了 Head 和 Tail 指针： ~~~java transient Node<E> first; transient Node<E> last; ~~~ LinkedList 的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率*LinkedList*没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用`Collections.synchronizedList()`方法对其进行包装。 ### 2\. add() :-:  add() 方法有两个版本，一个是`add(E e)`，该方法在 LinkedList 的末尾插入元素，因为有 last 指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是`add(int index, E element)`，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。 ~~~java // JDK 1.8 public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ 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++; } ~~~ `add(int index, E element)`的逻辑稍显复杂，可以分成两部分 1. 先根据 index 找到要插入的位置； 2. 修改引用，完成插入操作。 ~~~java 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)); } ~~~ 上面代码中的`node(int index)`函数有一点小小的 trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件`index < (size >> 1)`，也即是 index 是靠近前端还是后端。 ### 3\. remove() remove() 方法也有两个版本，一个是删除跟指定元素相等的第一个元素`remove(Object o)`，另一个是删除指定下标处的元素`remove(int index)`。 :-:  两个删除操作都要： 1. 先找到要删除元素的引用； 2. 修改相关引用，完成删除操作。 在寻找被删元素引用的时候`remove(Object o)`调用的是元素的 equals 方法，而`remove(int index)`使用的是下标计数，两种方式都是线性时间复杂度。在步骤 2 中，两个`revome()`方法都是通过`unlink(Node<E> x)`方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。 ### 4\. get() ~~~java public E get(int index) { checkElementIndex(index); return node(index).item; } 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`离 size 中间距离来判断是从头结点正序查还是从尾节点倒序查。 * node() 会以`O(n/2)`的性能去获取一个结点 * 如果索引值大于链表大小的一半，那么将从尾结点开始遍历 这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。 ### 5\. 总结 * LinkedList 插入，删除都是移动指针效率很高。 * 查找需要进行遍历查询，效率较低。 ### 6\. ArrayList 与 LinkedList * ArrayList 基于动态数组实现，LinkedList 基于双向链表实现； * ArrayList 支持随机访问，LinkedList 不支持； * LinkedList 在任意位置添加删除元素更快。 ### 面试题：ArrayList 与 LinkedList哪个更占空间？ https://www.cnblogs.com/yeya/p/13430797.html