LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的
jdk在线api
LinkedList继承与AbstractSequentialList，而AbstractSequentialList 继承于AbstractList，是List接口的简化版实现，简化的地方在于：简化在 AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问
想要实现一个支持按次序访问的 List的话，只需要继承这个抽象类，然后把指定的抽象方法实现就好了
需要实现的方法： 为什么实现了这个方法就能正常工作了呢？观察源码可以发现，所有的方法都是围绕这个方法获得的迭代器进行操作的（以get为例）
LinkedList 实现 List 接口，能对它能进行add、set、等一些对列表进行操作的方法操作
既然LinkedList是通过双向链表的，但是它也实现了List接口，也就是说，它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？
实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。
这就是“双线链表和索引值联系起来”的方法
LinkedList实现了Queue接口，代表他是个队列，支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。 Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问
队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null public interface Queue<E> extends Collection<E> { //在尾部添加: boolean add(E e); //offer(E) 在尾部添加: boolean offer(E e); //删除并返回头部 E remove(); //删除并返回头部 如果此队列为空，则返回 null E poll(); //获取头部但不删除 E element(); //获取头部但不删除 如果此队列为空，则返回 null E peek(); }LinkedList也实现了Deque接口，Deque双端队列继承自Queue
此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败
此接口扩展了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法 当队列使用
Queue MethodEquivalent Deque Methodadd(e)addLast(e)offer(e)offerLast(e)remove()removeFirst()poll()pollFirst()element()getFirst()peek()peekFirst()双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法 当栈使用
Queue MethodEquivalent Deque Methodpush(e)addFirst(e)pop()removeFirst()peek()peekFirst()那么就推荐使用iterator，在其中就有一个foreach，增强的for循环，其中原理也就是iterator，我们在使用的时候，使用foreach或者iterator都可以。
有一个头节点，一个尾节点，一个表示链表中实际元素个数的变量
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ // 实际元素个数 transient int size = 0; // 头结点 transient Node<E> first; // 尾结点 transient Node<E> last; }1⃣️ 空参构造函数
/** * Constructs an empty list. */ public LinkedList() { }2⃣️ 有参构造函数
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ //将集合c中的各个元素构建成LinkedList链表。 public LinkedList(Collection<? extends E> c) { // 调用无参构造函数 this(); // 添加集合中所有的元素 addAll(c); }1⃣️ add(E) add函数用于向LinkedList中添加一个元素，并且添加到链表尾部
public boolean add(E e) { // 添加到末尾 linkLast(e); return true; }其中linkLast(e)，就是new出来一个node，pre指向当前的last节点，next为空，再把new出来的node赋值给last，size++，同时还要改边modCount（线程不安全） 注意，再插入前还有一步就是保留当前的last节点，这个的目的就是判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它
/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; //临时节点l(L的小写)保存last，也就是l指向了最后一个节点 final Node<E> newNode = new Node<>(l, e, null);//将e封装为节点，并且e.prev指向了最后一个节点 last = newNode;//newNode成为了最后一个节点，所以last指向了它 if (l == null) //判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它 first = newNode; else //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点 l.next = newNode; size++;//添加一个节点，size自增 modCount++; }2⃣️ addAll()
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //真正核心的地方就是这里了，记得我们传过来的是size，c public boolean addAll(int index, Collection<? extends E> c) { //检查index这个是否为合理。这个很简单，自己点进去看下就明白了。 checkPositionIndex(index); //将集合c转换为Object数组 a Object[] a = c.toArray(); //数组a的长度numNew，也就是由多少个元素 int numNew = a.length; if (numNew == 0) //集合c是个空的，直接返回false，什么也不做。 return false; //集合c是非空的，定义两个节点(内部类)，每个节点都有三个属性，item、next、prev。注意：不要管这两个什么含义，就是用来做临时存储节点的。这个Node看下面一步的源码分析，Node就是linkedList的最核心的实现，可以直接先跳下一个去看Node的分析 Node<E> pred, succ; //构造方法中传过来的就是index==size if (index == size) { //linkedList中三个属性：size、first、last。 size：链表中的元素个数。 first：头节点 last：尾节点，就两种情况能进来这里 //情况一、：构造方法创建的一个空的链表，那么size=0，last、和first都为null。linkedList中是空的。什么节点都没有。succ=null、pred=last=null //情况二、：链表中有节点，size就不是为0，first和last都分别指向第一个节点，和最后一个节点，在最后一个节点之后追加元素，就得记录一下最后一个节点是什么，所以把last保存到pred临时节点中。 succ = null; pred = last; } else { //情况三、index！=size，说明不是前面两种情况，而是在链表中间插入元素，那么就得知道index上的节点是谁，保存到succ临时节点中，然后将succ的前一个节点保存到pred中，这样保存了这两个节点，就能够准确的插入节点了 //举个简单的例子，有2个位置，1、2、如果想插数据到第二个位置，双向链表中，就需要知道第一个位置是谁，原位置也就是第二个位置上是谁，然后才能将自己插到第二个位置上。如果这里还不明白，先看一下文章开头对于各种链表的删除，add操作是怎么实现的。 succ = node(index); pred = succ.prev; } //前面的准备工作做完了，将遍历数组a中的元素，封装为一个个节点。 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //pred就是之前所构建好的，可能为null、也可能不为null，为null的话就是属于情况一、不为null则可能是情况二、或者情况三 Node<E> newNode = new Node<>(pred, e, null); //如果pred==null，说明是情况一，构造方法，是刚创建的一个空链表，此时的newNode就当作第一个节点，所以把newNode给first头节点 if (pred == null) first = newNode; else //如果pred！=null，说明可能是情况2或者情况3，如果是情况2，pred就是last，那么在最后一个节点之后追加到newNode，如果是情况3，在中间插入，pred为原index节点之前的一个节点，将它的next指向插入的节点，也是对的 pred.next = newNode; //然后将pred换成newNode，注意，这个不在else之中，请看清楚了。 pred = newNode; } if (succ == null) { //如果succ==null，说明是情况一或者情况二， 情况一、构造方法，也就是刚创建的一个空链表，pred已经是newNode了，last=newNode，所以linkedList的first、last都指向第一个节点。 情况二、在最后节后之后追加节点，那么原先的last就应该指向现在的最后一个节点了，就是newNode。 last = pred; } else { //如果succ！=null，说明可能是情况三、在中间插入节点，举例说明这几个参数的意义，有1、2两个节点，现在想在第二个位置插入节点newNode，根据前面的代码，pred=newNode，succ=2，并且1.next=newNode， 1已经构建好了，pred.next=succ，相当于在newNode.next = 2； succ.prev = pred，相当于 2.prev = newNode， 这样一来，这种指向关系就完成了。first和last不用变，因为头节点和尾节点没变 pred.next = succ; //。。 succ.prev = pred; } //增加了几个元素，就把 size = size +numNew 就可以了 size += numNew; modCount++; return true; }其中调用了node()函数，此函数是根据索引下标找到该结点并返回，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置
Node<E> node(int index) { // 判断插入的位置在链表前半段或者是后半段 if (index < (size >> 1)) { // 插入位置在前半段 index<size/2 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; // 返回该结点 } }addAll()中的一个问题 在addAll函数中，传入一个集合参数和插入位置，然后将集合转化为数组，然后再遍历数组，挨个添加数组的元素，但是问题来了，为什么要先转化为数组再进行遍历，而不是直接遍历集合呢？
从效果上两者是完全等价的，都可以达到遍历的效果。关于为什么要转化为数组的问题，我的思考如下：
如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。
如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合。
说白了，就是有利于提高多线程访问该集合的效率，尽可能短时间的阻塞
如果我们要移除的值在链表中存在多个一样的值，那么我们会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * {@code i} such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns {@code true} if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return {@code true} if this list contained the specified element */ //首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值，那么我们会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做 public boolean remove(Object o) { //这里可以看到，linkedList也能存储null if (o == null) { //循环遍历链表，直到找到null值，然后使用unlink移除该值。下面的这个else中也一样 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; } /** * Unlinks non-null node x. */ //不能传一个null值过，注意，看之前要注意之前的next、prev这些都是谁。 E unlink(Node<E> x) { // assert x != null; //拿到节点x的三个属性 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。 if (prev == null) { //说明移除的节点是头节点，则first头节点应该指向下一个节点 first = next; } else { //不是头节点，prev.next=next：有1、2、3，将1.next指向3 prev.next = next; //然后解除x节点的前指向。 x.prev = null; } if (next == null) { //说明移除的节点是尾节点 last = prev; } else { //不是尾节点，有1、2、3，将3.prev指向1. 然后将2.next=解除指向。 next.prev = prev; x.next = null; } //x的前后指向都为null了，也把item为null，让gc回收它 x.item = null; size--; //移除一个节点，size自减 modCount++; return element; //由于一开始已经保存了x的值到element，所以返回。 }注意，如果调用iterator()方法，调用的是AbstractSequentialList中的iterator()方法，实际上返回的还是ListIterator
public Iterator<E> iterator() {//AbstractSequentialList中的iterator方法 return listIterator(); } private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } ........ }千万不要使用快速随机访问list.get(i);遍历LinkedList，因为LinkedList并不支持随机访问，每次都从头或尾找，效率低，不像使用迭代器等保留了上次访问的位置m，所以推荐使用迭代器或foreach（语法糖：编译的时候用迭代器实现）
