前言
LinkedList由于实现了Deque这个接口，所以可以当栈和队列使用。不过一般要用栈或队列的时候推荐使用ArrayDeque,所以这里就不讲LinkedList的栈和队列功能了。还是和上篇ArrayList一样，讲些常用的 *** 。
LinkedList内部是由双链表组成的，里面存放着一个个Node，每个Node又包含三个元素(prev,item,next):
prev:指向前一个Nodeitem:存放存入的数据next:指向下一个Node链表的之一个Node的prev为null，最后个Node的next为null
我简单的画了一张图，可以看下
这个prev和next并不是指向null，因为内存中没有为null分配空间，这边是表示是prev和next为null；
本文内容
01 内部变量
相比于Arraylist，LinkedList内部变量就少得多，就只有三个，size存这当前元素的个数，first指向链表的之一个，last指向列表的最后一个
02 构造 ***
2.1 无参构造 ***
（1）代码实现
List<String> list=new LinkedList<>();
（2）源码分析
无参构造只是初始化了数据，并未做任何操作(初始化 size=0 first=null last=null)
2.2 有参构造 ***
（1）代码实现
List<String> oldList=new LinkedList<>(); List<String> newList=new LinkedList<>(oldList);
（2）源码分析
由于篇幅有限，addAll() *** 这边就不讲了，后面另写文章再讲，里面的操作就相当于把***里的元素***到新***里面。
03 get ***
3.1 get(int index)
这里先讲get() *** ，然后再讲add() *** ，原因是插入 *** 里用到的调用的 *** 个get() *** 里是一样的
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.add("灰"); list.add("灰2"); list.add("灰3"); list.get(2);
（2）源码分析
checkElementIndex(int index)检查越界node(int index)查找Node04 add ***
4.1 add(E e)
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui");
（2）源码分析
linkLast(E e)连接最后一个元素Node<E>内部类就像开头说的，每个Node里有三个，prev:指向前一个Node，item:存放存入的数据，next:指向下一个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; } }
（3）流程图
之一次添加时的流程示意图之一次添加时的流程示意图
不是之一次添加不是之一次添加
4.2 add(int index, E element)
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.add("灰"); list.add(1,"hk");
（2）源码分析
这边插入元素时，先判断插入的位置是不是尾部，如果不尾部的话，先调用和get()那个一样的 *** ，来查找要插入位置的当前元素，然后进行插入操作
checkPositionIndex(int index)检查是否越界这个检查越界的 *** 个get()检查越界的 *** 有点不同，它是可以等于size的，因为linkedList的索引设计也是从0开始的，所以size永远比索引大1
linkBefore(E e, Node<E> succ)插入元素操作（3）流程图
上面说的可能有点绕，看看流程图就明白了，哈哈
添加的位置为之一个添加的位置为之一个
添加的位置为中间添加的位置为中间
05 set ***
5.1 set(int index, E element)
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.set(0,"灰");
（2）源码解析
这里大多调用的是和get()里一样的 ***
06 remove ***
6.1 remove(int index)
按索引删除，先找到被删除的Node，然后解除相关链接，设置Node里三大元素为null，删除后返回被删除Node里的item
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.add("灰"); list.remove(1);
（2）源码解析
unlink(Node<E> x)解除Node的连接，然后返回被解除链接的item（3）流程图
删除的是链表里的之一个元素删除的是链表里的之一个元素
删除的是链表里的中间元素删除的是链表里的最后一个元素6.2 remove(Object o)
这个删除就比较慢了，它内部没有用二分查找算法，而是从头开始一一对比，时间复杂度为O(n)，这个删除也是只删除最早添加的数据
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.remove("hui");
（2）源码解析
unlink() *** 就是上面讲的那个
07 clear ***
7.1 clear()
（1）代码实现
List<String> list=new LinkedList<>(); list.add("hui"); list.clear();
（2）源码解析
总结
LinkedList里删除，添加操作一般就两个步骤，变换前后Node指向的地址，删除操作把对应Node里的三个变量都设置为null，方便GC回收。
如果要删除元素时，更好选择传入索引删除，他比直接传入要删除的对象的 *** 要快很多
作者：灰灰H_K原文链接：https://juejin.im/post/5e12861b6fb9a0481d28b510
