面试官：你能说说 LinedList 吗？
Python 小星：LinedList 数据结构是链表，查询慢，增删快。
面试官：那 LinkedList 是单向链表还是双向链表？
Python 小星：双向链表
面试官：那 LinkedList 是双向循环链表吗？
Python 小星：......
面试官：没事，那我问你 LinkedList 为什么不用单链表，而是用双链表？
Python 小星：......
面试官：那 LinkedList 删除元素，默认是删除最后一个还是第一个元素？
Python 小星：最后一个
面试官：回去等消息吧
如果你对链表不是很熟悉，可以先看看 @Python大星 之前的文章
这里用图简单带过：
1、单链表
2、双向链表
3、循环链表
单链表 和 双向链表的区别？？？
① 删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有 2*i 次。而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为 i 次。
② 查找时也一样，我们可以借用二分法的思路，从 head（首节点）向后查找操作和 last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。
相信不少小伙伴在浏览其他博客时，会看到有的地方说 LinkedList 是双向链表，有的地方说是双向循环链表。这个各有其道理，jdk 1.6 ，LinkedList 是双向循环链表，从 jdk 1.7 后，LinkedList 是简单的双向链表。下面我们主要以 jdk 1.8 的 LinkedList 说起。
LinkedList 源码解析
1、类的属性
实际元素个数，首节点，尾节点
2、 Node 的静态内部类
3、构造函数
4、查找 - get
先校验 index 的有效性
在查找时，先比较 index 与 （size >> 1），即 index 与 size 中间值比较。
如果 index 较小，则从 first 开始往 last 方向遍历；
如果 index 较大，则从 last 开始往 first 方向遍历。
5、添加 - add
注意：当从指定位置添加元素，其中可能会使用 node 方法，从查找中我们可以知道，查找当前 index 对应的 node 元素，需要遍历链表，如果增加的元素在中间，在大数据量下，花费时间可能比 ArrayList 要多。
① 插入到第一个元素中 - linkFirst
新添加的元素，前节点 pre 为 null，后节点 next 为原 first 节点。
新的 first 节点为当前添加的 new。
判断 first 是否为空，即添加的 new 是否是第一个元素，
如果为空，则 last 节点 为 当前节点 new；
如果不为空，last 节点不变，原 first 的前节点 pre 变更为 new，后节点 next 不变。
② 插入到最后一个元素中 - linkLast
新添加的元素后节点 next 为 null，前节点 pre 为原 last 节点。
新的 last 节点为当前添加的 new。
判断 last 是否为空，即添加的 new 是否是第一个元素，
如果为空，则 first 节点为当前节点 new ；
如果不为空，则原 last 节点的后节点 next 为当前节点 new
③ 在非空节点前插入元素 - linkBefore
和 linkFirst 原理一样
6、修改
先校验 index 的有效性
然后 node 方法返回当前 index 对应的 node 值
最后给原 node 值赋予新的 element
7、删除
我们可以看到 LinkedList 默认是从 first 节点开始删除数据的
@Python大星 | 文
